On the boundary of regular languages. (English) Zbl 1317.68098

This paper considers the computation of the boundary of a regular language, defined as the intersection of the Kleene star of this language with the Kleene star of its complement. The precise state complexity of the boundary of a regular language is found. The upper bound is obtained by counting unreachable states in the automaton produced using standard constructions for Kleene star and intersection, and it is proved that this upper bound can be reached by automata over a five-letter alphabet. A precise bound in the case of a four-letter alphabet and asymptotic bounds for two- and three-letter alphabets are also provided.
Reviewer: Michal Kunc (Brno)


68Q45 Formal languages and automata
Full Text: DOI


[1] Brzozowski, J. A.; Grant, E.; Shallit, J., Closures in formal languages and Kuratowski’s theorem, Internat. J. Found. Comput. Sci., 22, 301-321 (2011) · Zbl 1246.68139
[2] Fife, J. H., The Kuratowski closure-complement problem, Math. Mag., 64, 180-182 (1991) · Zbl 0735.54001
[3] Jirásková, G.; Shallit, J., The state complexity of star-complement-star, (Yen, H.-C.; Ibarra, O. H., DLT 2012. DLT 2012, LNCS, vol. 7410 (2012), Springer: Springer Heidelberg), 380-391 · Zbl 1370.68178
[4] Konstantinidis, S., Conference on Implementation and Application of Automata, LNCS, vol. 7982, 208-219 (2013)
[5] Kuratowski, C., Sur l’opération \(\overline{A}\) de l’analysis situs, Fund. Math., 3, 182-199 (1922)
[6] Maslov, A. N., Estimates of the number of states of finite automata, Sov. Math., Dokl., 11, 1373-1375 (1970) · Zbl 0222.94064
[7] Rabin, M.; Scott, D., Finite automata and their decision problems, IBM J. Res. Develop., 3, 114-129 (1959) · Zbl 0158.25404
[8] Salomaa, A.; Salomaa, K.; Yu, S., State complexity of combined operations, Theoret. Comput. Sci., 383, 140-152 (2007) · Zbl 1124.68056
[9] Shallit, J., Open problems in automata theory and formal languages
[11] Sipser, M., Introduction to the Theory of Computation (1997), PWS Publishing Company: PWS Publishing Company Boston · Zbl 1169.68300
[12] Yu, S., Regular languages, (Rozenberg, G.; Salomaa, A., Handbook of Formal Languages, vol. I (1997), Springer: Springer Heidelberg), 41-110, Ch. 2 · Zbl 0866.68057
[13] Yu, S.; Zhuang, Q.; Salomaa, K., The state complexity of some basic operations on regular languages, Theoret. Comput. Sci., 125, 315-328 (1994) · Zbl 0795.68112
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.