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.
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
}
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