Determining the consistency of partial tree descriptions

DOI10.1016/J.ARTINT.2006.12.004MaRDI QIDQ1028903zbMATH OpenOpenAlexFDO

Authors Manuel Bodirsky, Martin Kuetz

Publication date 9 July 2009

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.artint.2006.12.004

zbMATH Keywords

constraint satisfaction problemsgraph algorithmsleft-linear point algebratree descriptions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Problems related to evolution (92D15)

Recommendations

• scientific article; zbMATH DE number 1444316
• Tree reconstruction from partial orders
• scientific article; zbMATH DE number 2086393
• scientific article; zbMATH DE number 910861
• Computing the Local Consensus of Trees

Cites work

• A first-order axiomatization of the theory of finite trees
• A Sufficient Condition for Backtrack-Free Search
• Algorithms on Strings, Trees and Sequences
• Classifying the Complexity of Constraints Using Finite Algebras
• Computer Science Logic
• Constraint Satisfaction with Countable Homogeneous Templates
• Expressive power and complexity in algebraic logic
• scientific article; zbMATH DE number 3857387 (Why is no real title available?)
• scientific article; zbMATH DE number 44603 (Why is no real title available?)
• scientific article; zbMATH DE number 2086393 (Why is no real title available?)
• Local and global relational consistency
• Maintaining knowledge about temporal intervals
• Reasoning about temporal relations
• Reasoning about temporal relations, the tractable subalgebras of Allen's interval algebra
• Relation algebras and their application in temporal and spatial reasoning
• The complexity of constraint satisfaction: an algebraic approach
• The complexity of reconstructing trees from qualitative characters and subtrees
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The constraint language for lambda structures
• The difficulty of constructing a leaf-labelled tree including or avoiding given subtrees

Cited in

(7)

• Combining tree partitioning, precedence, and incomparability constraints
• Trees in trees: is the incomplete information about a tree consistent?
• scientific article; zbMATH DE number 1444316 (Why is no real title available?)
• Hardness of Network Satisfaction for Relation Algebras with Normal Representations
• Constraint Satisfaction Problems with Infinite Templates
• The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom
• Identifying consensus of trees through alignment

This page was built for publication: Determining the consistency of partial tree descriptions

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