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
- Venues:
- IWPT | WS
- SIG:
- SIGPARSE
- Publisher:
- Association for Computational Linguistics
- Note:
- Pages:
- 1–9
- Language:
- URL:
- https://aclanthology.org/1995.iwpt-1.2
- DOI:
- 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)
- PDF:
- https://preview.aclanthology.org/auto-file-uploads/1995.iwpt-1.2.pdf