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
EditorsMichal Hospodár, Galina Jirásková, Stavros Konstantinidis
PublisherSpringer Nature
Pages248-259
Number of pages12
ISBN (Print)9783030232467
DOIs
StatePublished - 1 Jul 2019
Event21st International Conference on Descriptional Complexity of Formal Systems, DCFS 2019 - Košice, Slovakia
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
Country/TerritorySlovakia
CityKošice
Period17/07/1919/07/19

    Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

ID: 43985755