Lionel Moser
Lower bounds of NP-hard and co-NP-hard for the time complexity of DATR query evaluation are established by showing that an NP-complete language can be recognized in DATR, and that its complement can be as well.
Download zip file
