A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
A simple P-complete problem and its language-theoretic representations
Tekijät: Okhotin A
Kustantaja: ELSEVIER SCIENCE BV
Julkaisuvuosi: 2011
Journal: Theoretical Computer Science
Tietokannassa oleva lehden nimi: THEORETICAL COMPUTER SCIENCE
Lehden akronyymi: THEOR COMPUT SCI
Numero sarjassa: 1-2
Vuosikerta: 412
Numero: 1-2
Aloitussivu: 68
Lopetussivu: 82
Sivujen määrä: 15
ISSN: 0304-3975
DOI: https://doi.org/10.1016/j.tcs.2010.09.015
Tiivistelmä
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. (C) 2010 Elsevier B.V. All rights reserved.
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. (C) 2010 Elsevier B.V. All rights reserved.
Turun yliopiston Tutkimustietojärjestelmän portaali