Closure properties of hyper-minimized automata
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 45 (2011) no. 4, pp. 459-466.

Two deterministic finite automata are almost equivalent if they disagree in acceptance only for finitely many inputs. An automaton A is hyper-minimized if no automaton with fewer states is almost equivalent to A. A regular language L is canonical if the minimal automaton accepting L is hyper-minimized. The asymptotic state complexity s(L) of a regular language L is the number of states of a hyper-minimized automaton for a language finitely different from L. In this paper we show that: (1) the class of canonical regular languages is not closed under: intersection, union, concatenation, Kleene closure, difference, symmetric difference, reversal, homomorphism, and inverse homomorphism; (2) for any regular languages L1 and L2 the asymptotic state complexity of their sum L1 ∪ L2, intersection L1 ∩ L2, difference L1 - L2, and symmetric difference L1 ⊕ L2 can be bounded by s(L1s(L2). This bound is tight in binary case and in unary case can be met in infinitely many cases. (3) For any regular language L the asymptotic state complexity of its reversal LR can be bounded by 2s(L). This bound is tight in binary case. (4) The asymptotic state complexity of Kleene closure and concatenation cannot be bounded. Namely, for every k ≥ 3, there exist languages K, L, and M such that s(K) = s(L) = s(M) = 1 and s(K) = s(L·M) = k. These are answers to open problems formulated by Badr et al. [RAIRO-Theor. Inf. Appl. 43 (2009) 69-94].

DOI : 10.1051/ita/2011128
Classification : 68Q45, 68Q70
Mots clés : finite state automata, regular languages, hyper-minimized automata
@article{ITA_2011__45_4_459_0,
     author = {Szepietowski, Andrzej},
     title = {Closure properties of hyper-minimized automata},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {459--466},
     publisher = {EDP-Sciences},
     volume = {45},
     number = {4},
     year = {2011},
     doi = {10.1051/ita/2011128},
     mrnumber = {2876117},
     zbl = {1232.68087},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita/2011128/}
}
TY  - JOUR
AU  - Szepietowski, Andrzej
TI  - Closure properties of hyper-minimized automata
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2011
SP  - 459
EP  - 466
VL  - 45
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita/2011128/
DO  - 10.1051/ita/2011128
LA  - en
ID  - ITA_2011__45_4_459_0
ER  - 
%0 Journal Article
%A Szepietowski, Andrzej
%T Closure properties of hyper-minimized automata
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2011
%P 459-466
%V 45
%N 4
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita/2011128/
%R 10.1051/ita/2011128
%G en
%F ITA_2011__45_4_459_0
Szepietowski, Andrzej. Closure properties of hyper-minimized automata. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 45 (2011) no. 4, pp. 459-466. doi : 10.1051/ita/2011128. http://www.numdam.org/articles/10.1051/ita/2011128/

[1] A. Badr, V. Geffert and I. Shipman, Hyper-minimizing minimized deterministic finite state automata. RAIRO-Theor. Inf. Appl. 43 (2009) 69-94. | Numdam | MR | Zbl

[2] T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein, Introduction to Algorithms, 2nd edition. MIT Press and McGraw-Hill (2001). | MR | Zbl

[3] M. Holzer and A. Maletti, An n log n algorithm for hyper-minimizing a (minimized) deterministic automaton. Theoret. Comput. Sci. 411 (2010) 3404-3413. | MR | Zbl

[4] G. Jiraskova and J. Sebej, Note on reversal of binary regular languages, in Proc. of DCFS 2011. Lect. Notes Comput. Sci. 6808 (2011) 212-221. | MR

Cité par Sources :