State Complexity of Linear Conjunctive Languages
Alexander Okhotin · 2004
The e-free languages generated by linear conjunctive grammars have recently been proved to be exactly the languages accepted by trellis automata. This paper begins the study of the descriptional complexity of this language family by comparing the number of states in automata with the size of grammars. The state complexity of the languages $(a^C)^+$ and $\{a^n(b^C^n)^+ | n\geq 1\}$ is determined (it is $C$ and $C+3$, respectively), leading to an exact expression for the worst-case complexity of all set-theoretic operations and to the non-uniqueness of minimal automata. A superpolynomial lower bound and an exponential upper bound for the succinctness tradeoff between linear conjunctive grammars and trellis automata are established.