Standard

The hardest linear conjunctive language. / Okhotin, Alexander.

в: Information Processing Letters, Том 86, № 5, 15.06.2003, стр. 247-253.

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

Harvard

Okhotin, A 2003, 'The hardest linear conjunctive language', Information Processing Letters, Том. 86, № 5, стр. 247-253. https://doi.org/10.1016/S0020-0190(02)00511-2

APA

Okhotin, A. (2003). The hardest linear conjunctive language. Information Processing Letters, 86(5), 247-253. https://doi.org/10.1016/S0020-0190(02)00511-2

Vancouver

Okhotin A. The hardest linear conjunctive language. Information Processing Letters. 2003 Июнь 15;86(5):247-253. https://doi.org/10.1016/S0020-0190(02)00511-2

Author

Okhotin, Alexander. / The hardest linear conjunctive language. в: Information Processing Letters. 2003 ; Том 86, № 5. стр. 247-253.

BibTeX

@article{6cb0c77e6eae438292cde9205b03ad4f,
title = "The hardest linear conjunctive language",
abstract = "The hardest linear conjunctive language was discussed. The P-complete language of yes-instances of Circuit Value Problem under a suitable encoding was generated by a linear conjunctive grammar, and it was accepted by a triangular trellis automaton. The results have implications on properties of languages generated by conjunctive grammars of general form and on the relationship between the abstract models of parallel computation.",
keywords = "Computational complexity, Conjunctive grammars, Formal languages, Trellis automata",
author = "Alexander Okhotin",
year = "2003",
month = jun,
day = "15",
doi = "10.1016/S0020-0190(02)00511-2",
language = "English",
volume = "86",
pages = "247--253",
journal = "Information Processing Letters",
issn = "0020-0190",
publisher = "Elsevier",
number = "5",

}

RIS

TY - JOUR

T1 - The hardest linear conjunctive language

AU - Okhotin, Alexander

PY - 2003/6/15

Y1 - 2003/6/15

N2 - The hardest linear conjunctive language was discussed. The P-complete language of yes-instances of Circuit Value Problem under a suitable encoding was generated by a linear conjunctive grammar, and it was accepted by a triangular trellis automaton. The results have implications on properties of languages generated by conjunctive grammars of general form and on the relationship between the abstract models of parallel computation.

AB - The hardest linear conjunctive language was discussed. The P-complete language of yes-instances of Circuit Value Problem under a suitable encoding was generated by a linear conjunctive grammar, and it was accepted by a triangular trellis automaton. The results have implications on properties of languages generated by conjunctive grammars of general form and on the relationship between the abstract models of parallel computation.

KW - Computational complexity

KW - Conjunctive grammars

KW - Formal languages

KW - Trellis automata

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

U2 - 10.1016/S0020-0190(02)00511-2

DO - 10.1016/S0020-0190(02)00511-2

M3 - Article

AN - SCOPUS:0037545759

VL - 86

SP - 247

EP - 253

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 5

ER -

ID: 41144982