The Complexity of Infinite Computations In Models of Set Theory

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 b...

Popoln opis

Bibliografske podrobnosti

Glavni avtor:	Olivier Finkel
Format:	Artigo
Jezik:	Inglês
Izdano:	Logical Methods in Computer Science e.V. 2009-12-01
Serija:	Logical Methods in Computer Science
Teme:	computer science - logic in computer science computer science - computational complexity mathematics - logic f.1.1 f.1.3 f.4.1 f.4.3
Online dostop:	https://lmcs.episciences.org/1205/pdf
Oznake:	Označite Brez oznak, prvi označite!