[hal-00735050] Ambiguity of $\omega$-Languages of Turing Machines

An omega-language is a set of infinite words over a finite alphabet X We consider the class of recursive $\omega$-languages ie the class of $\omega$-languages accepted by Turing machines with a Büchi acceptance condition which is also the class $\Sigma1^1$ of effective analytic subsets of $X^\omega$ for some finite alphabet X We investigate here the notion of ambiguity for recursive $\omega$-languages with regard to acceptance by Büchi Turing machines We first present in detail essentials on the literature on $\omega$-languages accepted by Turing Machines Then we give a complete and broad view on the notion of ambiguity and unambiguity of Büchi Turing machines and of the omega-languages they accept To obtain our new results we make use of results and methods of effective descriptive set theory



from HAL : Dernières publications http://ift.tt/1uJ8Dep