Geodesic
On Computational Aspects of Maximal Specificity in Probabilistic Explanation
Sibirskij žurnal čistoj i prikladnoj matematiki, Tome 11 (2011) no. 4, pp. 78-93

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{VNGU_2011_11_4_a7,
     author = {S. O. Speranski},
     title = {On {Computational} {Aspects} of {Maximal} {Specificity} in {Probabilistic} {Explanation}},
     journal = {Sibirskij \v{z}urnal \v{c}istoj i prikladnoj matematiki},
     pages = {78--93},
     publisher = {mathdoc},
     volume = {11},
     number = {4},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VNGU_2011_11_4_a7/}
}
TY  - JOUR
AU  - S. O. Speranski
TI  - On Computational Aspects of Maximal Specificity in Probabilistic Explanation
JO  - Sibirskij žurnal čistoj i prikladnoj matematiki
PY  - 2011
SP  - 78
EP  - 93
VL  - 11
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/VNGU_2011_11_4_a7/
LA  - ru
ID  - VNGU_2011_11_4_a7
ER  - 
%0 Journal Article
%A S. O. Speranski
%T On Computational Aspects of Maximal Specificity in Probabilistic Explanation
%J Sibirskij žurnal čistoj i prikladnoj matematiki
%D 2011
%P 78-93
%V 11
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/VNGU_2011_11_4_a7/
%G ru
%F VNGU_2011_11_4_a7
S. O. Speranski. On Computational Aspects of Maximal Specificity in Probabilistic Explanation. Sibirskij žurnal čistoj i prikladnoj matematiki, Tome 11 (2011) no. 4, pp. 78-93. http://geodesic.mathdoc.fr/item/VNGU_2011_11_4_a7/