DOI

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.

Язык оригиналаанглийский
Страницы (с-по)247-253
Число страниц7
ЖурналInformation Processing Letters
Том86
Номер выпуска5
DOI
СостояниеОпубликовано - 15 июн 2003
Опубликовано для внешнего пользованияДа

    Предметные области Scopus

  • Теоретические компьютерные науки
  • Обработка сигналов
  • Информационные системы
  • Прикладные компьютерные науки

ID: 41144982