×
Jirásek, Jozef; Jirásková, Galina

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

Theor. Comput. Sci. 578, 42-57 (2015).
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)

Cited in 1 Document

MSC:

68Q45 Formal languages and automata

Keywords:

regular language; boundary; deterministic finite automaton; state complexity
PDF BibTeX XML Cite
\textit{J. Jirásek} and \textit{G. Jirásková}, Theor. Comput. Sci. 578, 42--57 (2015; Zbl 1317.68098)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[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, LNCS, vol. 7410, (2012), 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) · JFM 48.0210.04
[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
[10] J. Shallit, State complexity of \((\overline{L^\ast})^\ast\) and \(L^\ast \cap(\overline{L})^\ast\), Personal communication, 2010.
[11] Sipser, M., Introduction to the theory of computation, (1997), PWS Publishing Company Boston · Zbl 1169.68300
[12] Yu, S., Regular languages, (Rozenberg, G.; Salomaa, A., Handbook of Formal Languages, vol. I, (1997), Springer Heidelberg), 41-110, Ch. 2
[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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.