Standard

On the transformation of ll(k)-linear grammars to ll(1)-linear. / Okhotin, Alexander; Olkhovsky, Ilya.

Computer Science – Theory and Applications - 15th International Computer Science Symposium in Russia, CSR 2020, Proceedings. ed. / Henning Fernau. Springer Nature, 2020. p. 328-340 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12159 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Okhotin, A & Olkhovsky, I 2020, On the transformation of ll(k)-linear grammars to ll(1)-linear. in H Fernau (ed.), Computer Science – Theory and Applications - 15th International Computer Science Symposium in Russia, CSR 2020, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12159 LNCS, Springer Nature, pp. 328-340, 15th International Computer Science Symposium in Russia, CSR 2020, Yekaterinburg, Russian Federation, 29/06/20. https://doi.org/10.1007/978-3-030-50026-9_24

APA

Okhotin, A., & Olkhovsky, I. (2020). On the transformation of ll(k)-linear grammars to ll(1)-linear. In H. Fernau (Ed.), Computer Science – Theory and Applications - 15th International Computer Science Symposium in Russia, CSR 2020, Proceedings (pp. 328-340). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12159 LNCS). Springer Nature. https://doi.org/10.1007/978-3-030-50026-9_24

Vancouver

Okhotin A, Olkhovsky I. On the transformation of ll(k)-linear grammars to ll(1)-linear. In Fernau H, editor, Computer Science – Theory and Applications - 15th International Computer Science Symposium in Russia, CSR 2020, Proceedings. Springer Nature. 2020. p. 328-340. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-030-50026-9_24

Author

Okhotin, Alexander ; Olkhovsky, Ilya. / On the transformation of ll(k)-linear grammars to ll(1)-linear. Computer Science – Theory and Applications - 15th International Computer Science Symposium in Russia, CSR 2020, Proceedings. editor / Henning Fernau. Springer Nature, 2020. pp. 328-340 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{1ad5f85b8cb44949acf62cd47aa7e0c5,
title = "On the transformation of ll(k)-linear grammars to ll(1)-linear",
abstract = "It is proved that every LL(k)-linear grammar can be transformed to an equivalent LL(1)-linear grammar. The transformation incurs a blow-up in the number of nonterminal symbols by a factor of (formula presented), where m is the size of the alphabet. A close lower bound is established: for certain LL(k)-linear grammars with n nonterminal symbols, every equivalent LL(1)-linear grammar must have at least (formula presented) nonterminal symbols.",
author = "Alexander Okhotin and Ilya Olkhovsky",
year = "2020",
month = jun,
day = "1",
doi = "10.1007/978-3-030-50026-9_24",
language = "English",
isbn = "9783030500252",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "328--340",
editor = "Henning Fernau",
booktitle = "Computer Science – Theory and Applications - 15th International Computer Science Symposium in Russia, CSR 2020, Proceedings",
address = "Germany",
note = "15th International Computer Science Symposium in Russia, CSR 2020 ; Conference date: 29-06-2020 Through 03-07-2020",

}

RIS

TY - GEN

T1 - On the transformation of ll(k)-linear grammars to ll(1)-linear

AU - Okhotin, Alexander

AU - Olkhovsky, Ilya

PY - 2020/6/1

Y1 - 2020/6/1

N2 - It is proved that every LL(k)-linear grammar can be transformed to an equivalent LL(1)-linear grammar. The transformation incurs a blow-up in the number of nonterminal symbols by a factor of (formula presented), where m is the size of the alphabet. A close lower bound is established: for certain LL(k)-linear grammars with n nonterminal symbols, every equivalent LL(1)-linear grammar must have at least (formula presented) nonterminal symbols.

AB - It is proved that every LL(k)-linear grammar can be transformed to an equivalent LL(1)-linear grammar. The transformation incurs a blow-up in the number of nonterminal symbols by a factor of (formula presented), where m is the size of the alphabet. A close lower bound is established: for certain LL(k)-linear grammars with n nonterminal symbols, every equivalent LL(1)-linear grammar must have at least (formula presented) nonterminal symbols.

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

UR - https://www.mendeley.com/catalogue/97cf2206-3000-304f-af3e-848913f9cc97/

U2 - 10.1007/978-3-030-50026-9_24

DO - 10.1007/978-3-030-50026-9_24

M3 - Conference contribution

AN - SCOPUS:85087273061

SN - 9783030500252

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

SP - 328

EP - 340

BT - Computer Science – Theory and Applications - 15th International Computer Science Symposium in Russia, CSR 2020, Proceedings

A2 - Fernau, Henning

PB - Springer Nature

T2 - 15th International Computer Science Symposium in Russia, CSR 2020

Y2 - 29 June 2020 through 3 July 2020

ER -

ID: 61323684