Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
GF(2)-grammars are a recently introduced grammar family that has some unusual algebraic properties and is closely connected to the family of unambiguous grammars. By using the method of formal power series, we establish strong conditions that are necessary for subsets of a1∗a2∗⋯ak∗ to be described by some GF(2)-grammar. By further applying the established results, we settle the long-standing open question of proving the inherent ambiguity of the language {anbmcℓ∣n≠morm≠ℓ}, as well as give a new, purely algebraic, proof of the inherent ambiguity of the language {anbmcℓ∣n=morm=ℓ}.
Язык оригинала | английский |
---|---|
Название основной публикации | Developments in Language Theory - 25th International Conference, DLT 2021, Proceedings |
Редакторы | Nelma Moreira, Rogério Reis |
Издатель | Springer Nature |
Страницы | 279-290 |
Число страниц | 12 |
ISBN (электронное издание) | 978-3-030-81508-0 |
ISBN (печатное издание) | 9783030815073 |
DOI | |
Состояние | Опубликовано - 2021 |
Событие | 25th International Conference on Developments in Language Theory, DLT 2021 - Virtual, Online Продолжительность: 16 авг 2021 → 20 авг 2021 |
Название | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Том | 12811 LNCS |
ISSN (печатное издание) | 0302-9743 |
ISSN (электронное издание) | 1611-3349 |
конференция | 25th International Conference on Developments in Language Theory, DLT 2021 |
---|---|
Город | Virtual, Online |
Период | 16/08/21 → 20/08/21 |
ID: 93920126