Institutul de Matematică şi Informatică "Vladimir Andrunachievici"
Universitatea de Stat din MoldovaRO EN
An Example of Π30-complete Infinitary Rational Relation
Authors: Olivier Finkel
Keywords: Infinitary rational relations; topological properties; Borel hierarchy; Π30-complete set.
– 0.19 Mb
Keywords: Infinitary rational relations; topological properties; Borel hierarchy; Π30-complete set.
Abstract
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.
E-mail:
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.
E-mail:
Fulltext
– 0.19 Mb
Contents
- An Example of Π30-complete Infinitary Rational Relation
- Machine Intelligence Quotient as a Complex Fuzzy Numeral
- Aspect oriented programming and component assembly
- The Pico's formula Generalization
- On Soundness for Time Workflow Nets
- Ordering of jobs with three different processing times in the Mxn Bellman-Johnson problem
- Abstracts of Dr. Hab. Thesis
