EFFICIENT AUTOMATON-BASED RECOGNITION FOR LINEAR CONJUNCTIVE LANGUAGES
Alexander Okhotin · International Journal of Foundations of Computer Science · 2003
Linear conjunctive grammars have recently been proved computationally equivalent to triangular trellis automata. The relation between these grammars and these automata resembles that between regular expressions and finite automata: while the former are better suited for human use, the latter are considerably easier to implement. This paper studies efficient algorithms for converting a linear conjunctive grammar to an equivalent triangular trellis automaton, and also proposes a number of techniques of reducing the size of these automata.