Possibilistic logic: Complexity and algorithms
This paper represents a chapter in Volume 5 of the Handbook of defeasible reasoning and uncertainty management systems. It contains a comprehensive study of algorithmic and complexity issues related to possibilistic logic. Section 1 of the paper introduces the main notions and problems. Section 2 recalls the basics of possibilistic theory, viz. a formal background of standard possibilistic logic (SPL). SPL, or necessity-valued fragment of possibilistic logic, although poorer than full possibilistic logic, is important because: (a) algorithmic issues are simpler and easily extendible to the full case, and (b) SPL is sufficient for modelling a preference order upon formulae, which is closely related to the nonmonotonic approach to preferential models and belief revision theory. Section 3 investigates algorithmic and complexity issues for the deduction problem in SPL. Several versions of the deduction problem are considered for a possibilistic extension of refutation by resolution. The complexity issues are restricted to the case of propositional necessity-valued logic. Section 4 discusses algorithms for possibilistic model finding, based on an extension of the well-known procedure of Davis and Putnam, also in the case of propositional SPL. Section 5 examines proof methods for an extended fragment of possibilistic logic, which handles both certainty-valued and possibility-valued statements. The final Section 6 concludes, pointing to related work such as fuzzy constraint satisfaction, possibilistic logic programming, and drowning-free variants of possibilistic logic. Nine important areas of applications of the discussed topics are emphasized.NEWLINENEWLINEFor the entire collection see [Zbl 0959.00013].
- scientific article; zbMATH DE number 3995647
- Computational complexity and the expressive power of logics
- Probabilistic logic under coherence: complexity and algorithms
- Complexity for probability logic with quantifiers over propositions
- scientific article; zbMATH DE number 4103047
- Computational aspects of probability logics
- scientific article; zbMATH DE number 4114609
- Probabilization of logics: completeness and decidability
- On the transformation between possibilistic logic bases and possibilistic causal networks
- Fusion of possibilistic knowledge bases from a postulate point of view.
- Qualitative conditioning in an interval-based possibilistic setting
- The possibilistic Horn non-clausal knowledge bases
- Extending uncertainty formalisms to linear constraints and other complex formalisms
- A split-combination approach to merging knowledge bases in possibilistic logic
- A possibilistic decision logic with applications
- Compiling min-based possibilistic causal networks: a mutilated-based approach
- Possibilistic extension rules for reasoning and knowledge compilation
- Symbolic possibilistic logic: completeness and inference methods
- scientific article; zbMATH DE number 500949 (Why is no real title available?)
- Quantitative possibility theory: logical- and graphical-based representations
- scientific article; zbMATH DE number 6806035 (Why is no real title available?)
- Complexity of Possible and Necessary Existence Problems in Abstract Argumentation
- Algorithmic correspondence and canonicity for possibility semantics
- Possibilistic logic: a retrospective and prospective view
- Reasoning with partially ordered information in a possibilistic logic framework
- A first polynomial non-clausal class in many-valued logic
- Solving conflicts in information merging by a flexible interpretation of atomic propositions
- Reasoning and learning in the setting of possibility theory -- overview and perspectives
- Analysis of the syntactic computation of Fagin-Halpern conditioning in possibilistic logic
- Syntactic computation of Fagin-Halpern conditioning in possibility theory
- Logical representation and fusion of prioritized information based on guaranteed possibility measures: Application to the distance-based merging of classical bases
- Weakening conflicting information for iterated revision and knowledge integration
- Hybrid possibilistic networks
- A new default theories compilation for MSP-entailment
This page was built for publication: Possibilistic logic: Complexity and algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2752126)
