Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 0608.68066
Head, Tom
The topological structure of adherences of regular languages. (English)
[J] RAIRO, Inf. Théor. Appl. 20, 31-41 (1986). ISSN 0988-3754

The topological structure of the adherences of regular languages is considered using zero-dimensional compact metric spaces, studied by {\it 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.
[M.Linna]

MSC 2000:: *68Q45 Formal languages
54E45 Compactness in metric spaces

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

Citations: Zbl 0253.54028

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]