Computabilities of Validity and Satisfiability in Probability Logics
  over Finite and Countable Models
  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
$\forall x$ quantifier is interpreted as "there exists a set $A$ of measure
$\ge 1 - \epsilon$ such that for each $x \in A$, ...." Previously, Kuyper and
Terwijn proved that the general satisfiability and validity problems for this
logic are, i) for rational $\epsilon \in (0, 1)$, respectively
$\Sigma^1_1$-complete and $\Pi^1_1$-hard, and ii) for $\epsilon = 0$,
respectively decidable and $\Sigma^0_1$-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 $\epsilon \in (0, 1)$, respectively
$\Sigma^0_1$- and $\Pi^0_1$-complete, and ii) for $\epsilon = 0$, respectively
decidable and $\Pi^0_1$-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.
