The complexity of reasoning with FODD and GFODD

DOI10.1016/j.artint.2015.08.005zbMath1344.68215arXiv1407.1408OpenAlexW2293553724MaRDI QIDQ900300

Benjamin J. Hescott, Roni Khardon

Publication date: 22 December 2015

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1407.1408

zbMATH Keywords

first-order logicpolynomial hierarchycomplexity analysisdecision diagrams

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Knowledge representation (68T30) Classical first-order logic (03B10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Uses Software

• ProbLog
• FODD-Planner
• FluCaP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Decision-theoretic planning with generalized first-order decision diagrams
• Finite-model theory -- A personal perspective
• Elements of finite model theory.
• Practical solution techniques for first-order MDPs
• Model theory.
• Reasoning with examples: Propositional formulae and database dependencies
• Binary decision diagrams for first-order predicate logic.
• Markov logic networks
• Reasoning with models
• Probabilistic Relational Planning with First Order Decision Diagrams
• Graph-Based Algorithms for Boolean Function Manipulation
• Learning to reason
• Computability and complexity theory
• Graph Ramsey theory and the polynomial hierarchy