Standard

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 › peer-review

Harvard

Makarov, V 2021, Bounded Languages Described by GF(2)-grammars. in N Moreira & R Reis (eds), Developments in Language Theory - 25th International Conference, DLT 2021, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12811 LNCS, Springer Nature, pp. 279-290, 25th International Conference on Developments in Language Theory, DLT 2021, Virtual, Online, 16/08/21. https://doi.org/10.1007/978-3-030-81508-0_23

APA

Makarov, V. (2021). Bounded Languages Described by GF(2)-grammars. In N. Moreira, & R. Reis (Eds.), Developments in Language Theory - 25th International Conference, DLT 2021, Proceedings (pp. 279-290). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12811 LNCS). Springer Nature. https://doi.org/10.1007/978-3-030-81508-0_23

Vancouver

Makarov V. Bounded Languages Described by GF(2)-grammars. In Moreira N, Reis R, editors, Developments in Language Theory - 25th International Conference, DLT 2021, Proceedings. Springer Nature. 2021. p. 279-290. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-030-81508-0_23

Author

Makarov, Vladislav. / Bounded Languages Described by GF(2)-grammars. Developments in Language Theory - 25th International Conference, DLT 2021, Proceedings. editor / Nelma Moreira ; Rogério Reis. Springer Nature, 2021. pp. 279-290 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{1aaef5454a804701b4e25e82eccd70c4,
title = "Bounded Languages Described by GF(2)-grammars",
abstract = "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=ℓ}.",
keywords = "Bounded languages, Finite fields, Formal grammars, Inherent ambiguity, Unambiguous grammars",
author = "Vladislav Makarov",
note = "Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.; 25th International Conference on Developments in Language Theory, DLT 2021 ; Conference date: 16-08-2021 Through 20-08-2021",
year = "2021",
doi = "10.1007/978-3-030-81508-0_23",
language = "English",
isbn = "9783030815073",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "279--290",
editor = "Nelma Moreira and Rog{\'e}rio Reis",
booktitle = "Developments in Language Theory - 25th International Conference, DLT 2021, Proceedings",
address = "Germany",

}

RIS

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