One-Dimensional Logic over Trees

DOI10.4230/LIPICS.MFCS.2017.64MaRDI QIDQ5111281zbMATHOpenAlexFDO

Authors Emanuel Kieroński, Antti Kuusisto

Publication date 26 May 2020

Full work available at URL https://dblp.uni-trier.de/db/conf/mfcs/mfcs2017.html#KieronskiK17

zbMATH Keywords

treessatisfiabilityexpressivityfragments of first-order logic

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Subsystems of classical logic (including intuitionistic logic) (03B20) Computational aspects of satisfiability (68R07)

Recommendations

• One-dimensional logic over words
• Extending two-variable logic on trees
• Complexity and expressivity of uniform one-dimensional fragment with equality
• One-dimensional fragment of first-order logic
• Uniform one-dimensional fragments with one equivalence relation

Cites work

• scientific article; zbMATH DE number 803291 (Why is no real title available?)
• Alternation
• Complexity and expressivity of uniform one-dimensional fragment with equality
• Complexity of two-variable logic on finite trees
• Database Theory - ICDT 2005
• Decidability of weak logics with deterministic transitive closure
• Extending two-variable logic on trees
• First-order logic with two variables and unary temporal logic
• On the complexity of the two-variable guarded fragment with transitive guards
• One-dimensional fragment of first-order logic
• One-dimensional logic over words
• Two-variable logic with a between relation
• Two-variable logic with counting and a linear order
• Unary negation
• Uniform one-dimensional fragments with one equivalence relation

Cited in

(8)

• Uniform guarded fragments
• One-dimensional fragment of first-order logic
• Complexity and expressivity of uniform one-dimensional fragment with equality
• One-dimensional fragment over words and trees
• First-order logic on finite trees
• One-dimensional logic over words
• Uniform one-dimensional fragments with one equivalence relation
• One-and-a-halfth-order Logic

This page was built for publication: One-Dimensional Logic over Trees

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