Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTopology and Ambiguity in Omega Context Free Languages
238
0
0.0
(
0
)
Added by
Olivier Finkel
Publication date
2008
fields
Informatics Engineering
and research's language is
English
Authors
Olivier Finkel
Ask ChatGPT about the research
No Arabic abstract
We study the links between the topological complexity of an omega context free language and its degree of ambiguity. In particular, using known facts from classical descriptive set theory, we prove that non Borel omega context free languages which are recognized by Buchi pushdown automata have a maximum degree of ambiguity. This result implies that degrees of ambiguity are really not preserved by the operation of taking the omega power of a finitary context free language. We prove also that taking the adherence or the delta-limit of a finitary language preserves neither unambiguity nor inherent ambiguity. On the other side we show that methods used in the study of omega context free languages can also be applied to study the notion of ambiguity in infinitary rational relations accepted by Buchi 2-tape automata and we get first results in that direction.
rate research
Read More
We show that, from a topological point of view, considering the Borel and the Wadge hierarchies, 1-counter Buchi automata have the same accepting power than Turing machines equipped with a Buchi acceptance condition. In particular, for every non null recursive ordinal alpha, there exist some Sigma^0_alpha-complete and some Pi^0_alpha-complete omega context free languages accepted by 1-counter Buchi automata, and the supremum of the set of Borel ranks of context free omega languages is the ordinal gamma^1_2 which is strictly greater than the first non recursive ordinal. This very surprising result gives answers to questions of H. Lescow and W. Thomas [Logical Specifications of Infinite Computations, In:A Decade of Concurrency, LNCS 803, Springer, 1994, p. 583-621].
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.
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.
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.
Locally finite omega languages were introduced by Ressayre in [Journal of Symbolic Logic, Volume 53, No. 4, p.1009-1026]. They generalize omega languages accepted by finite automata or defined by monadic second order sentences. We study here closure properties of the family LOC_omega of locally finite omega languages. In particular we show that the class LOC_omega is neither closed under intersection nor under complementation, giving an answer to a question of Ressayre.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
