First-order logic on finite trees

DOI10.1007/3-540-59293-8_191zbMath1496.68178OpenAlexW1549978238MaRDI QIDQ5096727

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

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

Related Items

A note on the characterization of TL [EF] ⋮ Aperiodicity, Star-freeness, and First-order Logic Definability of Operator Precedence Languages ⋮ Algebraic recognizability of regular tree languages ⋮ Characterizing EF and EX tree logics ⋮ Automata on finite trees ⋮ On labeled birooted tree languages: algebras, automata and logic

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Modulo-counting quantifiers over finite trees
• Tree acceptors and some of their applications
• An application of games to the completeness problem for formalized theories
• First-order properties of trees, star-free expressions, and aperiodicity
• Bottom-up and top-down tree transformations— a comparison
• Application of model theoretic games to discrete linear orders and finite automata
• On the Ehrenfeucht-Fraïssé game in theoretical computer science
• On finite monoids having only trivial subgroups
• Generalized finite automata theory with an application to a decision problem of second-order logic

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