Vestnik Novosibirskogo Gosudarstvennogo Universiteta. Seriya Matematika, Mekhanika, Informatika
 RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Sib. J. Pure and Appl. Math.: Year: Volume: Issue: Page: Find

 Vestn. Novosib. Gos. Univ., Ser. Mat. Mekh. Inform., 2011, Volume 11, Issue 4, Pages 78–93 (Mi vngu102)

On Computational Aspects of Maximal Specificity in Probabilistic Explanation

S. O. Speranski

Novosibirsk State University

Abstract: In the present paper the computational aspects of the formal requirement of maximal specificity are investigated. This requirement is imposed on rules in the language of propositional classical logic when given a computable rational-valued probability measure over the language. We prove undecidability for several general problems of discovering maximally specific rules and probability measures for which the collection of all specific rules is computable; establish decidability of the set of maximally specific rules if certain natural conditions are met; study the question whether it is possible to uniformly obtain decision procedures in case these conditions hold; estimate the complexity of introduced subclasses of measures in the arithmetical hierarchy.

Keywords: inductive and probability logic, maximal specificity, decidability, computability, complexity.

Full text: PDF file (283 kB)
References: PDF file   HTML file
UDC: 510.647+.51

Citation: S. O. Speranski, “On Computational Aspects of Maximal Specificity in Probabilistic Explanation”, Vestn. Novosib. Gos. Univ., Ser. Mat. Mekh. Inform., 11:4 (2011), 78–93

Citation in format AMSBIB
\Bibitem{Spe11} \by S.~O.~Speranski \paper On Computational Aspects of Maximal Specificity in Probabilistic Explanation \jour Vestn. Novosib. Gos. Univ., Ser. Mat. Mekh. Inform. \yr 2011 \vol 11 \issue 4 \pages 78--93 \mathnet{http://mi.mathnet.ru/vngu102}