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

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

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

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

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

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

@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",

}

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