UNI-MB - logo
UMNIK - logo
 
E-resources
Full text
Peer reviewed
  • State complexity of GF(2)-o...
    Okhotin, Alexander; Sazhneva, Elizaveta

    Information and computation, March 2022, 2022-03-00, Volume: 284
    Journal Article

    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.