no. 4
Closure properties of hyper-minimized automata
RAIRO. Theoretical Informatics and 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∗(L1)·s∗(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
Keywords: 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},
     pages = {459--466},
     year = {2011},
     publisher = {EDP-Sciences},
     volume = {45},
     number = {4},
     doi = {10.1051/ita/2011128},
     mrnumber = {2876117},
     zbl = {1232.68087},
     language = {en},
     url = {https://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
PY  - 2011
SP  - 459
EP  - 466
VL  - 45
IS  - 4
PB  - EDP-Sciences
UR  - https://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
%D 2011
%P 459-466
%V 45
%N 4
%I EDP-Sciences
%U https://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, Tome 45 (2011) no. 4, pp. 459-466. doi: 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. | Zbl | MR | Numdam

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

[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. | Zbl | MR

[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 :