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

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

Fingerprint

State Complexity
Formal languages
Concatenation
Unary
Relatively prime
Formal Languages
Regular Languages
Logic
Necessary
Language

Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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. https://doi.org/10.1007/978-3-030-23247-4_19
Okhotin, Alexander ; Sazhneva, Elizaveta. / State Complexity of GF(2)-Concatenation and GF(2)-Inverse on Unary Languages. Descriptional Complexity of Formal Systems - 21st IFIP WG 1.02 International Conference, DCFS 2019, Proceedings. editor / Stavros Konstantinidis ; Michal Hospodár ; Galina Jirásková. Springer, 2019. pp. 248-259 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{994308a0091747eca1166701cb4b34ba,
title = "State Complexity of GF(2)-Concatenation and GF(2)-Inverse on Unary Languages",
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.",
author = "Alexander Okhotin and Elizaveta Sazhneva",
year = "2019",
month = "7",
day = "1",
doi = "10.1007/978-3-030-23247-4_19",
language = "English",
isbn = "9783030232467",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "248--259",
editor = "Stavros Konstantinidis and Michal Hospod{\'a}r and Galina Jir{\'a}skov{\'a}",
booktitle = "Descriptional Complexity of Formal Systems - 21st IFIP WG 1.02 International Conference, DCFS 2019, Proceedings",
address = "Germany",

}

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. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11612 LNCS, Springer, pp. 248-259, Košice, 17/07/19. https://doi.org/10.1007/978-3-030-23247-4_19

State Complexity of GF(2)-Concatenation and GF(2)-Inverse on Unary Languages. / Okhotin, Alexander; Sazhneva, Elizaveta.

Descriptional Complexity of Formal Systems - 21st IFIP WG 1.02 International Conference, DCFS 2019, Proceedings. ed. / Stavros Konstantinidis; Michal Hospodár; Galina Jirásková. Springer, 2019. p. 248-259 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11612 LNCS).

Research outputpeer-review

TY - GEN

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

AU - Okhotin, Alexander

AU - Sazhneva, Elizaveta

PY - 2019/7/1

Y1 - 2019/7/1

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

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

UR - http://www.scopus.com/inward/record.url?scp=85069478114&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-23247-4_19

DO - 10.1007/978-3-030-23247-4_19

M3 - Conference contribution

AN - SCOPUS:85069478114

SN - 9783030232467

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 248

EP - 259

BT - Descriptional Complexity of Formal Systems - 21st IFIP WG 1.02 International Conference, DCFS 2019, Proceedings

A2 - Konstantinidis, Stavros

A2 - Hospodár, Michal

A2 - Jirásková, Galina

PB - Springer

ER -

Okhotin A, Sazhneva E. State Complexity of GF(2)-Concatenation and GF(2)-Inverse on Unary Languages. In Konstantinidis S, Hospodár M, Jirásková G, editors, Descriptional Complexity of Formal Systems - 21st IFIP WG 1.02 International Conference, DCFS 2019, Proceedings. Springer. 2019. p. 248-259. (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-23247-4_19