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 -