Do you want to publish a course? Click here

Topological Complexity of omega-Powers : Extended Abstract

152   0   0.0 ( 0 )
 Added by Olivier Finkel
 Publication date 2008
and research's language is English




Ask ChatGPT about the research

This is an extended abstract presenting new results on the topological complexity of omega-powers (which are included in a paper Classical and effective descriptive complexities of omega-powers available from arXiv:0708.4176) and reflecting also some open questions which were discussed during the Dagstuhl seminar on Topological and Game-Theoretic Aspects of Infinite Computations 29.06.08 - 04.07.08.



rate research

Read More

218 - Olivier Finkel 2013
We survey recent results on the topological complexity of context-free omega-languages which form the second level of the Chomsky hierarchy of languages of infinite words. In particular, we consider the Borel hierarchy and the Wadge hierarchy of non-deterministic or deterministic context-free omega-languages. We study also decision problems, the links with the notions of ambiguity and of degrees of ambiguity, and the special case of omega-powers.
We show that there are $Sigma_3^0$-complete languages of infinite words accepted by non-deterministic Petri nets with Buchi acceptance condition, or equivalently by Buchi blind counter automata. This shows that omega-languages accepted by non-deterministic Petri nets are topologically more complex than those accepted by deterministic Petri nets.
159 - Olivier Finkel 2012
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 Buchi 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 Buchi 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 Buchi 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.
259 - Olivier Finkel 2020
The $omega$-power of a finitary language L over a finite alphabet $Sigma$ is the language of infinite words over $Sigma$ defined by L $infty$ := {w 0 w 1. .. $in$ $Sigma$ $omega$ | $forall$i $in$ $omega$ w i $in$ L}. The $omega$-powers appear very naturally in Theoretical Computer Science in the characterization of several classes of languages of infinite words accepted by various kinds of automata, like B{u}chi automata or B{u}chi pushdown automata. We survey some recent results about the links relating Descriptive Set Theory and $omega$-powers.
131 - Zhaohua Luo 2010
An abstract machine is a theoretical model designed to perform a rigorous study of computation. Such a model usually consists of configurations, instructions, programs, inputs and outputs for the machine. In this paper we formalize these notions as a very simple algebraic system, called a configuration machine. If an abstract machine is defined as a configuration machine consisting of primitive recursive functions then the functions computed by the machine are always recursive. The theory of configuration machines provides a useful tool to study universal machines.
comments
Fetching comments Fetching comments
Sign in to be able to follow your search criteria
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا