Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
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
}
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