Graph decompositions and tree automata in reasoning with uncertainty

DOI10.1080/09528139308953776zbMATH0802.68143OpenAlexW2026831733MaRDI QIDQ4286533FDOQ4286533

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 inferencetree automatatree-widthpossibilistic logicprobabilistic logicdecomposable graphsmodel preference reasoning

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Probability and inductive logic (03B48) 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

• 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?)
• 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
• 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 Computational Complexity of Provability in Systems of Modal Propositional Logic
• The complexity of computing the permanent
• The computational complexity of probabilistic inference using Bayesian belief networks
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs

Cited in

(3)

• Partition-based logical reasoning for first-order and propositional theories
• Unifying tree decompositions for reasoning in graphical models
• 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)