Standard

On the expressive power of GF(2)-grammars. / Makarov, Vladislav; Okhotin, Alexander.

SOFSEM 2019: Theory and Practice of Computer Science - 45th International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings. ed. / Rastislav Královič; Giovanni Pighizzini; Jerzy Nawrocki; Barbara Catania. Springer Nature, 2019. p. 310-323 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11376 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Makarov, V & Okhotin, A 2019, On the expressive power of GF(2)-grammars. in R Královič, G Pighizzini, J Nawrocki & B Catania (eds), SOFSEM 2019: Theory and Practice of Computer Science - 45th International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11376 LNCS, Springer Nature, pp. 310-323, 45th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2018, Nový Smokovec, Slovakia, 27/01/19. https://doi.org/10.1007/978-3-030-10801-4_25

APA

Makarov, V., & Okhotin, A. (2019). On the expressive power of GF(2)-grammars. In R. Královič, G. Pighizzini, J. Nawrocki, & B. Catania (Eds.), SOFSEM 2019: Theory and Practice of Computer Science - 45th International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings (pp. 310-323). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11376 LNCS). Springer Nature. https://doi.org/10.1007/978-3-030-10801-4_25

Vancouver

Makarov V, Okhotin A. On the expressive power of GF(2)-grammars. In Královič R, Pighizzini G, Nawrocki J, Catania B, editors, SOFSEM 2019: Theory and Practice of Computer Science - 45th International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings. Springer Nature. 2019. p. 310-323. (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-10801-4_25

Author

Makarov, Vladislav ; Okhotin, Alexander. / On the expressive power of GF(2)-grammars. SOFSEM 2019: Theory and Practice of Computer Science - 45th International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings. editor / Rastislav Královič ; Giovanni Pighizzini ; Jerzy Nawrocki ; Barbara Catania. Springer Nature, 2019. pp. 310-323 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{af6a05a7d98641af8aac4836c589b256,
title = "On the expressive power of GF(2)-grammars",
abstract = "GF(2)-grammars, recently introduced by Bakinova et al. (“ Formal languages over GF(2) ”, LATA 2018), are a variant of ordinary context-free grammars, in which the disjunction is replaced by exclusive OR, whereas the classical concatenation is replaced by a new operation called GF(2)-concatenation: KʘL is the set of all strings with an odd number of partitions into a concatenation of a string in K and a string in L. This paper establishes several results on the family of languages defined by these grammars. Over the unary alphabet, GF(2)-grammars define exactly the 2-automatic sets. No language of the form (formula Presented), with uniformly superlinear f, can be described by any GF(2)-grammar. The family is not closed under union, intersection, classical concatenation and Kleene star, non-erasing homomorphisms. On the other hand, this family is closed under injective nondeterministic finite transductions, and contains a hardest language under reductions by homomorphisms.",
author = "Vladislav Makarov and Alexander Okhotin",
year = "2019",
month = jan,
day = "1",
doi = "10.1007/978-3-030-10801-4_25",
language = "English",
isbn = "9783030108007",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "310--323",
editor = "Rastislav Kr{\'a}lovi{\v c} and Giovanni Pighizzini and Jerzy Nawrocki and Barbara Catania",
booktitle = "SOFSEM 2019",
address = "Germany",
note = "45th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2018 ; Conference date: 27-01-2019 Through 30-01-2019",

}

RIS

TY - GEN

T1 - On the expressive power of GF(2)-grammars

AU - Makarov, Vladislav

AU - Okhotin, Alexander

PY - 2019/1/1

Y1 - 2019/1/1

N2 - GF(2)-grammars, recently introduced by Bakinova et al. (“ Formal languages over GF(2) ”, LATA 2018), are a variant of ordinary context-free grammars, in which the disjunction is replaced by exclusive OR, whereas the classical concatenation is replaced by a new operation called GF(2)-concatenation: KʘL is the set of all strings with an odd number of partitions into a concatenation of a string in K and a string in L. This paper establishes several results on the family of languages defined by these grammars. Over the unary alphabet, GF(2)-grammars define exactly the 2-automatic sets. No language of the form (formula Presented), with uniformly superlinear f, can be described by any GF(2)-grammar. The family is not closed under union, intersection, classical concatenation and Kleene star, non-erasing homomorphisms. On the other hand, this family is closed under injective nondeterministic finite transductions, and contains a hardest language under reductions by homomorphisms.

AB - GF(2)-grammars, recently introduced by Bakinova et al. (“ Formal languages over GF(2) ”, LATA 2018), are a variant of ordinary context-free grammars, in which the disjunction is replaced by exclusive OR, whereas the classical concatenation is replaced by a new operation called GF(2)-concatenation: KʘL is the set of all strings with an odd number of partitions into a concatenation of a string in K and a string in L. This paper establishes several results on the family of languages defined by these grammars. Over the unary alphabet, GF(2)-grammars define exactly the 2-automatic sets. No language of the form (formula Presented), with uniformly superlinear f, can be described by any GF(2)-grammar. The family is not closed under union, intersection, classical concatenation and Kleene star, non-erasing homomorphisms. On the other hand, this family is closed under injective nondeterministic finite transductions, and contains a hardest language under reductions by homomorphisms.

UR - http://www.scopus.com/inward/record.url?scp=85062357069&partnerID=8YFLogxK

UR - http://www.mendeley.com/research/expressive-power-gf2grammars

U2 - 10.1007/978-3-030-10801-4_25

DO - 10.1007/978-3-030-10801-4_25

M3 - Conference contribution

AN - SCOPUS:85062357069

SN - 9783030108007

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 310

EP - 323

BT - SOFSEM 2019

A2 - Královič, Rastislav

A2 - Pighizzini, Giovanni

A2 - Nawrocki, Jerzy

A2 - Catania, Barbara

PB - Springer Nature

T2 - 45th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2018

Y2 - 27 January 2019 through 30 January 2019

ER -

ID: 41137431