期刊,Journal of logic, language and information 2025年34卷1/2期_国家学术搜索

On the Strongest Principles of Rational Belief Assignment

J. B. ParisA. Vencovska

1-26页

查看更多>>摘要：We show that in Polyadic Pure Inductive Logic the Invariance Principle, based on consideration of symmetry with respect to automorphisms, has only a trivial solution, namely the polyadic equivalent of Carnap's c_0. (This extends a result proved earlier in the unary case.) We then consider the Exchangeable Invariance Principle, a symmetry principle which is a weakening of the Invariance Principle and has been proven to be strictly stronger than the Permutation Invariance Principle. We show that the Exchangeable Invariance Principle follows from Spectrum Exchangeability, a principle not obviously based on symmetry but based on irrelevance, that is treating certain features as irrelevant for the purpose of belief assignment, and that the converse does not hold. We conclude that Spectrum Exchangeability is the strongest currently known rational principle of belief assignment in Pure Inductive Logic that does not lead to the aforementioned trivial solution.

原文链接:

NETL
NSTL
Springer Nature

On the Strongest Principles of Rational Belief Assignment

J. B. ParisA. Vencovska

1-26页

查看更多>>摘要：We show that in Polyadic Pure Inductive Logic the Invariance Principle, based on consideration of symmetry with respect to automorphisms, has only a trivial solution, namely the polyadic equivalent of Carnap's c_0. (This extends a result proved earlier in the unary case.) We then consider the Exchangeable Invariance Principle, a symmetry principle which is a weakening of the Invariance Principle and has been proven to be strictly stronger than the Permutation Invariance Principle. We show that the Exchangeable Invariance Principle follows from Spectrum Exchangeability, a principle not obviously based on symmetry but based on irrelevance, that is treating certain features as irrelevant for the purpose of belief assignment, and that the converse does not hold. We conclude that Spectrum Exchangeability is the strongest currently known rational principle of belief assignment in Pure Inductive Logic that does not lead to the aforementioned trivial solution.

原文链接:

NETL
NSTL
Springer Nature

Non-Monotonicity and Contraposition

Vincenzo CrupiTiziano DalmonteAndrea lacona

27-46页

查看更多>>摘要：This paper develops a formal theory of non-monotonic consequence which differs from most extant theories in that it assumes Contraposition as a basic principle of defeasible reasoning. We define a minimal logic that combines Contraposition with three uncontroversial inference rules, and we prove some key results that characterize this logic and its possible extensions.

原文链接:

NETL
NSTL
Springer Nature

Non-Monotonicity and Contraposition

Vincenzo CrupiTiziano DalmonteAndrea lacona

27-46页

查看更多>>摘要：This paper develops a formal theory of non-monotonic consequence which differs from most extant theories in that it assumes Contraposition as a basic principle of defeasible reasoning. We define a minimal logic that combines Contraposition with three uncontroversial inference rules, and we prove some key results that characterize this logic and its possible extensions.

原文链接:

NETL
NSTL
Springer Nature

One Head is Better than Two: A Polynomial Restriction for Propositional Definite Horn Forgetting

Paolo Liberatore

49-88页

查看更多>>摘要：Logical forgetting is NP-complete as a decision problem even in the simple case of propositional Horn formulae, and may exponentially increase their size. A way to forget is to replace each variable to forget with the body of each clause whose head is the variable. It takes polynomial time in the single-head case: each variable is the head of at most a clause. Some formulae are not single-head but can be made so to simplify forgetting. They are called single-head equivalent. The first contribution of this article is the study of a semantical characterization of single-head equivalence. Two necessary conditions are given. They are sufficient when the formula is interequivalent, that is, the formula makes two sets of variables equivalent only if they are also equivalent to their intersection. All acyclic formulae are interequivalent. The second contribution of this article is an incomplete algorithm for turning a formula single-head. In case of success, forgetting becomes possible in polynomial time and produces a polynomial-size formula, none of which is otherwise guaranteed. The algorithm is complete on interequivalent formulae.

原文链接:

NETL
NSTL
Springer Nature

One Head is Better than Two: A Polynomial Restriction for Propositional Definite Horn Forgetting

Paolo Liberatore

49-88页

