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)
|
Keywords | automata 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
|
Eingabedatum | 24. Februar 2011 |
---|