文章基本信息

标题：Ambiguity of Ï-Languages of Turing Machines
本地全文：下载
作者：Olivier Finkel
期刊名称：Logical Methods in Computer Science
印刷版ISSN：1860-5974
电子版ISSN：1860-5974
出版年度：2014
卷号：10
期号：3
页码：1
DOI：10.2168/LMCS-10(3:12)2014
出版社：Technical University of Braunschweig
摘要：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.
其他关键词：Automata and formal languages; infinite words; Turing machines; B¨uchi transition systems; ambiguity; degrees of ambiguity; logic in computer science; effective descriptive set theory; models of set theory.