Acyclic Context-sensitive Grammars

Erik Aarts


Abstract
A grammar formalism is introduced that generates parse trees with crossing branches. The uniform recognition problem is NP-complete, but for any fixed grammar the recognition problem is polynomial.
Anthology ID:
1995.iwpt-1.2
Volume:
Proceedings of the Fourth International Workshop on Parsing Technologies
Month:
September 20-24
Year:
1995
Address:
Prague and Karlovy Vary, Czech Republic
Editors:
Eva Hajicova, Bernard Lang, Robert Berwick, Harry Bunt, Bob Carpenter, Ken Church, Aravind Joshi, Ronald Kaplan, Martin Kay, Makoto Nagao, Anton Nijholt, Mark Steedman, Henry Thompson, Masaru Tomita, K. Vijay-Shanker, Yorick Wilks, Kent Wittenburg
Venues:
IWPT | WS
SIG:
SIGPARSE
Publisher:
Association for Computational Linguistics
Note:
Pages:
1–9
Language:
URL:
https://aclanthology.org/1995.iwpt-1.2
DOI:
Bibkey:
Cite (ACL):
Erik Aarts. 1995. Acyclic Context-sensitive Grammars. In Proceedings of the Fourth International Workshop on Parsing Technologies, pages 1–9, Prague and Karlovy Vary, Czech Republic. Association for Computational Linguistics.
Cite (Informal):
Acyclic Context-sensitive Grammars (Aarts, IWPT-WS 1995)
Copy Citation:
PDF:
https://aclanthology.org/1995.iwpt-1.2.pdf