Transforming structures by set interpretations

DOI10.2168/LMCS-3(2:4)2007MaRDI QIDQ5310689zbMATH OpenFDO

Authors Thomas Colcombet, Christof Löding

Publication date 11 October 2007

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2168/LMCS-3(2:4)2007

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Computable structure theory, computable model theory (03C57) Automata and formal grammars in connection with logical questions (03D05)

Recommendations

• Finite presentations of infinite structures: Automata and interpretations
• Regular sets over extended tree structures
• Semantics of trees
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Monadic second-order logic on tree-like structures

Cited in

(18)

• Second-order finite automata
• Constructing decidable graphs from decidable structures
• Rewriting higher-order stack trees
• Tree-automatic scattered linear orders
• The Caucal hierarchy: interpretations in the (W)MSO+\(\mathsf{U}\) logic
• Interpretations in trees with countably many branches
• Simple monadic theories and partition width
• Rewriting higher-order stack trees
• When Is Reachability Intrinsically Decidable?
• Cardinality Quantifiers in MLO over Trees
• scientific article; zbMATH DE number 2086419 (Why is no real title available?)
• On the complexity of infinite advice strings
• Uniformly Automatic Classes of Finite Structures
• Monadic decomposability of regular relations
• Regular model checking revisited
• Synthesizing nested relational queries from implicit specifications: via model theory and via proof theory
• Simple classes of automatic structures
• Lexicographic transductions of finite words

This page was built for publication: Transforming structures by set interpretations

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