Search


Volume

Author

Year

  • < Previous
  • 1
  • Next >
2 results

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;]
Published on December 21, 2009
Volume 5, Issue 4

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.
Published on May 8, 2019
Volume 15, Issue 2
  • < Previous
  • 1
  • Next >