Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
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 language | English |
---|---|
Title of host publication | Developments in Language Theory - 25th International Conference, DLT 2021, Proceedings |
Editors | Nelma Moreira, Rogério Reis |
Publisher | Springer Nature |
Pages | 279-290 |
Number of pages | 12 |
ISBN (Electronic) | 978-3-030-81508-0 |
ISBN (Print) | 9783030815073 |
DOIs | |
State | Published - 2021 |
Event | 25th International Conference on Developments in Language Theory, DLT 2021 - Virtual, Online Duration: 16 Aug 2021 → 20 Aug 2021 |
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 12811 LNCS |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference | 25th International Conference on Developments in Language Theory, DLT 2021 |
---|---|
City | Virtual, Online |
Period | 16/08/21 → 20/08/21 |
ID: 93920126