Computer Science – Formal Languages and Automata Theory
Scientific paper
2011-02-24
Computer Science
Formal Languages and Automata Theory
Scientific paper
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.
Kufleitner Manfred
Lauser Alexander
No associations
LandOfFree
Cantor Topologies for Finite Words does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Cantor Topologies for Finite Words, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cantor Topologies for Finite Words will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-86857