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

DOI10.1080/11663081.2016.1139967zbMATH Open1398.03106arXiv1410.3059OpenAlexW3100765028MaRDI QIDQ4586148FDOQ4586148

Authors: Greg Yang 

Publication date: 12 September 2018

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

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.

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

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

Mathematics Subject Classification ID

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

Cites Work

• Measure theory. Vol. I and II
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Elements of finite model theory.
• Title not available (Why is that?)
• Title not available (Why is that?)
• A theory of the learnable
• Toward efficient agnostic learning
• Title not available (Why is that?)
• Vapnik-Chervonenkis density in some theories without the independence property. II
• Vapnik-Chervonenkis Classes of Definable Sets
• Vapnik-Chervonenkis density in some theories without the independence property. I
• Learning halfspaces with malicious noise
• Robust logics
• 10.1162/153244304773936072
• Probabilistic Logic and Induction
• Decidability and Undecidability in Probability Logic
• Learning Theory
• Model theory of measure spaces and probability logic
• Computational hardness of validity in probability logic

Cited In (5)

• On relative and probabilistic finite counterability
• Title not available (Why is that?)
• On standard completeness and finite model property for a probabilistic logic on Łukasiewicz events
• Computational hardness of validity in probability logic
• 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)