Topology and ambiguity in ω-context free languages

Finkel, Olivier ; Simonnet, Pierre

Bull. Belg. Math. Soc. Simon Stevin, Tome 10 (2003) no. 1, p. 707-722 / Harvested from Project Euclid

Résumé

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üchi pushdown automata have a maximum degree of ambiguity. This result implies that degrees of ambiguity are really not preserved by the operation $W \rightarrow W^\omega$, defined over finitary context free languages. We prove also that taking the adherence or the $\delta$-limit of a finitary language preserves neither ambiguity 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üchi 2-tape automata and we get first results in that direction.

Détail

Publié le : 2003-12-14
Classification:  context free languages,  infinite words,  infinitary rational relations,  ambiguity,  degrees of ambiguity,  topological properties,  borel hierarchy,  analytic sets,  68Q45,  03D05,  03D55,  03E15