First-order logic on finite trees

DOI10.1007/3-540-59293-8_191MaRDI QIDQ5096727zbMATH OpenOpenAlexFDO

Authors Andreas Potthoff

Publication date 18 August 2022

Published in TAPSOFT '95: Theory and Practice of Software Development (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-59293-8_191

Mathematics Subject Classification ID

Classical first-order logic (03B10) Basic properties of first-order languages and structures (03C07) Automata and formal grammars in connection with logical questions (03D05) Formal languages and automata (68Q45)

Recommendations

• First-order logic on higher-order nested pushdown trees
• Extension of First-Order Theories into Trees
• Finite tree property for first-order logic with identity and functions
• Order-Invariant First-Order Logic over Hollow Trees
• First-order theories of bounded trees
• A first-order axiomatization of the theory of finite trees
• Logics and Automata for Totally Ordered Trees
• One-Dimensional Logic over Trees
• scientific article; zbMATH DE number 638619
• Rules and Refutation Rules for the Logic of Finite n-ary Trees

Cites work

• An application of games to the completeness problem for formalized theories
• Application of model theoretic games to discrete linear orders and finite automata
• Bottom-up and top-down tree transformations— a comparison
• First-order properties of trees, star-free expressions, and aperiodicity
• Generalized finite automata theory with an application to a decision problem of second-order logic
• scientific article; zbMATH DE number 3885853 (Why is no real title available?)
• scientific article; zbMATH DE number 3854429 (Why is no real title available?)
• scientific article; zbMATH DE number 3855013 (Why is no real title available?)
• scientific article; zbMATH DE number 475413 (Why is no real title available?)
• scientific article; zbMATH DE number 522865 (Why is no real title available?)
• scientific article; zbMATH DE number 194781 (Why is no real title available?)
• scientific article; zbMATH DE number 3368555 (Why is no real title available?)
• Modulo-counting quantifiers over finite trees
• On finite monoids having only trivial subgroups
• On the Ehrenfeucht-Fraïssé game in theoretical computer science (extended abstract)
• Tree acceptors and some of their applications

Cited in

(22)

• Finite trees in tense logic
• Modulo-counting quantifiers over finite trees
• Deciding the first-order theory of an algebra of feature trees with updates
• Tree canonization and transitive closure
• Automata on finite trees
• First-order theories of bounded trees
• On labeled birooted tree languages: algebras, automata and logic
• Algebraic recognizability of regular tree languages
• Characterizing EF and EX tree logics
• Regular tree languages, cardinality predicates, and addition-invariant FO
• Regular tree languages definable in FO and in FO\(_{\mathrm{mod}}\)
• First-order definable languages
• scientific article; zbMATH DE number 638619 (Why is no real title available?)
• Star-free picture expressions are strictly weaker than first-order logic
• First-order aspects of tree paths
• First-Order Logic on CPDA Graphs
• scientific article; zbMATH DE number 2206362 (Why is no real title available?)
• STACS 2005
• On n-equivalence of binary trees
• Aperiodicity, Star-freeness, and First-order Logic Definability of Operator Precedence Languages
• First-order logics: some characterizations and closure properties
• A note on the characterization of TL [EF]

This page was built for publication: First-order logic on finite trees

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