On Propositional Definability
Lang, Jérôme; Marquis, Pierre (2006), On Propositional Definability, Artificial Intelligence, 172, 8-9, p. 991-1017. 10.1016/j.artint.2007.12.003
TypeArticle accepté pour publication ou publié
Journal nameArtificial Intelligence
MetadataShow full item record
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Centre de Recherche en Informatique de Lens [CRIL]
Abstract (EN)In standard propositional logic, logical definability is the ability to derive the truth value of some propositional symbols given a propositional formula and the truth values of some propositional symbols. Although appearing more or less informally in various AI settings, a computation-oriented investigation of the notion is still lacking, and this paper aims at filling the gap. After recalling the two definitions of definability, which are equivalent in standard propositional logic (while based on different intuitions), and defining a number of related notions, we give several characterization results, and many complexity results for definability. We also show close connections with hypothesis discriminability and with reasoning about action and change.
Subjects / KeywordsKnowledge representation; Propositional logic; Computational complexity; Definability; Hypothesis discriminability; Reasoning about action and change
Showing items related by title and author.