Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-05T03:29:17.047Z Has data issue: false hasContentIssue false

Closure properties of hyper-minimized automata

Published online by Cambridge University Press:  14 November 2011

Andrzej Szepietowski*
Affiliation:
Institute of Informatics, University of Gdańsk, ul. Wita Stwosza 57, 80-952 Gdańsk, Poland.. [email protected]
Get access

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

Type
Research Article
Copyright
© EDP Sciences 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Références

Badr, A., Geffert, V. and Shipman, I., Hyper-minimizing minimized deterministic finite state automata. RAIRO-Theor. Inf. Appl. 43 (2009) 6994. Google Scholar
T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein, Introduction to Algorithms, 2nd edition. MIT Press and McGraw-Hill (2001).
Holzer, M. and Maletti, A., An n log n algorithm for hyper-minimizing a (minimized) deterministic automaton. Theoret. Comput. Sci. 411 (2010) 34043413. Google Scholar
Jiraskova, G. and Sebej, J., Note on reversal of binary regular languages, in Proc. of DCFS 2011. Lect. Notes Comput. Sci. 6808 (2011) 212221.Google Scholar