IMI/Publicaţii/CSJM/Ediţii/CSJM v.15, n.1 (43), 2007/

An Example of Π30-complete Infinitary Rational Relation

Authors: Olivier Finkel
Keywords: Infinitary rational relations; topological properties; Borel hierarchy; Π30-complete set.


We give in this paper an example of infinitary rational relation, accepted by a 2-tape Buchi automaton, which is Π30-complete in the Borel hierarchy. Moreover the example of infinitary rational relation given in this paper has a very simple structure and can be easily described by its sections.

Olivier Finkel
Equipe Modeles de Calcul et Complexite
Laboratoire de l'Informatique du Parallelisme
CNRS et Ecole Normale Superieure de Lyon
46, Allee d'Italie 69364 Lyon Cedex 07, France.


Adobe PDF document0.19 Mb