CS Paper Radar

Multimodal Logic Programming with Full Formulas

Kenji Tokuo

cs.LO math.LO ·submitted 2026-08-14 13:28 UTC · v1

Abstract

This paper presents a first-order multimodal logic programming system called MMLP. The system accepts arbitrary formulas as both programs and queries, without restricting either side to Horn clauses or a separate goal grammar. Its declarative semantics is given independently by a Hilbert system for selected D, T, I, B, 4, and 5 modal principles. Execution uses a nested proof calculus with finite grammar certificates for modal propagation. Certificate reachability is equivalent to the associated Horn closure, certificate existence is decidable, and the calculus is cut-free complete. For quantified answer computation, we give a unification algorithm based on permission sets that controls eigenparameter scope. The algorithm always terminates and fails exactly when no admissible solution exists. A successful run returns a unifier that is itself admissible and through which all admissible solutions factor. Computed answers are declaratively correct, and each declaratively correct answer is an ordinary output instance of a computed answer. In proof search, MMLP admits syntactic focalization and a fair and complete enumeration of focused answers. It represents exactly the same answer substitutions as Nguyen's pure logical KDI4s5-MPROLOG on their common fragment, while admitting a strictly larger program and query language.

Closest papers

Nearest neighbours by meaning across the whole index.

Verifiable LLM-Guided Focal SMT Solving for Quantified Arrays

cs.AI ·2026-10-29 ·Kunhang Lv, Rui Han, Fuqi Jia, Yuhang Dong, Feifei Ma +1 more
similarity 0.65
Abstract

Large language models can often identify useful semantic structure in formal artifacts, but their outputs cannot be trusted as proofs or solver decisions. We study whether LLMs can instead guide formal reasoning systems through a narrow, solver-verifiable interface. We instantiate this idea in quantified array SMT solving, where modern instantiation-based techniques can fail when key ground terms and equalities are hidden by auxiliary variables, axiom guards, and nested array terms. We observe that many instances are largely driven by a small set of focal ground terms or constraints, similar to the backdoor sets in SAT solving. Building on this, we present LinguaArray, a framework where an LLM proposes a small Semantic Focus Set (ground terms/constraints), while a conventional SMT solver remains the sole proof engine and certifies all results. LinguaArray uses these LLM-suggested, solver-validated finite sets to significantly enhance solver capability, solving additional satisfiable and unsatisfiable instances that the backend alone fails to solve. It interacts within a finite time and then falls back to the backend solver to mitigate potential regressions. Evaluation on 1015 SMT-LIB instances across five logics under 1200s timeout (including LLM latency) shows that LinguaArray solves up to 69.1% of instances and increases solved-instance counts by 105%--397% over the corresponding backends.

0.22

Library-Grade Modal Logic

cs.LO ·2026-10-03 ·Marianna Girlando, Fabrizio Montesi
similarity 0.62
Abstract

Modal logic comprises a broad family of logics to reason about relational structures. The literature presents many such logics, displaying diverse operators, semantics, and applications. This plurality is reflected in a zoo of mechanised modal logics, which often duplicate syntax, semantics, metatheory, and reasoning infrastructure. We present a library-grade formalisation of modal logic in Lean, developed as part of CSLib (the Lean Computer Science Library) and designed around two complementary forms of reuse: vertical reuse, whereby specialised logics inherit from common abstractions, and horizontal reuse, whereby modal logic becomes a reasoning tool for independently formalised domains. Our development provides a generic framework for polyadic modal languages, reusable metatheory and proof automation, and derived interfaces for specialised modal logics. We exemplify our infrastructure by deriving basic modal logic, basic temporal logic, and Hennessy-Milner Logic; the latter subsumes and extends CSLib's previous implementation while reducing its logic-specific code by 67%. We further apply the same modal infrastructure to reasoning about mathematics (radicals of ideals), theory of programming languages (the type safety strategy for the simply typed $λ$-calculus), and concurrency theory (reasoning about processes in the Calculus of Communicating Systems). Our experience suggests that reuse, automation, and integration with the strong Lean ecosystem should be treated as first-class design concerns when formalising theories for shared libraries.

0.16

Symbolic Execution of Constrained Horn Clauses

cs.LO cs.PL ·2026-10-02 ·Johannes Weiser, Zafer Esen, Philipp Rümmer
similarity 0.62
Abstract · 34 pages, 8 figures

Constrained Horn clauses (CHCs) are a fragment of first-order logic widely used as an intermediate language for verification. We study constrained resolution as a calculus for reasoning about the satisfiability of sets of CHCs. Constrained resolution forms a simple alternative to model checking algorithms such as CEGAR and IC3 and is here shown to exhibit complementary features. We show that, when CHCs encode programs, forward symbolic execution corresponds to positive unit hyper-resolution, and backward symbolic execution to SLD resolution, which are special cases of constrained resolution. We formalize forward and backward reasoning for linear and non-linear CHCs and transition systems, prove refutational completeness under fair strategies, and develop subsumption criteria for pruning redundant derivations. We moreover show that backward resolution with subsumption generalizes $k$-induction to non-linear CHCs, and that forward constrained resolution is related to the problem of constructing proofs in incorrectness logic. Lastly, we provide an experimental evaluation in the Eldarica CHC solver on benchmarks from CHC-COMP.

