Technical Report TR-2011-02

BibliographyKufleitner, Manfred; Lauser, Alexander: Cantor Topologies for Finite Words.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Technical Report Computer Science No. 2011/02.
15 pages, english.
CR-SchemaF.1.1 (Models of Computation)
F.4.3 (Formal Languages)
Keywordsautomata theory; finite semigroups; Cantor topology; regular languages
Abstract

We consider the Cantor topology over finite words, which is obtained by resembling the well-known Cantor topology over infinite words. We consider two automata models: Complete flip automata recognize exactly the class of regular open sets, and deterministic weak automata are expressively complete for the class of regular Boolean combinations of open sets. These automata models yield decidability of the membership problem. In addition, we obtain simple and effective algebraic characterizations for regular open languages and for regular Boolean combinations of open sets. The algebraic characterizations admit counterparts for the left-right dual and the two-sided version of the Cantor topology over finite words.

As an application, we consider Boolean combinations of open sets which are recognizable by monoids in the variety DA. As it turns out, several characterizations of DA-languages admit natural restrictions for this subclass.

Full text and
other links
PDF (410410 Bytes)
Department(s)University of Stuttgart, Institute of Formal Methods in Computer Science, Theoretical Computer Science
Entry dateFebruary 24, 2011
   Publ. Computer Science