Standard

Expressive power of LL(k) boolean grammars. / Okhotin, Alexander.

Fundamentals of Computation Theory - 16th International Symposium, FCT 2007, Proceedings. Springer Nature, 2007. стр. 446-457 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 4639 LNCS).

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

Harvard

Okhotin, A 2007, Expressive power of LL(k) boolean grammars. в Fundamentals of Computation Theory - 16th International Symposium, FCT 2007, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Том. 4639 LNCS, Springer Nature, стр. 446-457, 16th International Symposium on Fundamentals of Computation Theory, FCT 2007, Budapest, Венгрия, 27/08/07. https://doi.org/10.1007/978-3-540-74240-1_39

APA

Okhotin, A. (2007). Expressive power of LL(k) boolean grammars. в Fundamentals of Computation Theory - 16th International Symposium, FCT 2007, Proceedings (стр. 446-457). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 4639 LNCS). Springer Nature. https://doi.org/10.1007/978-3-540-74240-1_39

Vancouver

Okhotin A. Expressive power of LL(k) boolean grammars. в Fundamentals of Computation Theory - 16th International Symposium, FCT 2007, Proceedings. Springer Nature. 2007. стр. 446-457. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-540-74240-1_39

Author

Okhotin, Alexander. / Expressive power of LL(k) boolean grammars. Fundamentals of Computation Theory - 16th International Symposium, FCT 2007, Proceedings. Springer Nature, 2007. стр. 446-457 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{5f9844059c204ff89d5d6e07573ecdca,
title = "Expressive power of LL(k) boolean grammars",
abstract = "The family of languages generated by Boolean grammars and usable with recursive descent parsing is studied. It is demonstrated that Boolean LL languages over a unary alphabet are regular, while Boolean LL subsets of Σ* a* obey a certain periodicity property, which, in particular, makes the language {anb2n | n ≥ 0} nonrepresentable. It is also shown that {anbncs | n ≥ 0, s ∈ {a, b}} is not generated by any linear conjunctive LL grammar, while linear Boolean LL grammars cannot generate {anb nc* |n ≥S 0}.",
author = "Alexander Okhotin",
note = "Funding Information: The author is grateful to the anonymous reviewers for careful reading and numerous valuable comments, and particularly for noticing a serious error in the earlier ad hoc proof of Example 8. The work was supported by the Academy of Finland under grants 118540 and 134860.; 16th International Symposium on Fundamentals of Computation Theory, FCT 2007 ; Conference date: 27-08-2007 Through 30-08-2007",
year = "2007",
doi = "10.1007/978-3-540-74240-1_39",
language = "English",
isbn = "9783540742395",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "446--457",
booktitle = "Fundamentals of Computation Theory - 16th International Symposium, FCT 2007, Proceedings",
address = "Germany",

}

RIS

TY - GEN

T1 - Expressive power of LL(k) boolean grammars

AU - Okhotin, Alexander

N1 - Funding Information: The author is grateful to the anonymous reviewers for careful reading and numerous valuable comments, and particularly for noticing a serious error in the earlier ad hoc proof of Example 8. The work was supported by the Academy of Finland under grants 118540 and 134860.

PY - 2007

Y1 - 2007

N2 - The family of languages generated by Boolean grammars and usable with recursive descent parsing is studied. It is demonstrated that Boolean LL languages over a unary alphabet are regular, while Boolean LL subsets of Σ* a* obey a certain periodicity property, which, in particular, makes the language {anb2n | n ≥ 0} nonrepresentable. It is also shown that {anbncs | n ≥ 0, s ∈ {a, b}} is not generated by any linear conjunctive LL grammar, while linear Boolean LL grammars cannot generate {anb nc* |n ≥S 0}.

AB - The family of languages generated by Boolean grammars and usable with recursive descent parsing is studied. It is demonstrated that Boolean LL languages over a unary alphabet are regular, while Boolean LL subsets of Σ* a* obey a certain periodicity property, which, in particular, makes the language {anb2n | n ≥ 0} nonrepresentable. It is also shown that {anbncs | n ≥ 0, s ∈ {a, b}} is not generated by any linear conjunctive LL grammar, while linear Boolean LL grammars cannot generate {anb nc* |n ≥S 0}.

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

U2 - 10.1007/978-3-540-74240-1_39

DO - 10.1007/978-3-540-74240-1_39

M3 - Conference contribution

AN - SCOPUS:38149008756

SN - 9783540742395

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

SP - 446

EP - 457

BT - Fundamentals of Computation Theory - 16th International Symposium, FCT 2007, Proceedings

PB - Springer Nature

T2 - 16th International Symposium on Fundamentals of Computation Theory, FCT 2007

Y2 - 27 August 2007 through 30 August 2007

ER -

ID: 78926537