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=ℓ}.

Original languageEnglish
Title of host publicationDevelopments in Language Theory - 25th International Conference, DLT 2021, Proceedings
EditorsNelma Moreira, Rogério Reis
PublisherSpringer Nature
Pages279-290
Number of pages12
ISBN (Electronic)978-3-030-81508-0
ISBN (Print)9783030815073
DOIs
StatePublished - 2021
Event25th International Conference on Developments in Language Theory, DLT 2021 - Virtual, Online
Duration: 16 Aug 202120 Aug 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12811 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference25th International Conference on Developments in Language Theory, DLT 2021
CityVirtual, Online
Period16/08/2120/08/21

    Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

    Research areas

  • Bounded languages, Finite fields, Formal grammars, Inherent ambiguity, Unambiguous grammars

ID: 93920126