Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
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.
Original language | English |
---|---|
Title of host publication | Language and Automata Theory and Applications - 14th International Conference, LATA 2020, Proceedings |
Editors | Alberto Leporati, Carlos Martín-Vide, Dana Shapira, Claudio Zandron |
Publisher | Springer Nature |
Pages | 287-299 |
Number of pages | 13 |
ISBN (Print) | 9783030406073 |
DOIs | |
State | Published - 1 Jan 2020 |
Event | 14th International Conference on Language and Automata Theory and Applications, LATA 2020 - Milan, Italy Duration: 4 Mar 2020 → 6 Mar 2020 |
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 12038 LNCS |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference | 14th International Conference on Language and Automata Theory and Applications, LATA 2020 |
---|---|
Country/Territory | Italy |
City | Milan |
Period | 4/03/20 → 6/03/20 |
ID: 52800168