Parsing mildly context-sensitive languages with thread automata
Éric Villemonte de la Clergerie · 2002
We introduce simple but powerful automata called Thread Automata, to describe a wide range of parsing strategies for Mildly Context-Sensitive languages. Thread Automata are completed by a Dynamic Programming interpretation ensuring that tabular parsing may be performed with polynomial worst-case complexity.