Standard

A simple P-complete problem and its representations by language equations. / Okhotin, Alexander.

Machines, Computations, and Universality - 5th International Conference, MCU 2007, Proceedings. 2007. стр. 267-278 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 4664 LNCS).

Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование

Harvard

Okhotin, A 2007, A simple P-complete problem and its representations by language equations. в Machines, Computations, and Universality - 5th International Conference, MCU 2007, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Том. 4664 LNCS, стр. 267-278, 5th International Conference on Machines, Computations, and Universality, MCU 2007, Orleans, Франция, 10/09/07.

APA

Okhotin, A. (2007). A simple P-complete problem and its representations by language equations. в Machines, Computations, and Universality - 5th International Conference, MCU 2007, Proceedings (стр. 267-278). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 4664 LNCS).

Vancouver

Okhotin A. A simple P-complete problem and its representations by language equations. в Machines, Computations, and Universality - 5th International Conference, MCU 2007, Proceedings. 2007. стр. 267-278. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

Author

Okhotin, Alexander. / A simple P-complete problem and its representations by language equations. Machines, Computations, and Universality - 5th International Conference, MCU 2007, Proceedings. 2007. стр. 267-278 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{07d588b3c5724072b58f719e17b1f08e,
title = "A simple P-complete problem and its representations by language equations",
abstract = "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.",
author = "Alexander Okhotin",
year = "2007",
month = dec,
day = "1",
language = "English",
isbn = "3540721592",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "267--278",
booktitle = "Machines, Computations, and Universality - 5th International Conference, MCU 2007, Proceedings",
note = "5th International Conference on Machines, Computations, and Universality, MCU 2007 ; Conference date: 10-09-2007 Through 13-09-2007",

}

RIS

TY - GEN

T1 - A simple P-complete problem and its representations by language equations

AU - Okhotin, Alexander

PY - 2007/12/1

Y1 - 2007/12/1

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

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

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

M3 - Conference contribution

AN - SCOPUS:37849021619

SN - 3540721592

SN - 9783540721598

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 267

EP - 278

BT - Machines, Computations, and Universality - 5th International Conference, MCU 2007, Proceedings

T2 - 5th International Conference on Machines, Computations, and Universality, MCU 2007

Y2 - 10 September 2007 through 13 September 2007

ER -

ID: 41143911