Computer Science – Logic in Computer Science
Scientific paper
2008-01-03
Bulletin of the Belgian Mathematical Society 10 (5) (2003) 707-722
Computer Science
Logic in Computer Science
Scientific paper
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 B\"uchi 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 B\"uchi 2-tape automata and we get first results in that direction.
Finkel Olivier
Simonnet Pierre
No associations
LandOfFree
Topology and Ambiguity in Omega Context Free Languages does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Topology and Ambiguity in Omega Context Free Languages, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Topology and Ambiguity in Omega Context Free Languages will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-611252