CS Paper Radar

Cyclic Nonassociative Bilinear Logic With Additive Constants as Extension of Full Nonassociative Lambek Calculus

Paweł Płaczek, Cheng-Syuan Wan

cs.LO ·submitted 2026-10-29 18:04 UTC · v1
publishedtheory

Abstract

Cyclic Linear Logic (CyMALL, CyBL) is a compromise between Commutative Linear Logic (MALL) and Noncommutative Linear Logic (Bilinear Logic, BL). We do not admit commutativity of the tensor, but we still admit only one De Morgan negation. MALL and its variants are natural extensions of Full Lambek Calculus (FL). Abrusci proved that CyBL is not a conservative extension of FL, if we admit additive constants in these logics. In this paper we show that Cyclic Nonassociative Bilinear Logic (CyNBL) with both additive constants is a strongly conservative extension of Full Nonassociative Lambek Calculus with only one additive constant - the upper bound - and that this holds even in the presence of an arbitrary set of nonlogical axioms.

Comment
In Proceedings NCL'26, arXiv:2610.34489
Journal ref
EPTCS 455, 2026, pp. 151-164
DOI
10.4204/EPTCS.455.12

Closest papers

Nearest neighbours by meaning across the whole index.

Restricted Peirce's Law and Natural Deduction

cs.LO ·2026-10-29 ·Satoru Niki
publishedtheoryhot direction similarity 0.55
Abstract · In Proceedings NCL'26, arXiv:2610.34489

The constructive logic JP' is known to be the weakest logic between intuitionistic and minimal logic that satisfies Glivenko's theorem. In spite of this natural and desirable formal property, the motivation for its notion of negation remains rather elusive: it can be characterised by a restriction of Peirce's law or by the double negation of ex falso quodlibet, neither of which is very intuitive. In order to have an alternative perspective on this negation, we study in this paper a couple of natural deduction systems for JP'. We first present a system that is normalisable and satisfies a restricted form of the subformula property. Then a modification of this system is introduced, whose rules satisfy the separation of connectives and the full subformula property. Afterwards we turn our attention to a typed lambda-calculus, with respect to which our natural deduction enjoys the Curry-Howard correspondence, followed by a concluding discussion.

0.40

Non-Expansive Fuzzy Modal Logic Has Uniform Interpolation

cs.LO ·2026-10-23 ·Stefan Gebhart, Lutz Schröder, Paul Wild
similarity 0.53
Abstract

Fuzzy logics with truth values in the unit interval vary in their choice of propositional connectives and their semantics, ranging from just minimum and maximum as in Zadeh logics to truncated addition and subtraction as in Łukasiewicz logics or their extensions with truth constants, known as Pavelka logics. In the more specific world of fuzzy modal logics, non-expansive fuzzy modal logic has recently been proposed as a sweet spot between Łukasiewicz (more precisely, Pavelka) and Zadeh fuzzy modal logic; it restricts Łukasiewicz propositional connectives to have one argument constant, equivalently extends the Zadeh propositional base with constant shift operators. It retains reasonable expressiveness both in practical terms and abstractly; in particular, it characterizes the standard notion of behavioural distance on fuzzy Kripke frames. At the same time, it allows for satisfiability checking in the same complexity as for its two-valued correspondent (the modal logic K, or the description logic ALC), in contrast to the notorious computational hardness of Łukasiewicz modal logic. In the present work, we show that non-expansive fuzzy modal logic admits uniform interpolation, a key property in modularization, information hiding, summarization, and other applications that fails for both Łukasiewicz (or Pavelka) and Zadeh modal logic.

0.24

Proceedings Twelfth International Conference on Non-Classical Logics. Theory and Applications

cs.LO cs.SC ·2026-10-25 ·Andrzej Indrzejczak, Tomasz Jarmu{ż}ek, Mateusz Klonowski, Michał Zawidzki
publishedunusual similarity 0.53
Abstract

Non-Classical Logics. Theory and Applications (NCL) is an international conference aimed at presenting novel results and survey papers in the broad field of non-classical logics and their applications. The first two editions were held in Ł{ó}d{ź}, Poland, in September 2008 and 2009. Subsequent editions were organised in Toru{ń} (2010, 2012, 2015, 2018) and Ł{ó}d{ź} (2011, 2013, 2016, 2022, 2024). The tenth edition of the conference, organised by the University of Ł{ó}d{ź} in 2022, was the first to have its proceedings published in EPTCS. We are honoured and pleased to continue this practice and, for the third time, include all accepted long papers in an EPTCS volume. Furthermore, for the first time, we have also included all accepted extended abstracts in the volume.

0.41

Paraclassical Logics with Two Negations

cs.LO ·2026-10-29 ·Pawel Pawlowski, Pietro Vigiani
publishedhot direction similarity 0.53
Abstract · In Proceedings NCL'26, arXiv:2610.34489

We study three paraclassical propositional logics with two negations, CLoaN, CLouN, and CLauN, obtained by pairwise combining the one-negation systems CLuN, CLaN, and CLoN. CLuN's negation is glut-tolerant and paraconsistent, CLaN's negationis gap-tolerant and paracomplete, and CLoN's negation is both paraconsistent and paracomplete. We provide sound and complete two-valued non-deterministic semantics for each of the two-negations systems. We then focus on CLauN, the system containing the primitive dual pair of CLaN and CLuN negations. In this setting, we show deductive relationships between different negations expressible in CLauN; we show two diferent ways to recapture classical logic by means of translations, locally and globally; and we show a duality results for the multiple conclusion consequence relation of the logic.

