×
Head, Tom

The topological structure of adherences of regular languages. (English) Zbl 0608.68066

RAIRO, Inf. Théor. Appl. 20, 31-41 (1986).
The topological structure of the adherences of regular languages is considered using zero-dimensional compact metric spaces, studied by R. S. Pierce [Mem. Am. Math. Soc. 130 (1972; Zbl 0253.54028)]. It is shown that the adherence of any regular language L is of such finite type, and from any automaton recognizing L a finite invariant structure, called a structural diagram by the author, is algorithmically constructible. This result implies that homeomorphism of adherences is decidable for regular languages. It is also shown that every zero- dimensional compact metrizable space of finite type is homeomorphic with the adherence of a regular language, where the language can be chosen to be two-testable in the strict sense.
Reviewer: M.Linna

Cited in 4 Documents

MSC:

68Q45 Formal languages and automata
54E45 Compact (locally compact) metric spaces

Keywords:

zero-dimensional compact metric spaces; structural diagram; homeomorphism of adherences

Citations:

Zbl 0253.54028
PDF BibTeX XML Cite
\textit{T. Head}, RAIRO, Inform. Théor. Appl. 20, 31--41 (1986; Zbl 0608.68066)
Full Text: DOI EuDML
  • logo of hbz
  • logo of WorldCat

References:

[1] 1. L. BOASSON and M. NIVAT, Adherences of Languages, Journal of Computer and System Sciences, Vol. 20, 1980, pp. 285-309. Zbl0471.68052 MR584863 · Zbl 0471.68052
[2] 2. T. HEAD, The Adherences of Languages as Topological Spaces, in: Automata on Infinite Wonds, edited by M. Nivat and D. Perrin, LNCS, vol. 192, Springer-Verlag, 1985. Zbl0571.68057 MR814740 · Zbl 0571.68057
[3] 3. J. G. HOCKING and G. S. YOUNG, Topology, Addison-Wesley, Reading, Mass., U.S.A., 1961. Zbl0135.22701 MR125557 · Zbl 0135.22701
[4] 4. R. MCNAUGHTON and S. PAPERT, Counter-Free Automata, M.I.T. Press, Cambridge, Mass., U.S.A., 1971. Zbl0232.94024 MR371538 · Zbl 0232.94024
[5] 5. R. S. PIERCE, Compact zero-dimensional metric spaces of finite type, Memoirs of the Amercan Mathematical Society, No. 130, Providence, Rhode Island, U.S.A., 1972. Zbl0253.54028 MR357268 · Zbl 0253.54028
[6] 6. S. WILLARD, General Topology, Addison-Wesley, Reading, Mass., U.S.A., 1970. Note added in proof: The following are recommended further references. Zbl0205.26601 MR264581 · Zbl 0205.26601
[7] R. LINDNER and L. STAIGER, Algebraische Codierungstheorie - Theorie der sequentiellen Codierungen, Akademie-Verlag, Berlin, 1977. Zbl0363.94016 MR469495 · Zbl 0363.94016
[8] L. STAIGER, Finite-state \omega -languages, J. Comput. System Sci. 27 (1983), pp. 434-448. Zbl0541.68052 MR727390 · Zbl 0541.68052
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.