Olivier Finkel - Ambiguity of {\omega}-Languages of Turing Machines

lmcs:765 - Logical Methods in Computer Science, August 28, 2014, Volume 10, Issue 3 - https://doi.org/10.2168/LMCS-10(3:12)2014
Ambiguity of {\omega}-Languages of Turing Machines

Authors: Olivier Finkel

    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üchi 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ü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.


    Volume: Volume 10, Issue 3
    Published on: August 28, 2014
    Accepted on: June 25, 2015
    Submitted on: October 2, 2012
    Keywords: Computer Science - Logic in Computer Science,Computer Science - Computational Complexity,Mathematics - Logic

    Linked data

    Source : ScholeXplorer HasVersion DOI 10.48550/arxiv.1209.5669
    • 10.48550/arxiv.1209.5669
    Ambiguity of ��-Languages of Turing Machines
    Finkel, Olivier ;

    3 Documents citing this article

    Share

    Consultation statistics

    This page has been seen 1196 times.
    This article's PDF has been downloaded 355 times.