0.19

Towards Finite Satisfiability of PDL with Loops

cs.LO ·2026-10-11 ·Bartosz Jan Bednarczyk, Mikołaj Swoboda
theory similarity 0.61
Abstract · 52 pages, 8 figures, 2 tables. Under submission. This is a part of our ongoing work in progress: we are close to settling the finite satisfi…

Propositional Dynamic Logic (PDL) is a well-established modal logic of programs. Among its many extensions, the loop operator stands out for capturing the cyclic behaviour of programs: a world satisfies loop(pi) precisely when it can return to itself along a path matching the regular expression pi. While the satisfiability problem for the resulting logic LPDL was settled already in the 1980s, the decidability of its finite satisfiability problem has remained open ever since. The core difficulty is inherent to the finite setting: requiring and forbidding cycles at once is easily reconciled over arbitrary models, but over finite ones it defeats the existing finite-model-theoretic techniques. We make the first substantial progress towards closing this gap. We prove that finite satisfiability is ExpTime-complete for LPDL formulae (also in the presence of the converse operator) in negation normal form, under the restriction that every negated non-atomic loop has the form loop(pi^+) for some arbitrarily complex program pi -- a generalised form of self-reachability; positive occurrences of loops remain unrestricted. At the heart of our approach lies a novel way of representing intended finite models as their infinite, cactus-like unravellings: these are recognisable by two-way tree automata and satisfy a tailored omega-regular foldability condition that lets us finitise the accepted structures.

0.36

Decidability of Elementary Modal Logics is Undecidable

cs.LO ·2026-11-08 ·Jakub Michaliszyn
theory similarity 0.61
Abstract

We study the decidability of modal satisfiability over classes of Kripke frames defined by universal first-order sentences. Although some such classes yield undecidable satisfiability problems, decidability is guaranteed for wide families of frame conditions, including universal Horn sentences and universal sentences implying transitivity. A more than decade-old open problem asks a natural question: can decidable and undecidable cases be distinguished algorithmically? We prove that this is impossible, already for equality-free universal frame conditions over a single binary relation. More precisely, there is no algorithm that, given such a condition, decides whether its associated local modal satisfiability problem is decidable. We first establish the result for conditions with equality and then eliminate equality by passing to quotients of worlds with identical incoming and outgoing edges.

0.16

Tracking relevance syntactically: A nested approach to weak relevant logic

cs.LO ·2026-11-12 ·Fabio De Martin Polo, Han Gao
theory similarity 0.60
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

Extending SMT Solving with Non-Ground Clause Learning

cs.AI cs.LO ·2026-09-10 ·Yasmine Briefs, Christoph Weidenbach
theory similarity 0.60
Abstract · Extended version of LPAR 2026 paper

Quantifier instantiation is currently the main approach to non-ground SMT solving: solvers generate ground instances and solve the resulting ground SMT problems with CDCL(T)-style reasoning. When a conflict is found, conflict analysis learns only a ground clause, even though the conflict comes from instances of non-ground clauses. Yet non-ground reasoning can give exponentially shorter proofs than purely ground reasoning. We propose a calculus that consists of ground instantiations, CDCL(T)-style rules, and non-ground conflict analysis. The solver reasons on ground instances, but the resolution steps of conflict analysis are performed on their original non-ground clauses. This produces learned clauses that are typically more general than the ground conflict. With a suitable strategy, the learned clauses are even non-redundant. We also show how chronological backtracking can be included in SMT solving. Our calculus gives a common setting for CDCL(T)-style SMT solving, a range of instantiation-based procedures, and non-ground clause learning, and we prove that it simulates CDCL, SCL(FOL), SCL(T), and even Resolution.

0.14

Executable Specifications in Transition Algebra

cs.LO ·2026-11-04 ·Daniel Găină, Adrián Riesco, Ionuţ Ţuţu
similarity 0.60
Abstract

Transition Algebra can be viewed as an extension of many-sorted first-order logic by borrowing essential features from dynamic logic. This leads us to new, more expressive sentences that include transitions labelled with actions, which are built from terms using union, composition, and iteration operators. We define a suitable notion of Horn clause, develop a system of proof rules for reasoning about clauses, and subsequently show that the proof system is sound and complete. We then introduce a rewriting relation based on Horn clauses, capturing transitions along established paths expressed as actions. This rewriting relation is naturally extended to a narrowing procedure for solving queries, thereby laying foundation for logic programming in Transition Algebra. As usual, soundness for both rewriting and narrowing is straightforward, whereas completeness requires additional conditions. Finally, we provide a prototype tool that demonstrates the practical aspects and shows the effectiveness of the proposed method.

0.19