Decomposability helps for deciding logics of knowledge and belief

DOI10.1007/3-540-57787-4_3zbMath1496.03067OpenAlexW1528558057MaRDI QIDQ5096273

Stefan Arnborg

Publication date: 16 August 2022

Published in: Graph Transformations in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-57787-4_3

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logics of knowledge and belief (including belief change) (03B42) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15)

Cites Work

• Unnamed Item
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• A guide to completeness and complexity for modal logics of knowledge and belief
• Nonserial dynamic programming
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Algorithms finding tree-decompositions of graphs
• Easy problems for tree-decomposable graphs
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• Computing the Reliability of Complex Networks
• An algebraic theory of graph reduction
• Graph decompositions and tree automata in reasoning with uncertainty

This page was built for publication: Decomposability helps for deciding logics of knowledge and belief