A simple P-complete problem and its language-theoretic representations

Результат исследований: Научные публикации в периодических изданияхстатья

4 Цитирования (Scopus)


A variant of the Circuit Value Problem is introduced, in which every gate implements the NOR function (x v y), and one of the inputs of every kth 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, which can be succinctly represented by language equations of several types. Using this representation, a conjunctive grammar with 8 rules, a Boolean grammar with 5 rules and an LL(1) Boolean grammar with 8 rules for this language are constructed. Another encoding of the problem is represented by a trellis automaton with 11 states and a linear conjunctive grammar with 20 rules.

Язык оригиналаанглийский
Страницы (с-по)68-82
Число страниц15
ЖурналTheoretical Computer Science
Номер выпуска1-2
СостояниеОпубликовано - 1 янв 2011

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

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

Fingerprint Подробные сведения о темах исследования «A simple P-complete problem and its language-theoretic representations». Вместе они формируют уникальный семантический отпечаток (fingerprint).