A variant of Circuit Value Problem over the basis of Peirce's arrow (NOR) is introduced, in which one of the inputs of every k-th gate must be the (k - 1)-th gate. The problem, which remains P-complete, is encoded as a simple formal language over a two-letter alphabet. It is shown that this language can be naturally and succinctly represented by language equations from several classes. Using this representation, a small conjunctive grammar and an even smaller LL(1) Boolean grammar for this language are constructed.

Язык оригиналаанглийский
Название основной публикацииMachines, Computations, and Universality - 5th International Conference, MCU 2007, Proceedings
Страницы267-278
Число страниц12
СостояниеОпубликовано - 1 дек 2007
Событие5th International Conference on Machines, Computations, and Universality, MCU 2007 - Orleans, Франция
Продолжительность: 10 сен 200713 сен 2007

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том4664 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

конференция

конференция5th International Conference on Machines, Computations, and Universality, MCU 2007
Страна/TерриторияФранция
ГородOrleans
Период10/09/0713/09/07

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

  • Теоретические компьютерные науки
  • Компьютерные науки (все)

ID: 41143911