Technischer Bericht TR-2011-02

Bibliograph.
Daten
Kufleitner, Manfred; Lauser, Alexander: Cantor Topologies for Finite Words.
Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Technischer Bericht Informatik Nr. 2011/02.
15 Seiten, englisch.
CR-Klassif.F.1.1 (Models of Computation)
F.4.3 (Formal Languages)
Keywordsautomata theory; finite semigroups; Cantor topology; regular languages
Kurzfassung

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.

Volltext und
andere Links
PDF (410410 Bytes)
Abteilung(en)Universität Stuttgart, Institut für Formale Methoden der Informatik, Theoretische Informatik
Eingabedatum24. Februar 2011
   Publ. Institut   Publ. Informatik