|
Organizers |
\omega-Languages and the Borel Hierarchy in Cantor Space
by
Ludwig Staiger
Martin-Luther-Universität
The present talk intends to show the
usefulness of topological methods in particular in that part of Computer
Science where nonterminating computations are studied. Here the fundamentals
were established in the sixties by the work of Büchi ,
Trakhtenbrot , McNaughton and Rabin who
investigated the behaviour of automata on infinite sequences. From the very
beginning topological considerations in the space of infinite sequences
X\omega over a finite alphabet X (the so-called Cantor space)
played a crucial rôle (see the book and the survey papers
). We focus on the following five topics.
1. Acceptance and topology
In this part we show that acceptance conditions for computational devices
(like finite automata, push-down automata, Turing machines or the so-called
X-automata of ) reflect topological properties. In particular,
acceptance conditions for deterministic automata reveal strong correspondences
to low level Borel classes in Cantor space (see ).
2. Computability, measure and category
Here we connect (non-)computability constraints of infinite sequences like
Borel normality, randomness etc. to measure and Baire category properties of
sets of sequences (so-called \omega-languages) defined by the above
mentioned computational devices.
3. Refinements of the Borel hierarchy: Wadge
and Wagner hierarchy
Using reducibility notions known from recursion theory, Wadge in his thesis
investigated a very subtle refinement of the Borel hierarchy. His
refinement is based on the following continuous reducibility in Cantor space:
F <= w E iff there is a continuous mapping \Phi:X\omega --> X\omega such that F=\Phi-1(E).
Wagner in obtained a full description of Wadge's hierarchy restricted to the family of \omega-languages definable by finite automata.
We review briefly basic concepts and present some new developments in this
direction (see ).
4. Arithmetical operators and Duparc's
backspace operation
Arithmetical operators are closely connected to the Arithmetical hierarchy of
\omega-languages which is a subhierarchy of the Borel hierarchy, albeit its
classes are defined by recursion theoretic means. So, unlike the case of
simpler automata types, the classes of the Arithmetical hierarchy are not
restrictions of Borel classes to the subfamily of \omega-languages defined
by Turing machines (say). In this part of the talk we show a connection
between Duparc's recent backspace operation, fundamental
for the investigation of the Wadge hierarchy, and Wagner's Arithmetical
operators (see ).
5. Topological complexity of regular
\omega-languages, context-free \omega-languages and \omega-power
languages
In this last part we review several results showing the influence of the
computational device defining an \omega-language and the Borel complexity of
this \omega-language. For deterministic devices we obtain some low upper
bounds in the Borel hierarchy (see ), whereas for
nondeterministic push-down automata the Borel complexity of the defined
\omega-languages is unbounded .
We also show that some measure-category-coincidence results for \omega-languages defined by finite automata (see ) are no longer true if we extend the computational power of the defining devices a little bit.
Date received: June 27, 2002
Copyright © 2002 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cait-66.