The hardest linear conjunctive language
This paper demonstrates that the P-complete language of yes-instances of Circuit Value Problem under a suitable encoding can be generated by a linear conjunctive grammar, or, equivalently, accepted by a triangular trellis automaton. This result has several implications on the properties of the languages generated by conjunctive grammars of the general form. and on the relationship between the abstract models of parallel computation. (C) 2002 Elsevier Science B.V. All rights reserved.
conjunctive grammars computational complexity formal languages trellis automata