%0 Conference Proceedings
%T State Complexity of GF(2)-Concatenation and GF(2)-Inverse on Unary Languages
%+ St Petersburg State University (SPbU)
%A Okhotin, Alexander
%A Sazhneva, Elizaveta
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 21th International Conference on Descriptional Complexity of Formal Systems (DCFS)
%C Košice, Slovakia
%Y Michal Hospodár
%Y Galina Jirásková
%Y Stavros Konstantinidis
%I Springer International Publishing
%3 Descriptional Complexity of Formal Systems
%V LNCS-11612
%P 248-259
%8 2019-07-17
%D 2019
%R 10.1007/978-3-030-23247-4_19
%Z Computer Science [cs]Conference papers
%X 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$$.
%G English
%Z TC 1
%Z WG 1.02
%2 https://inria.hal.science/hal-02387287/document
%2 https://inria.hal.science/hal-02387287/file/480958_1_En_19_Chapter.pdf
%L hal-02387287
%U https://inria.hal.science/hal-02387287
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-WG
%~ IFIP-DCFS
%~ IFIP-WG1-2
%~ IFIP-LNCS-11612