Graph decompositions and tree automata in reasoning with uncertainty

DOI10.1080/09528139308953776MaRDI QIDQ4286533zbMATH OpenOpenAlexFDO

Authors Stefan Arnborg

Publication date 11 December 1994

Published in Journal of Experimental & Theoretical Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/09528139308953776

zbMATH Keywords

Bayesian inferencedecomposable graphsmodel preference reasoningpossibilistic logicprobabilistic logictree automatatree-width

Mathematics Subject Classification ID

Probability and inductive logic (03B48) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Logic in artificial intelligence (68T27)

Recommendations

• Unifying tree decompositions for reasoning in graphical models
• Tree-decompositions and the model-checking problem
• scientific article; zbMATH DE number 2155183
• scientific article; zbMATH DE number 1765702
• Term Rewriting and Applications
• On the strength of unambiguous tree automata
• Deciding entailments in inductive separation logic with tree automata
• An Automata Theoretic Approach to Rational Tree Relations
• Multitrees, model completeness, and decidability
• Validation of Stochastic Systems

Cites work

• A Computational Approach to Approximate and Plausible Reasoning with Applications to Expert Systems
• A logic for default reasoning
• Algorithms finding tree-decompositions of graphs
• Characterization and Recognition of Partial 3-Trees
• Characterization of partial 3-trees in terms of three structures
• Complexity of Finding Embeddings in a k-Tree
• Computing the Reliability of Complex Networks
• Dempster's rule of combination is {\#}P-complete
• Easy problems for tree-decomposable graphs
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Efficient reasoning about rich temporal domains
• Graph expressions and graph rewritings
• scientific article; zbMATH DE number 3974289 (Why is no real title available?)
• scientific article; zbMATH DE number 48812 (Why is no real title available?)
• scientific article; zbMATH DE number 475617 (Why is no real title available?)
• Intuitionistic propositional logic is polynomial-space complete
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Many hard examples for resolution
• Nonserial dynamic programming
• On Spohn's rule for revision of beliefs
• Probabilistic logic
• Reduced State EnumerationߞAnother Algorithm for Reliability Evaluation
• The complexity of computing the permanent
• The computational complexity of probabilistic inference using Bayesian belief networks
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs

Cited in

(3)

• Unifying tree decompositions for reasoning in graphical models
• Partition-based logical reasoning for first-order and propositional theories
• Decomposability helps for deciding logics of knowledge and belief

This page was built for publication: Graph decompositions and tree automata in reasoning with uncertainty

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