On the expressive power of GF(2)-grammars

Research outputpeer-review

1 Citation (Scopus)

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.

Original languageEnglish
Title of host publicationSOFSEM 2019
Subtitle of host publicationTheory and Practice of Computer Science - 45th International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings
EditorsRastislav Královič, Giovanni Pighizzini, Jerzy Nawrocki, Barbara Catania
PublisherSpringer Nature
Pages310-323
Number of pages14
ISBN (Print)9783030108007
DOIs
Publication statusPublished - 1 Jan 2019
Event45th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2018 - Nový Smokovec
Duration: 27 Jan 201930 Jan 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11376 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference45th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2018
CountrySlovakia
CityNový Smokovec
Period27/01/1930/01/19

Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'On the expressive power of GF(2)-grammars'. Together they form a unique fingerprint.

  • Cite this

    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