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.