UNI-MB - logo
UMNIK - logo
 
E-resources
Full text
Peer reviewed
  • GF(2)-operations on basic f...
    Okhotin, Alexander; Radionova, Maria; Sazhneva, Elizaveta

    Theoretical computer science, 05/2024, Volume: 995
    Journal Article

    GF(2)-operations on formal languages (Bakinova et al., “Formal languages over GF(2)”, Inf. Comput., 2022) are variants of the classical concatenation and Kleene star obtained by replacing Boolean logic in their definitions with the GF(2) field. This paper investigates closure and non-closure of basic families of languages under these operations. First, it is proved that the group languages (those defined by permutation automata) are closed under GF(2)-concatenation and not closed under GF(2)-star; furthermore, the state complexity of GF(2)-concatenation for m-state and n-state permutation automata is determined as m⋅2n. Next, it is shown that the languages defined by trellis automata (one-way real-time cellular automata) are not closed under either operation, but are closed under GF(2)-concatenation with regular languages; the context-free languages and their linear and unambiguous variants are not closed under GF(2)-concatenation with a two-element set, nor under GF(2)-star; the LR(k) languages are closed under GF(2)-concatenation with a regular set on the right, but not on the left. •Two operations on formal languages, GF(2)-concatenation and GF(2)-star, are investigated.•The language family recognized by permutation automata is closed under GF(2)-concatenation, but not under GF(2)-star.•The language families defined by context-free grammars and their main subclasses are not closed under either operation.•The family recognized by trellis automata is closed under GF(2)-concatenation with regular sets.•The family defined by LR(k) grammars is closed under GF(2) concatenation with regular sets on the right, but not on the left.