DOI

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.

Язык оригиналаанглийский
Название основной публикацииLanguage and Automata Theory and Applications - 14th International Conference, LATA 2020, Proceedings
РедакторыAlberto Leporati, Carlos Martín-Vide, Dana Shapira, Claudio Zandron
ИздательSpringer Nature
Страницы287-299
Число страниц13
ISBN (печатное издание)9783030406073
DOI
СостояниеОпубликовано - 1 янв 2020
Событие14th International Conference on Language and Automata Theory and Applications, LATA 2020 - Milan, Италия
Продолжительность: 4 мар 20206 мар 2020

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том12038 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

конференция

конференция14th International Conference on Language and Automata Theory and Applications, LATA 2020
Страна/TерриторияИталия
ГородMilan
Период4/03/206/03/20

    Предметные области Scopus

  • Теоретические компьютерные науки
  • Компьютерные науки (все)

ID: 52800168