Sufficient and necessary conditions for solution finding in valuation-based systems
From MaRDI portal
Publication:2302788
DOI10.1016/J.IJAR.2019.08.006zbMATH Open1468.68205arXiv1508.03523OpenAlexW2969357465WikidataQ127350688 ScholiaQ127350688MaRDI QIDQ2302788FDOQ2302788
Authors: Jordi Roca-Lacostena, Jesús Cerquides, Marc Pouly 
Publication date: 26 February 2020
Published in: International Journal of Approximate Reasoning (Search for Journal in Brave)
Abstract: Valuation algebras abstract a large number of formalisms for automated reasoning and enable the definition of generic inference procedures. Many of these formalisms provide some notion of solution. Typical examples are satisfying assignments in constraint systems, models in logics or solutions to linear equation systems. Many widely used dynamic programming algorithms for optimization problems rely on low treewidth decompositions and can be understood as particular cases of a single algorithmic scheme for finding solutions in a valuation algebra. The most encompassing description of this algorithmic scheme to date has been proposed by Pouly and Kohlas together with sufficient conditions for its correctness. Unfortunately, the formalization relies on a theorem for which we provide counterexamples. In spite of that, the mainline of Pouly and Kohlas' theory is correct, although some of the necessary conditions have to be revised. In this paper we analyze the impact that the counter-examples have on the theory, and rebuild the theory providing correct sufficient conditions for the algorithms. Furthermore, we also provide necessary conditions for the algorithms, allowing for a sharper characterization of when the algorithmic scheme can be applied.
Full work available at URL: https://arxiv.org/abs/1508.03523
Recommendations
- A solution configuration and its algorithm of valuation algebras induced by a constraint semiring
- An algorithm for finding most likely explanations in valuation based systems
- Semiring induced valuation algebras: exact and approximate local computation algorithms
- On conditions for mappings to preserve optimal solutions of semiring-induced valuation algebras
- Consistency in Valuation-Based Systems
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Dynamic programming (90C39) Semirings (16Y60) Applications of universal algebra in computer science (08A70)
Cites Work
- Direct Methods for Sparse Linear Systems
- Graph theory
- Error bounds for convolutional codes and an asymptotically optimum decoding algorithm
- Title not available (Why is that?)
- Probabilistic graphical models.
- Join-graph propagation algorithms
- Probabilistic Networks and Expert Systems
- Title not available (Why is that?)
- Linear and combinatorial optimization in ordered algebraic structures
- Numerical methods in matrix computations
- Semiring induced valuation algebras: exact and approximate local computation algorithms
- Graphs, dioids and semirings. New models and algorithms.
- Nonserial dynamic programming
- Generic inference. A unifying theory for automated reasoning
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Dynamic programming. A computational tool.
- Title not available (Why is that?)
- Dynamic Programming
- Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
- Computing all-pairs shortest paths by leveraging low treewidth
- Mini-buckets: a general scheme for bounded inference
- Decomposable negation normal form
- Generic local computation
- Finite-State Processes and Dynamic Programming
- AND/OR search spaces for graphical models
- AND/OR branch-and-bound search for combinatorial optimization in graphical models
- Bucket elimination: A unifying framework for reasoning
- A common schema for dynamic programming and branch and bound algorithms
- A stronger model of dynamic programming algorithms
- Memory intensive AND/OR search for combinatorial optimization in graphical models
- Limitations of incremental dynamic programming
- Composition Principles for Synthesis of Optimal Multistage Processes
- Coalition structure generation over graphs
- Hybrid backtracking bounded by tree-decomposition of constraint networks
- Non-Serial Dynamic Programming — A Survey
- Compiling CSPs into tree-driven automata for interactive solving
- Title not available (Why is that?)
- Bridging the algorithm gap: A linear-time functional program for paragraph formatting
Cited In (4)
Uses Software
This page was built for publication: Sufficient and necessary conditions for solution finding in valuation-based systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2302788)
