Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Bounded Languages Described by GF(2)-grammars. / Makarov, Vladislav.
Developments in Language Theory - 25th International Conference, DLT 2021, Proceedings. ed. / Nelma Moreira; Rogério Reis. Springer Nature, 2021. p. 279-290 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12811 LNCS).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
}
TY - GEN
T1 - Bounded Languages Described by GF(2)-grammars
AU - Makarov, Vladislav
N1 - Publisher Copyright: © 2021, Springer Nature Switzerland AG.
PY - 2021
Y1 - 2021
N2 - 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=ℓ}.
AB - 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=ℓ}.
KW - Bounded languages
KW - Finite fields
KW - Formal grammars
KW - Inherent ambiguity
KW - Unambiguous grammars
UR - http://www.scopus.com/inward/record.url?scp=85113269412&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-81508-0_23
DO - 10.1007/978-3-030-81508-0_23
M3 - Conference contribution
AN - SCOPUS:85113269412
SN - 9783030815073
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 279
EP - 290
BT - Developments in Language Theory - 25th International Conference, DLT 2021, Proceedings
A2 - Moreira, Nelma
A2 - Reis, Rogério
PB - Springer Nature
T2 - 25th International Conference on Developments in Language Theory, DLT 2021
Y2 - 16 August 2021 through 20 August 2021
ER -
ID: 93920126