The hardest linear conjunctive language was discussed. The P-complete language of yes-instances of Circuit Value Problem under a suitable encoding was generated by a linear conjunctive grammar, and it was accepted by a triangular trellis automaton. The results have implications on properties of languages generated by conjunctive grammars of general form and on the relationship between the abstract models of parallel computation.

Original languageEnglish
Pages (from-to)247-253
Number of pages7
JournalInformation Processing Letters
Volume86
Issue number5
DOIs
StatePublished - 15 Jun 2003
Externally publishedYes

    Research areas

  • Computational complexity, Conjunctive grammars, Formal languages, Trellis automata

    Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

ID: 41144982