On the expressive power of GF(2)-grammars

Vladislav Makarov, Alexander Okhotin

Research output

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

Fingerprint

Context free grammars
Formal languages
Concatenation
Expressive Power
Grammar
Stars
Strings
Homomorphisms
Closed
Context-free Grammar
Formal Languages
Odd number
Unary
Injective
Star
Union
Intersection
Partition
Family
Language

Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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. https://doi.org/10.1007/978-3-030-10801-4_25
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, 2019. pp. 310-323 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@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 = "1",
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",
pages = "310--323",
editor = "Rastislav Kr{\'a}lovič and Giovanni Pighizzini and Jerzy Nawrocki and Barbara Catania",
booktitle = "SOFSEM 2019",
address = "Germany",

}

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, pp. 310-323, Nový Smokovec, 27/01/19. https://doi.org/10.1007/978-3-030-10801-4_25

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

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

ER -

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