Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
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.
Original language | English |
---|---|
Title of host publication | SOFSEM 2019 |
Subtitle of host publication | Theory and Practice of Computer Science - 45th International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings |
Editors | Rastislav Královič, Giovanni Pighizzini, Jerzy Nawrocki, Barbara Catania |
Publisher | Springer Nature |
Pages | 310-323 |
Number of pages | 14 |
ISBN (Print) | 9783030108007 |
DOIs | |
State | Published - 1 Jan 2019 |
Event | 45th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2018 - Nový Smokovec, Slovakia Duration: 27 Jan 2019 → 30 Jan 2019 |
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 11376 LNCS |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference | 45th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2018 |
---|---|
Country/Territory | Slovakia |
City | Nový Smokovec |
Period | 27/01/19 → 30/01/19 |
ID: 41137431