@inproceedings{559ed2c8d1e344058f184300882f90aa,
title = "The complexity and generative capacity of lexicalized abstract categorial grammars",
abstract = "Previous studies have shown that some well-known classes of grammars can be simulated by Abstract Categorial Grammars (de Groote 2001) in straightforward ways. These classes of grammars all generate subclasses of the PTIME languages. While the exact generative capacity of the class of ACGs and the complexity of its universal membership problem are both unknown, we show that the universal membership problem for the class of lexicalized ACGs is NP-complete and the languages generated by lexicalized ACGs form a subclass of NP which includes some NP-complete languages.",
author = "Ryo Yoshinaka and Makoto Kanazawa",
year = "2005",
month = jan,
day = "1",
doi = "10.1007/11422532_22",
language = "English",
isbn = "3540257837",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "330--346",
booktitle = "Logical Aspects of Computational Linguistics - 5th International Conference, LACL 2005, Proceedings",
note = "5th International Conference on Logical Aspects of Computational Linguistics, LACL 2005 ; Conference date: 28-04-2005 Through 30-04-2005",
}