0.48

A Counterexample to KL1 Completeness and a Complete Disjunctive Calculus

cs.LO ·2026-10-27 ·Damiano Presa, Fabio Aurelio D'Asaro, Massimiliano Badino
theory similarity 0.52
Abstract

The logic KL$_1$ of Evans, Sergot and Stephenson formalizes Kant's rules as conditional imperatives $B \square\to C$ and permissives $B \diamond\to C$ over acts. Its consequence relation is operational: a rule follows from a set of rules when adjoining it leaves the set of outcomes unchanged for every input. The authors proved their calculus sound and conjectured that it is complete. We show that the conjecture fails: for distinct atoms $b,c,d$ the rules $\top \diamond\to b \lor d$, $b \diamond\to c$, $d \diamond\to c$ and $c \square\to b \lor d$ entail $\top \diamond\to c$, which is not derivable. Non-derivability is proved by an invariant that holds at every derivation depth and for arbitrary intermediate atoms. The obstruction is the side condition of may-trans, which requires each new act to bring with it a single intermediary act. Replacing it by a disjunctive side condition yields may-trans-disj, a strict generalization from which the original rule is derivable. Using a local characterization of entailment, we prove the repaired calculus sound for arbitrary sets of rules and complete for finite ones, and we show that, with finite inputs, completeness cannot be extended to infinite sets. The main results on KL$_1$ are formalized in Agda. For KL$_2$ we observe that the published reduction to KL$_1$ passes through infinite rule sets; re-establishing the decomposition for finite rule sets, we prove that KL$_2$ with the disjunctive rule is sound and complete for finite sets of rules. We close with remarks on KL$_3$ and on the significance of completeness for the relation between the operational and the inferential questions of Kant's logic.

0.32

Tracking relevance syntactically: A nested approach to weak relevant logic

cs.LO ·2026-11-12 ·Fabio De Martin Polo, Han Gao
theory similarity 0.51
Abstract

The variable-sharing property (VSP) is regarded as a key feature of relevant logics, while the Craig interpolation property (CIP), formulated with respect to relevant implication, implies the VSP in constant-free propositional languages. However, to the best of our knowledge, no constant-free distributive relevant logic has previously been shown to enjoy the CIP. This absence of positive results has contributed to a widespread impression among relevant logicians that relevance and Craig interpolation are incompatible. In this work, we address this tension by proving that the negation-free fragment of base relevant logic B, denoted B+, enjoys both properties. Our proof is purely syntactic and is based on a novel nested sequent calculus featuring binary relevant blocks as primitive structural constructs. Unlike conventional nested sequent calculi, where unary nesting reflects the binary accessibility relation of Kripke semantics, our calculus employs a binary nesting operator that directly reflects the ternary relational structure of Routley-Meyer semantics for relevant logics. After establishing soundness and cut-free completeness of the calculus, we prove several meta-logical properties for the logic. Most notably, we provide the first syntactic proof of the VSP (along with a variety of its stronger variants) and the first proof of the CIP for B+, both derived directly from the cut-free system using a structural notion internalized within nested sequents.

0.26

Modal Extensions of Generalised Nelson Logics

cs.LO ·2026-10-07 ·Igor Sedlár, Pietro Vigiani
similarity 0.51
Abstract

Motivated by relevant epistemic logic, we extend Dunn's simple Kripke-style binary relational semantics for the semi-relevant logic RM to fit a modal extension of RM. It is shown that the modal axioms and rules that need to be added to RM to obtain a sound and complete axiomatisation of its modal extension give an axiomatisation of modal extensions of all logics in the family of generalised Nelson logics, also studied by Dunn.

0.31

An Infinitary and a Cyclic Sequent Calculus for Non-Monotone Inductive Definitions

cs.LO math.LO ·2026-09-22 ·Robbe Van den Eede
published similarity 0.49
Abstract · 44 pages, 4 figures

Inductive definitions are an important form of knowledge in mathematics and computer science. Two common techniques to prove theorems about inductive definitions are the principle of mathematical induction and the principle of infinite descent. To formalize these principles, Brotherston and Simpson introduced the sequent calculus proof systems LKID, for mathematical induction, and LKIDω and CLKIDω , for infinite descent. LKIDω is an infinitary system, in which proofs are infinite trees, and CLKIDω a cyclic system, in which proofs are finite graphs. However, these calculi restrict to monotone definitions, while inductive definitions are generally non-monotone. The logic FO(ID) extends classical first-order logic with non-monotone inductive definitions. In earlier work, we provided a formalization of the principle of mathematical induction for non-monotone definitions by extending LKID to a sequent calculus SCFO(ID) for FO(ID). In this paper, we provide a formalization of the principle of infinite descent for non-monotone definitions by extending LKIDω and CLKIDω to sequent calculi SCFO(ID)-inf resp. SCFO(ID)-cyc for FO(ID). Furthermore, we extend several proof-theoretic results for LKIDω and CLKIDω to SCFO(ID)-inf and SCFO(ID)-cyc regarding soundness, completeness, cut-elimination and the relation with SCFO(ID).

0.50