# Closure properties of hyper-minimized automata

RAIRO - Theoretical Informatics and Applications (2012)

- Volume: 45, Issue: 4, page 459-466
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topSzepietowski, Andrzej. "Closure properties of hyper-minimized automata." RAIRO - Theoretical Informatics and Applications 45.4 (2012): 459-466. <http://eudml.org/doc/221950>.

@article{Szepietowski2012,

abstract = {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].},

author = {Szepietowski, Andrzej},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Finite state automata; regular languages; hyper-minimized automata; finite state automata},

language = {eng},

month = {1},

number = {4},

pages = {459-466},

publisher = {EDP Sciences},

title = {Closure properties of hyper-minimized automata},

url = {http://eudml.org/doc/221950},

volume = {45},

year = {2012},

}

TY - JOUR

AU - Szepietowski, Andrzej

TI - Closure properties of hyper-minimized automata

JO - RAIRO - Theoretical Informatics and Applications

DA - 2012/1//

PB - EDP Sciences

VL - 45

IS - 4

SP - 459

EP - 466

AB - 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].

LA - eng

KW - Finite state automata; regular languages; hyper-minimized automata; finite state automata

UR - http://eudml.org/doc/221950

ER -

## References

top- A. Badr, V. Geffert and I. Shipman, Hyper-minimizing minimized deterministic finite state automata. RAIRO-Theor. Inf. Appl.43 (2009) 69–94. Zbl1170.68023
- T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein, Introduction to Algorithms, 2nd edition. MIT Press and McGraw-Hill (2001). Zbl1047.68161
- M. Holzer and A. Maletti, An n log n algorithm for hyper-minimizing a (minimized) deterministic automaton. Theoret. Comput. Sci.411 (2010) 3404–3413. Zbl1206.68173
- 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. Zbl05934417

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.