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

Alexander Okhotin; Elizaveta Sazhneva

doi:10.1007/978-3-030-23247-4_19

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

Research output › › peer-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 2ⁿ⁻¹ + 1.

Original language	English
Title of host publication	Descriptional Complexity of Formal Systems - 21st IFIP WG 1.02 International Conference, DCFS 2019, Proceedings
Editors	Stavros Konstantinidis, Michal Hospodár, Galina Jirásková
Publisher	Springer Nature
Pages	248-259
Number of pages	12
ISBN (Print)	9783030232467
DOIs	https://doi.org/10.1007/978-3-030-23247-4_19
Publication status	Published - 1 Jul 2019
Event	21st International Conference on Descriptional Complexity of Formal Systems, DCFS 2019 - Košice Duration: 17 Jul 2019 → 19 Jul 2019

Publication series

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

Conference

Conference	21st International Conference on Descriptional Complexity of Formal Systems, DCFS 2019
Country	Slovakia
City	Košice
Period	17/07/19 → 19/07/19

Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

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

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

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

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 Nature, 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 = jul,

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

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

note = "21st International Conference on Descriptional Complexity of Formal Systems, DCFS 2019 ; Conference date: 17-07-2019 Through 19-07-2019",

}

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 Nature, pp. 248-259, 21st International Conference on Descriptional Complexity of Formal Systems, DCFS 2019, 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 Nature, 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 output › › peer-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 Nature

T2 - 21st International Conference on Descriptional Complexity of Formal Systems, DCFS 2019

Y2 - 17 July 2019 through 19 July 2019

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