Regular sets over extended tree structures

DOI10.1016/J.TCS.2011.10.020zbMATH Open1244.68047OpenAlexW2044917901MaRDI QIDQ764339FDOQ764339

Séverine Fratani

Publication date: 13 March 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.10.020

Recommendations

• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• scientific article; zbMATH DE number 2087432
• An Extension of Muchnik's Theorem
• Monadic second-order logic on tree-like structures
• STACS 2005

zbMATH Keywords

automata with oracleiterated pushdown structureslabeled tree structuresMSO-definable sets

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The monadic theory of morphic infinite words and generalizations
• Mathematical Foundations of Computer Science 2003
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Monadic second-order logic on tree-like structures
• Fundamental properties of infinite trees
• Iterated stack automata and complexity classes
• An automata-theoretical characterization of the OI-hierarchy
• Uniformization and skolem functions in the class of trees
• Title not available (Why is that?)
• Nested Stack Automata
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the Borel Complexity of MSO Definable Sets of Branches
• Iterated pushdown automata and sequences of rational numbers
• Solving Sequential Conditions by Finite-State Strategies
• Full AFLs and nested iterated substitution
• Counter-free automata, first-order logic, and star-free expressions extended by prefix oracles
• A Note on Pushdown Store Automata and Regular Systems
• On decidability of monadic logic of order over the naturals extended by monadic predicates
• Uniformization, choice functions and well orders in the class of trees
• Title not available (Why is that?)
• FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
• On infinite transition graphs having a decidable monadic theory
• Selection in the monadic theory of a countable ordinal
• Selection over classes of ordinals expanded by monadic predicates
• The monadic second-order logic of graphs. IX: Machines and their behaviours
• Title not available (Why is that?)
• Linear Orders in the Pushdown Hierarchy
• Monadic second-order logic, graph coverings and unfoldings of transition systems
• Parametrized Regular Infinite Games and Higher-Order Pushdown Strategies
• Positional Strategies for Higher-Order Pushdown Parity Games
• Title not available (Why is that?)
• Selection and Uniformization Problems in the Monadic Theory of Ordinals: A Survey
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Mathematical Foundations of Computer Science 2005
• Symbolic Backwards-Reachability Analysis for Higher-Order Pushdown Systems

Cited In (5)

• Transforming structures by set interpretations
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Title not available (Why is that?)
• Measure properties of regular sets of trees
• Counter-free automata, first-order logic, and star-free expressions extended by prefix oracles

This page was built for publication: Regular sets over extended tree structures

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