Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › Рецензирование
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 мар 2020 → 6 мар 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/20 → 6/03/20 |
ID: 52800168