On the topological complexity of tree languages

MaRDI QIDQ3086917zbMATH OpenFDO

Authors Jacques Duparc, Filip Murlak, André Arnold, Damian Niwiński

Publication date 30 March 2011

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Descriptive set theory (03E15) Formal languages and automata (68Q45)

Recommendations

• On recognizable tree languages beyond the Borel hierarchy
• An upper bound on the complexity of recognizable tree languages
• On the Topological Complexity of Weakly Recognizable Tree Languages
• Deciding the topological complexity of Büchi languages
• Complexity of topological properties of regular \(\omega\)-languages

Cited in

(11)

• Tree adjoining languages and multipushdown languages
• Wadge-Wagner hierarchies
• Infinite games specified by 2-tape automata
• The Non-deterministic Mostowski Hierarchy and Distance-Parity Automata
• On the syntactic complexity of tree series
• The topological structure of adherences of regular languages
• Deciding the topological complexity of Büchi languages
• Polishness of some topologies related to word or tree automata
• An upper bound on the complexity of recognizable tree languages
• From Muller to parity and Rabin qutomata: optimal transformations preserving (history) determinism
• Tree-based language complexity of Thompson's group \(F\).

This page was built for publication: On the topological complexity of tree languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3086917)