10.2168/LMCS-10(3:12)2014
Finkel, Olivier
Olivier
Finkel
Ambiguity of {\omega}-Languages of Turing Machines
episciences.org
2014
Computer Science - Logic in Computer Science
Computer Science - Computational Complexity
Mathematics - Logic
contact@episciences.org
episciences.org
2012-10-02T00:00:00+02:00
2016-11-21T15:23:21+01:00
2014-08-28
eng
Journal article
https://lmcs.episciences.org/765
arXiv:1209.5669
1860-5974
PDF
1
Logical Methods in Computer Science ; Volume 10, Issue 3 ; 1860-5974
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 X{\omega} for some finite alphabet X. We investigate here the notion of
ambiguity for recursive {\omega}-languages with regard to acceptance by B\"uchi
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\"uchi 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.