DOI

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 авг 202120 авг 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/2120/08/21

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

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

ID: 93920126