Cyclic shift on multi-component grammars

Alexander Okhotin, Alexey Sorokin

Результат исследований: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

Аннотация

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
СтранаИталия
ГородMilan
Период4/03/206/03/20

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

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

Fingerprint Подробные сведения о темах исследования «Cyclic shift on multi-component grammars». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

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