Finkel, Olivier - Ambiguity of {ømega}-Languages of Turing Machines

lmcs:765 - Logical Methods in Computer Science, August 28, 2014, Volume 10, Issue 3
Ambiguity of {ømega}-Languages of Turing Machines

Authors: Finkel, Olivier

An {ømega}-language is a set of infinite words over a finite alphabet X. We consider the class of recursive {ømega}-languages, i.e. the class of {ømega}-languages accepted by Turing machines with a B\"uchi acceptance condition, which is also the class {\Sigma}11 of (effective) analytic subsets of X{ømega} for some finite alphabet X. We investigate here the notion of ambiguity for recursive {ømega}-languages with regard to acceptance by B\"uchi Turing machines. We first present in detail essentials on the literature on {ømega}-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 {ømega}-languages they accept. To obtain our new results, we make use of results and methods of effective descriptive set theory.


Source : oai:arXiv.org:1209.5669
DOI : 10.2168/LMCS-10(3:12)2014
Volume: Volume 10, Issue 3
Published on: August 28, 2014
Submitted on: June 25, 2015
Keywords: Computer Science - Logic in Computer Science,Computer Science - Computational Complexity,Mathematics - Logic


Share

Browsing statistics

This page has been seen 52 times.
This article's PDF has been downloaded 7 times.