查看更多>>摘要：Logical forgetting is NP-complete as a decision problem even in the simple case of propositional Horn formulae, and may exponentially increase their size. A way to forget is to replace each variable to forget with the body of each clause whose head is the variable. It takes polynomial time in the single-head case: each variable is the head of at most a clause. Some formulae are not single-head but can be made so to simplify forgetting. They are called single-head equivalent. The first contribution of this article is the study of a semantical characterization of single-head equivalence. Two necessary conditions are given. They are sufficient when the formula is interequivalent, that is, the formula makes two sets of variables equivalent only if they are also equivalent to their intersection. All acyclic formulae are interequivalent. The second contribution of this article is an incomplete algorithm for turning a formula single-head. In case of success, forgetting becomes possible in polynomial time and produces a polynomial-size formula, none of which is otherwise guaranteed. The algorithm is complete on interequivalent formulae.

原文链接:

NETL
NSTL
Springer Nature

A Logical Characterization of Weak Determinism as Simultaneous Application

Tatevik Yolyan

89-153页

查看更多>>摘要：Weakly deterministic functions are a subregular class of functions which have been claimed to describe the complexity of most attested phonological maps. This paper proposes a characterization of the weak deterministic functions within the formalism of Boolean Monadic Recursive Schemes (BMRS), in terms of a simultaneous application operator over BMRS programs. This paper provides proof that more complex patterns such as Sour Grapes harmony are not weakly deterministic, and shows that the proposed definition can decisively distinguish between weakly deterministic and properly regular maps. The consequence of this work is a logical characterization of the weakly deterministic boundary, and a testable hypothesis about the complexity of natural language phonological maps.

原文链接:

NETL
NSTL
Springer Nature

A Logical Characterization of Weak Determinism as Simultaneous Application

Tatevik Yolyan

89-153页

查看更多>>摘要：Weakly deterministic functions are a subregular class of functions which have been claimed to describe the complexity of most attested phonological maps. This paper proposes a characterization of the weak deterministic functions within the formalism of Boolean Monadic Recursive Schemes (BMRS), in terms of a simultaneous application operator over BMRS programs. This paper provides proof that more complex patterns such as Sour Grapes harmony are not weakly deterministic, and shows that the proposed definition can decisively distinguish between weakly deterministic and properly regular maps. The consequence of this work is a logical characterization of the weakly deterministic boundary, and a testable hypothesis about the complexity of natural language phonological maps.

原文链接:

NETL
NSTL
Springer Nature

A Family Whose Computable Numberings are All Complete

Marat Faizrahmanov

155-167页

查看更多>>摘要：In this paper, we construct a computable family R of r.e. sets whose every computable numbering α is complete and encodes the Godel numbering x→ W_x of the family of all r.e. sets within itself in the sense that there exists a recursive function r such that for every b ∈ N there is a B ⊆ N with α(r(b)) = B ⊕W_b. Then we prove that, for all n≥ 2, every non-trivial Σ_n~0-computable family has a non-complete (and even non-cylindrical) Σ_n~0-computable numbering, but there exists a Σ_n~0-computable family A whose every Σ_n~0computable numbering β has the fixed point property (i.e., for every recursive function / there is a p ∈ N with β(f(p)) = β(p)) and encodes within itself the numbering x → W_x~(￠~((n-1))

原文链接:

NETL
NSTL
Springer Nature

A Family Whose Computable Numberings are All Complete

Marat Faizrahmanov

155-167页

查看更多>>摘要：In this paper, we construct a computable family R of r.e. sets whose every computable numbering α is complete and encodes the Godel numbering x→ W_x of the family of all r.e. sets within itself in the sense that there exists a recursive function r such that for every b ∈ N there is a B ⊆ N with α(r(b)) = B ⊕W_b. Then we prove that, for all n≥ 2, every non-trivial Σ_n~0-computable family has a non-complete (and even non-cylindrical) Σ_n~0-computable numbering, but there exists a Σ_n~0-computable family A whose every Σ_n~0computable numbering β has the fixed point property (i.e., for every recursive function / there is a p ∈ N with β(f(p)) = β(p)) and encodes within itself the numbering x → W_x~(￠~((n-1))

原文链接:

NETL
NSTL
Springer Nature