State Complexity of GF(2)-Concatenation and GF(2)-Inverse on Unary Languages - Descriptional Complexity of Formal Systems
Conference Papers Year : 2019

State Complexity of GF(2)-Concatenation and GF(2)-Inverse on Unary Languages

Alexander Okhotin
  • Function : Author
  • PersonId : 1024589
Elizaveta Sazhneva
  • Function : Author
  • PersonId : 1059498

Abstract

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 $$2^{n-1}+1$$.
Fichier principal
Vignette du fichier
480958_1_En_19_Chapter.pdf (430.22 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

hal-02387287 , version 1 (29-11-2019)

Licence

Identifiers

Cite

Alexander Okhotin, Elizaveta Sazhneva. State Complexity of GF(2)-Concatenation and GF(2)-Inverse on Unary Languages. 21th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2019, Košice, Slovakia. pp.248-259, ⟨10.1007/978-3-030-23247-4_19⟩. ⟨hal-02387287⟩
46 View
57 Download

Altmetric

Share

More