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 language | English |
|---|---|
| Pages (from-to) | 247-253 |
| Number of pages | 7 |
| Journal | Information Processing Letters |
| Volume | 86 |
| Issue number | 5 |
| DOIs | |
| State | Published - 15 Jun 2003 |
| Externally published | Yes |
ID: 41144982