×

Intersection and union of regular languages and state complexity. (English) Zbl 0763.68048

Summary: A natural complexity measure for regular languages is the state complexity, i.e., the number of states needed by various finite-state devices (deterministic, non-deterministic, or other finite automata) in order to recognize the language. Often the state complexity influences the computational complexity of algorithms that use regular languages. Among the most fundamental operations that preserve regularity are intersection and union. It is well known that if \(k\) languages are each recognized by non-deterministic (or deterministic) finite automata with \(n\) states, then their intersection is recognized by a non-deterministic (respectively deterministic) finite automaton with \(n^ k\) states. Until recently little was known about lower-bounds or, in particular, about the optimality of the upper-bounds. R. Ravikumar [Some applications of a technique by Sakoda and Sipser, SIGAT News 21, No. 4, 73-77 (1990)] considers the follow problem. Given \(n\) languages \(L_ n^{(0)},L_ n^{(1)},\dots,L_ n^{(n-1)}\), each of which is recognized by a DFA (deterministic finite automaton) with \(n\) states: what is the number of states of the minimum DFR for the intersection \(\bigcap_ i L_ n^{(i)}\) in the worst case? He proves a lower bound of \(n!+1\); but, as E. Leiss [Some comments on a recent note of Ravikumar, SIGACT News 22, No. 1, 64 (1991)] points out, this does not completely solve the problem, since the best known upper bound is \(n^ n\). Below we show a lower bound of \(n^ n\); so the well-known upper bound is actually optimal. We extend this result to non-deterministic finite automata. We also consider the operation of union of regular languages.

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] J.-C. Birget, Partial orders on words, minimal elements of regular languages, and state complexity, Theoret. Comput. Sci.; J.-C. Birget, Partial orders on words, minimal elements of regular languages, and state complexity, Theoret. Comput. Sci. · Zbl 0786.68071
[2] Chandra, A.; Kozen, D.; Stockmeyer, L., Alternation, J. ACM, 28, 114-133 (1981) · Zbl 0473.68043
[3] Hopcroft, J.; Ullman, J., Introduction to Automata Theory, Languages, and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0426.68001
[4] Leiss, E., Succint representation of regular languages by boolean automata, Theoret. Comput. Sci., 13, 323-330 (1981) · Zbl 0458.68017
[5] Leiss, E., Some comments on a recent note of Ravikumar, SIGACT News, 22, 1, 64 (1991)
[6] Ravikumar, R., Some applications of a technique by Sakoda and Sipser, SIGACT News, 21, 4, 73-77 (1990)
[7] Sakoda, W.; Sipser, M., Non-determinism and the size of two-way automata, Proc. 10th ACM Symp. on Theory of Computing, 275-286 (1978) · Zbl 1282.68160
[8] Yu, S.; Zhuang, Q., On the state complexity of intersection of regular languages, SIGACT News, 22, 3, 52-54 (1991)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.