State Complexity of GF(2)-Concatenation and GF(2)-Inverse on Unary Languages

Alexander Okhotin, Elizaveta Sazhneva

Research outputpeer-review

Abstract

The paper investigates the state complexity of two operations on regular languages, known as GF(2)-concatenation and GF(2)-inverse (Bakinova et al., “Formal languages over GF(2)”, LATA 2018), in the case of a one-symbol alphabet. The GF(2)-concatenation is a variant of the classical concatenation obtained by replacing Boolean logic in its definition with the GF(2) field; it is proved that GF(2)-concatenation of two unary languages recognized by an m-state and an n-state DFA is recognized by a DFA with 2mn states, and this number of states is necessary in the worst case, as long as m and n are relatively prime. This operation is known to have an inverse, and the state complexity of the GF(2)-inverse operation over a unary alphabet is proved to be exactly 2n−1 + 1.

Original languageEnglish
Title of host publicationDescriptional Complexity of Formal Systems - 21st IFIP WG 1.02 International Conference, DCFS 2019, Proceedings
EditorsStavros Konstantinidis, Michal Hospodár, Galina Jirásková
PublisherSpringer Nature
Pages248-259
Number of pages12
ISBN (Print)9783030232467
DOIs
Publication statusPublished - 1 Jul 2019
Event21st International Conference on Descriptional Complexity of Formal Systems, DCFS 2019 - Košice
Duration: 17 Jul 201919 Jul 2019

Publication series

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

Conference

Conference21st International Conference on Descriptional Complexity of Formal Systems, DCFS 2019
CountrySlovakia
CityKošice
Period17/07/1919/07/19

Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'State Complexity of GF(2)-Concatenation and GF(2)-Inverse on Unary Languages'. Together they form a unique fingerprint.

  • Cite this

    Okhotin, A., & Sazhneva, E. (2019). State Complexity of GF(2)-Concatenation and GF(2)-Inverse on Unary Languages. In S. Konstantinidis, M. Hospodár, & G. Jirásková (Eds.), Descriptional Complexity of Formal Systems - 21st IFIP WG 1.02 International Conference, DCFS 2019, Proceedings (pp. 248-259). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11612 LNCS). Springer Nature. https://doi.org/10.1007/978-3-030-23247-4_19