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

Abstract : 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.
Complete list of metadatas

Cited literature [25 references]  Display  Hide  Download

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00130246
Contributor : Olivier Finkel <>
Submitted on : Monday, February 12, 2007 - 2:56:48 PM
Last modification on : Tuesday, April 24, 2018 - 1:52:56 PM
Long-term archiving on : Wednesday, April 7, 2010 - 2:45:49 AM

Files

PI-0-3-RAT-REL.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Olivier Finkel. An Example of Pi^0_3-complete Infinitary Rational Relation. Computer Science Journal of Moldova, 2007, 15 (1), pp.3-21. ⟨ensl-00130246⟩

Share

Metrics

Record views

174

Files downloads

85