Standard

Cyclic shift on multi-component grammars. / Okhotin, Alexander; Sorokin, Alexey.

Language and Automata Theory and Applications - 14th International Conference, LATA 2020, Proceedings. ed. / Alberto Leporati; Carlos Martín-Vide; Dana Shapira; Claudio Zandron. Springer Nature, 2020. p. 287-299 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12038 LNCS).

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

Harvard

Okhotin, A & Sorokin, A 2020, Cyclic shift on multi-component grammars. in A Leporati, C Martín-Vide, D Shapira & C Zandron (eds), Language and Automata Theory and Applications - 14th International Conference, LATA 2020, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12038 LNCS, Springer Nature, pp. 287-299, 14th International Conference on Language and Automata Theory and Applications, LATA 2020, Milan, Italy, 4/03/20. https://doi.org/10.1007/978-3-030-40608-0_20

APA

Okhotin, A., & Sorokin, A. (2020). Cyclic shift on multi-component grammars. In A. Leporati, C. Martín-Vide, D. Shapira, & C. Zandron (Eds.), Language and Automata Theory and Applications - 14th International Conference, LATA 2020, Proceedings (pp. 287-299). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12038 LNCS). Springer Nature. https://doi.org/10.1007/978-3-030-40608-0_20

Vancouver

Okhotin A, Sorokin A. Cyclic shift on multi-component grammars. In Leporati A, Martín-Vide C, Shapira D, Zandron C, editors, Language and Automata Theory and Applications - 14th International Conference, LATA 2020, Proceedings. Springer Nature. 2020. p. 287-299. (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-40608-0_20

Author

Okhotin, Alexander ; Sorokin, Alexey. / Cyclic shift on multi-component grammars. Language and Automata Theory and Applications - 14th International Conference, LATA 2020, Proceedings. editor / Alberto Leporati ; Carlos Martín-Vide ; Dana Shapira ; Claudio Zandron. Springer Nature, 2020. pp. 287-299 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{ea5daceed9694dd984fbe37ec5afa608,
title = "Cyclic shift on multi-component grammars",
abstract = "Multi-component grammars, known in the literature as “multiple context-free grammars” and “linear context-free rewriting systems”, describe the structure of a string by defining the properties of k-tuples of its substrings, in the same way as ordinary formal grammars (Chomsky{\textquoteright}s “context-free”) define properties of substrings. It is shown that, for every fixed k, the family of languages described by k-component grammars is closed under the cyclic shift operation. On the other hand, the subfamily defined by well-nested k-component grammars is not closed under the cyclic shift, yet their cyclic shifts are always defined by well-nested (k+1)-component grammars.",
author = "Alexander Okhotin and Alexey Sorokin",
year = "2020",
month = jan,
day = "1",
doi = "10.1007/978-3-030-40608-0_20",
language = "English",
isbn = "9783030406073",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "287--299",
editor = "Alberto Leporati and Carlos Mart{\'i}n-Vide and Dana Shapira and Claudio Zandron",
booktitle = "Language and Automata Theory and Applications - 14th International Conference, LATA 2020, Proceedings",
address = "Germany",
note = "14th International Conference on Language and Automata Theory and Applications, LATA 2020 ; Conference date: 04-03-2020 Through 06-03-2020",

}

RIS

TY - GEN

T1 - Cyclic shift on multi-component grammars

AU - Okhotin, Alexander

AU - Sorokin, Alexey

PY - 2020/1/1

Y1 - 2020/1/1

N2 - Multi-component grammars, known in the literature as “multiple context-free grammars” and “linear context-free rewriting systems”, describe the structure of a string by defining the properties of k-tuples of its substrings, in the same way as ordinary formal grammars (Chomsky’s “context-free”) define properties of substrings. It is shown that, for every fixed k, the family of languages described by k-component grammars is closed under the cyclic shift operation. On the other hand, the subfamily defined by well-nested k-component grammars is not closed under the cyclic shift, yet their cyclic shifts are always defined by well-nested (k+1)-component grammars.

AB - Multi-component grammars, known in the literature as “multiple context-free grammars” and “linear context-free rewriting systems”, describe the structure of a string by defining the properties of k-tuples of its substrings, in the same way as ordinary formal grammars (Chomsky’s “context-free”) define properties of substrings. It is shown that, for every fixed k, the family of languages described by k-component grammars is closed under the cyclic shift operation. On the other hand, the subfamily defined by well-nested k-component grammars is not closed under the cyclic shift, yet their cyclic shifts are always defined by well-nested (k+1)-component grammars.

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

UR - https://www.mendeley.com/catalogue/ca87525f-ba95-36b1-bc61-f796371cf2e2/

U2 - 10.1007/978-3-030-40608-0_20

DO - 10.1007/978-3-030-40608-0_20

M3 - Conference contribution

AN - SCOPUS:85081624251

SN - 9783030406073

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

SP - 287

EP - 299

BT - Language and Automata Theory and Applications - 14th International Conference, LATA 2020, Proceedings

A2 - Leporati, Alberto

A2 - Martín-Vide, Carlos

A2 - Shapira, Dana

A2 - Zandron, Claudio

PB - Springer Nature

T2 - 14th International Conference on Language and Automata Theory and Applications, LATA 2020

Y2 - 4 March 2020 through 6 March 2020

ER -

ID: 52800168