Topology and Ambiguity in Omega Context Free Languages
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 Büchi 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üchi 2-tape automata and we get first results in that direction.
Read the paper
Related studies
- eggNOG 5.0: a hierarchical, functionally and phylogenetically annotated orthology resource based on 5090 organisms and 2502 viruses
- Online Survival Analysis Software to Assess the Prognostic Value of Biomarkers Using Transcriptomic Data in Non-Small-Cell Lung Cancer
- OptiType: precision HLA typing from next-generation sequencing data
- Nicotinic Cholinergic System and COVID-19: In Silico Identification of an Interaction between SARS-CoV-2 and Nicotinic Receptors with Potential Therapeutic Targeting Implications
- Saccharomyces cerevisiae cells have three Omega class glutathione S-transferases acting as 1-Cys thiol transferases
- Hemolysis at low blood flow rates: in-vitro and in-silico evaluation of a centrifugal blood pump
Go deeper in Evidence Hub
Evidence Hub adds a study data sheet (design, sample size, evidence level, key numbers), an AI summary and a chat grounded in the paper's text.