Search

• < Previous
• 1
• Next >

---

The Complexity of Infinite Computations In Models of Set Theory

Olivier Finkel.

We prove the following surprising result: there exist a 1-counter B\"uchi automaton and a 2-tape B\"uchi automaton such that the \omega-language of the first and the infinitary rational relation of the second in one model of ZFC are \pi_2^0-sets, while in a different model of ZFC both are analytic&nbsp;[&hellip;]

---

Polishness of some topologies related to word or tree automata

Olivier Finkel ; Olivier Carton ; Dominique Lecomte.

We prove that the B\"uchi topology and the automatic topology are Polish. We also show that this cannot be fully extended to the case of a space of infinite labelled binary trees; in particular the B\"uchi and the Muller topologies are not Polish in this case.

---

Ambiguity of {\omega}-Languages of Turing Machines

Olivier Finkel.

An {\omega}-language is a set of infinite words over a finite alphabet X. We consider the class of recursive {\omega}-languages, i.e. the class of {\omega}-languages accepted by Turing machines with a B\"uchi acceptance condition, which is also the class {\Sigma}11 of (effective) analytic subsets of&nbsp;[&hellip;]

---