Erik Aarts


1995

pdf bib
Acyclic Context-sensitive Grammars
Erik Aarts
Proceedings of the Fourth International Workshop on Parsing Technologies

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.

1992

pdf bib
Uniform Recognition for Acyclic Context-Sensitive Grammars is NP-complete
Erik Aarts
COLING 1992 Volume 4: The 15th International Conference on Computational Linguistics

Search
Co-authors
    Venues