TY - JOUR

T1 - State complexity of GF(2)-operations on unary languages

AU - Okhotin, Alexander

AU - Sazhneva, Elizaveta

N1 - Publisher Copyright: © 2021 Elsevier Inc.

PY - 2022/3

Y1 - 2022/3

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, with the proof based on primitive polynomials over GF(2). For a generalization of the GF(2)-inverse, called the GF(2)-star, the state complexity in the unary case is exactly 2n.

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, with the proof based on primitive polynomials over GF(2). For a generalization of the GF(2)-inverse, called the GF(2)-star, the state complexity in the unary case is exactly 2n.

KW - GF(2)-concatenation

KW - GF(2)-inverse

KW - GF(2)-star

KW - Primitive polynomials

KW - State complexity

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

UR - https://www.mendeley.com/catalogue/be06499a-cf8b-327f-9bab-2db4f7b9584b/

U2 - 10.1016/j.ic.2021.104693

DO - 10.1016/j.ic.2021.104693

M3 - Article

AN - SCOPUS:85099344707

VL - 284

JO - Information and Computation

JF - Information and Computation

SN - 0890-5401

M1 - 104693

ER -