Logics and Automata for Totally Ordered Trees

DOI10.1007/978-3-540-70590-1_15MaRDI QIDQ3522020zbMATH OpenOpenAlexFDO

Authors Marco Kuhlmann, Joachim Niehren

Publication date 28 August 2008

Published in Rewriting Techniques and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-70590-1_15

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25)

Recommendations

• Term Rewriting and Applications
• An automata model for trees with ordered data values
• Complete axiomatizations of fragments of monadic second-order logic on finite trees
• Extending two-variable logic on data trees with order on data values and its automata
• Complete Axiomatizations of MSO, FO(TC 1 ) and FO(LFP 1 ) on Finite Trees

Cites work

• scientific article; zbMATH DE number 1665452 (Why is no real title available?)
• scientific article; zbMATH DE number 475416 (Why is no real title available?)
• Algebraic automata and context-free sets
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Generalized finite automata theory with an application to a decision problem of second-order logic
• Graph Structure and Monadic Second-Order Logic: Language Theoretical Aspects
• Handbook of Graph Grammars and Computing by Graph Transformation
• Monadic Datalog and the expressive power of languages for web information extraction
• Rewriting Techniques and Applications

Cited in

(6)

• First-order logic on finite trees
• An Automata Theoretic Approach to Rational Tree Relations
• Characterization of Logics over Ranked Tree Languages
• PDL for ordered trees
• Logics for Unordered Trees with Data Constraints on Siblings
• Hybrid tree automata and the yield theorem for constituent tree automata

This page was built for publication: Logics and Automata for Totally Ordered Trees

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