The University of Sussex

Evaluation in DATR is co-NP-Hard

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