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 languageEnglish
Title of host publicationLanguage and Automata Theory and Applications - 14th International Conference, LATA 2020, Proceedings
EditorsAlberto Leporati, Carlos Martín-Vide, Dana Shapira, Claudio Zandron
PublisherSpringer Nature
Pages287-299
Number of pages13
ISBN (Print)9783030406073
DOIs
StatePublished - 1 Jan 2020
Event14th International Conference on Language and Automata Theory and Applications, LATA 2020 - Milan, Italy
Duration: 4 Mar 20206 Mar 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12038 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference14th International Conference on Language and Automata Theory and Applications, LATA 2020
Country/TerritoryItaly
CityMilan
Period4/03/206/03/20

    Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

ID: 52800168