TY - GEN
T1 - State Complexity of GF(2)-inverse and GF(2)-star on Binary Languages
AU - Okhotin, Alexander
AU - Sazhneva, Elizaveta
N1 - Funding Information:
Supported by Russian Science Foundation, project 18-11-00100.
Publisher Copyright:
© 2020, Springer Nature Switzerland AG.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2020
Y1 - 2020
N2 - The GF(2)-inverse operation on formal languages is known to have state complexity for alphabets with at least three symbols, and for a one-symbol alphabet. In this paper, it is shown that, for a two-symbol alphabet, its state complexity is exactly For a more general operation of GF(2)-star, its state complexity for a binary alphabet remains.
AB - The GF(2)-inverse operation on formal languages is known to have state complexity for alphabets with at least three symbols, and for a one-symbol alphabet. In this paper, it is shown that, for a two-symbol alphabet, its state complexity is exactly For a more general operation of GF(2)-star, its state complexity for a binary alphabet remains.
UR - http://www.scopus.com/inward/record.url?scp=85097427528&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-62536-8_12
DO - 10.1007/978-3-030-62536-8_12
M3 - Conference contribution
AN - SCOPUS:85097427528
SN - 9783030625351
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 142
EP - 154
BT - Descriptional Complexity of Formal Systems - 22nd International Conference, 2020, Proceedings
A2 - Jirásková, Galina
A2 - Pighizzini, Giovanni
PB - Springer Nature
T2 - 22nd International Conference on Descriptional Complexity of Format Systems, DCFS 2020
Y2 - 24 August 2020 through 26 August 2020
ER -