Closure properties of hyper-minimized automata

Institute of Informatics, University of Gdańsk, ul. Wita Stwosza 57, 80-952 Gdańsk, Poland.
matszp@inf.ug.edu.pl

Received: 7 December 2010
Accepted: 10 October 2011

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 L₁ and L₂ the asymptotic state complexity of their sum L₁ ∪ L₂, intersection L₁ ∩ L₂, difference L₁ − L₂, and symmetric difference L₁ ⊕ L₂ can be bounded by s^∗(L₁)·s^∗(L₂). 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 L^R can be bounded by 2^s∗(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].