On the computational complexity of the theory of complete binary trees

MaRDI QIDQ3614383zbMATH OpenFDO

Authors Zhimin Li, Libo Luo, Li Xiang

Publication date 6 March 2009

zbMATH Keywords

bounded Ehrenfeucht-Fraïssé gamecomplete binary treeupper bounds for computational complexity

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Quantifier elimination, model completeness, and related topics (03C10) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• scientific article; zbMATH DE number 30615
• scientific article; zbMATH DE number 1894708
• An improved lower bound for the elementary theories of trees
• scientific article; zbMATH DE number 5171238
• \(\Sigma_ 1^ 1\)-completeness of a fragment of the theory of trees with subtree relation

Cited in

(14)

• \(\Sigma_ 1^ 1\)-completeness of a fragment of the theory of trees with subtree relation
• Computational complexity of theories of a binary predicate with a small number of variables
• scientific article; zbMATH DE number 1696443 (Why is no real title available?)
• scientific article; zbMATH DE number 5373718 (Why is no real title available?)
• scientific article; zbMATH DE number 30615 (Why is no real title available?)
• Decidability and complexity of tree share formulas
• An improved lower bound for the elementary theories of trees
• scientific article; zbMATH DE number 1894708 (Why is no real title available?)
• scientific article; zbMATH DE number 895329 (Why is no real title available?)
• scientific article; zbMATH DE number 1389856 (Why is no real title available?)
• scientific article; zbMATH DE number 5171238 (Why is no real title available?)
• The first-order theory of ground tree rewrite graphs
• On the bounded theories of finite trees
• On the complexity of computing treelength

This page was built for publication: On the computational complexity of the theory of complete binary trees

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