An Example of Pi^0_3-complete Infinitary Rational Relation

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We give in this paper an example of infinitary rational relation, accepted by a 2-tape Büchi automaton, which is Pi^0_3-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.

Keywords

Logic, Computational Complexity, Logic in Computer Science

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/123802

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0702334
 http://arxiv.org/abs/math/0702334

Collections

arXiv