TY - JOUR

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

AU - Okhotin, Alexander

PY - 2011/1/1

Y1 - 2011/1/1

N2 - 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.

AB - 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.

KW - Boolean grammars

KW - Circuit value problem

KW - Conjunctive grammars

KW - Language equations

KW - Trellis automata

UR - http://www.scopus.com/inward/record.url?scp=80051672051&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2010.09.015

DO - 10.1016/j.tcs.2010.09.015

M3 - Article

AN - SCOPUS:80051672051

VL - 412

SP - 68

EP - 82

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 1-2

ER -