Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
GF(2)-grammars, recently introduced by Bakinova et al. (“ Formal languages over GF(2) ”, LATA 2018), are a variant of ordinary context-free grammars, in which the disjunction is replaced by exclusive OR, whereas the classical concatenation is replaced by a new operation called GF(2)-concatenation: KʘL is the set of all strings with an odd number of partitions into a concatenation of a string in K and a string in L. This paper establishes several results on the family of languages defined by these grammars. Over the unary alphabet, GF(2)-grammars define exactly the 2-automatic sets. No language of the form (formula Presented), with uniformly superlinear f, can be described by any GF(2)-grammar. The family is not closed under union, intersection, classical concatenation and Kleene star, non-erasing homomorphisms. On the other hand, this family is closed under injective nondeterministic finite transductions, and contains a hardest language under reductions by homomorphisms.
Язык оригинала | английский |
---|---|
Название основной публикации | SOFSEM 2019 |
Подзаголовок основной публикации | Theory and Practice of Computer Science - 45th International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings |
Редакторы | Rastislav Královič, Giovanni Pighizzini, Jerzy Nawrocki, Barbara Catania |
Издатель | Springer Nature |
Страницы | 310-323 |
Число страниц | 14 |
ISBN (печатное издание) | 9783030108007 |
DOI | |
Состояние | Опубликовано - 1 янв 2019 |
Событие | 45th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2018 - Nový Smokovec, Словакия Продолжительность: 27 янв 2019 → 30 янв 2019 |
Название | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Том | 11376 LNCS |
ISSN (печатное издание) | 0302-9743 |
ISSN (электронное издание) | 1611-3349 |
конференция | 45th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2018 |
---|---|
Страна/Tерритория | Словакия |
Город | Nový Smokovec |
Период | 27/01/19 → 30/01/19 |
ID: 41137431