Computability of validity and satisfiability in probability logics over finite and countable models

DOI10.1080/11663081.2016.1139967MaRDI QIDQ4586148zbMATH OpenOpenAlexFDO

Authors Greg Yang

Publication date 12 September 2018

Published in Journal of Applied Non-Classical Logics (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Probability and inductive logic (03B48) Model theory of finite structures (03C13) Model theory of denumerable and separable structures (03C15) Complexity of computation (including implicit computational complexity) (03D15) Learning and adaptive systems in artificial intelligence (68T05)

Abstract: The $epsilon$-logic (which is called $epsilon$E-logic in this paper) of Kuyper and Terwijn is a variant of first order logic with the same syntax, in which the models are equipped with probability measures and in which the $forallx$ quantifier is interpreted as "there exists a set $A$ of measure $ge1-epsilon$ such that for each $xinA$, ...." Previously, Kuyper and Terwijn proved that the general satisfiability and validity problems for this logic are, i) for rational $epsilonin(0,1)$, respectively $Sigm{a}_1^1$-complete and $P{i}_1^1$-hard, and ii) for $epsilon=0$, respectively decidable and $Sigm{a}_1^0$-complete. The adjective "general" here means "uniformly over all languages." We extend these results in the scenario of finite models. In particular, we show that the problems of satisfiability by and validity over finite models in $epsilon$E-logic are, i) for rational $epsilonin(0,1)$, respectively $Sigm{a}_1^0$- and $P{i}_1^0$-complete, and ii) for $epsilon=0$, respectively decidable and $P{i}_1^0$-complete. Although partial results toward the countable case are also achieved, the computability of $epsilon$E-logic over countable models still remains largely unsolved. In addition, most of the results, of this paper and of Kuyper and Terwijn, do not apply to individual languages with a finite number of unary predicates. Reducing this requirement continues to be a major point of research. On the positive side, we derive the decidability of the corresponding problems for monadic relational languages --- equality- and function-free languages with finitely many unary and zero other predicates. This result holds for all three of the unrestricted, the countable, and the finite model cases. Applications in computational learning theory, weighted graphs, and neural networks are discussed in the context of these decidability and undecidability results.

Recommendations

• Probabilization of logics: completeness and decidability
• On the satisfiability of some simple probabilistic logics
• Computational aspects of probability logics
• Probability logic: A model-theoretic perspective
• A Logic of Probability with Decidable Model Checking
• scientific article; zbMATH DE number 1948170
• Computational hardness of validity in probability logic
• The complexity of satisfiability in non-iterated and iterated probabilistic logics
• Complexity for probability logic with quantifiers over propositions

Cites work

• 10.1162/153244304773936072
• A theory of the learnable
• Computational hardness of validity in probability logic
• Decidability and Undecidability in Probability Logic
• Elements of finite model theory.
• scientific article; zbMATH DE number 19091 (Why is no real title available?)
• scientific article; zbMATH DE number 194103 (Why is no real title available?)
• scientific article; zbMATH DE number 1234104 (Why is no real title available?)
• scientific article; zbMATH DE number 2061729 (Why is no real title available?)
• scientific article; zbMATH DE number 783783 (Why is no real title available?)
• scientific article; zbMATH DE number 3050845 (Why is no real title available?)
• Learning halfspaces with malicious noise
• Learning Theory
• Measure theory. Vol. I and II
• Model theory of measure spaces and probability logic
• Probabilistic Logic and Induction
• Robust logics
• Toward efficient agnostic learning
• Vapnik-Chervonenkis Classes of Definable Sets
• Vapnik-Chervonenkis density in some theories without the independence property. I
• Vapnik-Chervonenkis density in some theories without the independence property. II

Cited in

(5)

• On relative and probabilistic finite counterability
• On standard completeness and finite model property for a probabilistic logic on Łukasiewicz events
• Computational hardness of validity in probability logic
• scientific article; zbMATH DE number 465528 (Why is no real title available?)
• Random unary predicates: Almost sure theories and countable models

This page was built for publication: Computability of validity and satisfiability in probability logics over finite and countable models

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4586148)