Logic in Computer Science
See recent articles
Showing new listings for Monday, 16 November 2026
- [1] arXiv:2611.17618 [pdf, html, other]
-
Title: Lean-PEP: Performance-Estimation Certificates to Formally Verified Algorithmic BoundsComments: 26 pages, 2 figures, 8 tablesSubjects: Logic in Computer Science (cs.LO)
Performance-estimation certificates describe worst-case bounds for optimization algorithms. Turning a certificate into a formal theorem requires exact verification of its algebra and a connection between its coordinates, constraints and objective and the intended function-level problem. Lean-PEP provides a reusable interface for this task. It checks a submitted source and exact certificate against a supported canonical finite model, and a parameterized analytic theorem transfers the resulting finite bound to every admissible algorithm trajectory. Generated computation proofs discharge the obligations that depend on each certificate. An additional capture entry checks the numerical record and reconstruction policy. The implemented two-step proximal-gradient consumer verifies a new input with normalized bound 62500/499999, and a fixed eight-configuration batch yields seven distinct payloads with accepted certificates and executed Lean proofs. PG/GD cases and one-step attainment witnesses establish the corresponding algorithmic conclusions, and a fresh installation reproduces consumption of the supplied input. These results show how new certificate data can reuse a proved analytic interface to obtain function-level bounds within the supported models.
- [2] arXiv:2611.17866 [pdf, html, other]
-
Title: Active Learning of Temporal Specifications through Distinguishing QueriesSubjects: Logic in Computer Science (cs.LO); Artificial Intelligence (cs.AI)
Temporal specifications are essential for verification and monitoring, yet writing formulas that capture the intended behaviour is difficult. Active learning derives such specifications through interaction between a learner and a teacher, but remains underexplored for temporal logics. Existing approaches require the teacher to answer equivalence queries and to construct counterexamples, and they often rely on SAT-based learning procedures that restart the search after each new example. We present an active-learning framework for LTLf in which the teacher only labels traces and answers natural-language questions about the intended behaviour. The learner maintains an enumerated version space of candidate formulas, generates traces that distinguish candidates, and uses the teacher's hints to rank candidates or to restrict the search. We prove consistency with the observed examples, identification within bounded hypothesis classes with a bound on the number of queries, and a PAC guarantee for the final hypothesis. In experiments with a simulated teacher on 36 targets, including targets in four standard environments, the learner identifies every target when it compares all rivals, with fewer than seven queries beyond an initial sample of ten traces on average. Correct hints reduce the number of queries by up to 16% and the number of generated candidates by a fifth, and hints used for ranking never prevent identification, even when incorrect. Our enumeration-based version space is faster than the SAT-based approach of previous learners at every target size.
- [3] arXiv:2611.18017 [pdf, html, other]
-
Title: On Structure-Aware SAT SolvingSubjects: Logic in Computer Science (cs.LO)
Although modern SAT solvers have made remarkable progress, they still exploit formula structure only to a limited extent. We present two techniques that make SAT solving more structure-aware and provide experimental results showing their promise. The first technique ``$\mathit{melts}$'' the formula by reducing interaction between its parts. This is achieved by adding new variables, using existential quantifiers, and applying a procedure called partial quantifier elimination. The second technique exploits the notion of a $\mathit{local}$ $\mathit{proof}$. The latter establishes that a formula is unsatisfiable by proving that certain literals of its clauses are redundant. We show that using local proofs makes SAT solving more formula-specific.
- [4] arXiv:2611.18132 [pdf, html, other]
-
Title: Parameterized Weakest-Precondition Calculus for Fine-grained Properties of Quantum LoopsComments: 56 pages, 4 figuresSubjects: Logic in Computer Science (cs.LO); Programming Languages (cs.PL)
Quantum loops may execute arbitrarily many iterations, and understanding their runtime behavior requires knowing how often they terminate, how long terminating runs take, and how common very long runs are. We develop a compositional weakest-precondition framework for analyzing these properties on possibly infinite-dimensional state spaces. It uses parameterized predicates: families of quantum effects indexed by a positive observation scale. These families retain runtime information even when the expected runtime is infinite and can be reused through sequential composition and nested loops. We prove that weakest-precondition equations for loops have unique solutions in the parameterized predicate domain. From the asymptotic behavior of the derived weakest preconditions, we then recover these runtime properties and quantify the influence of very long terminating executions. For the classic discrete-time quantum walk on the one-dimensional infinite line with one absorbing boundary at the origin and the Hadamard gate as its coin operator, we verify its termination probability $2/\pi$, conditional mean $\pi/2$, and logarithmic growth of the conditional capped second moment. We then reuse the walk's specification to verify the termination probability and conditional mean runtime of an outer loop that repeatedly invokes it.
- [5] arXiv:2611.18147 [pdf, html, other]
-
Title: Evidence-Carrying Transport Across EffectsSubjects: Logic in Computer Science (cs.LO)
A program logic proved sound against one effectful semantics need not remain sound when the effect is re-implemented, yet the semantic relationship between reasoning before and after a change of effect is usually left implicit and re-established by hand. This paper provides a uniform, proof-relevant account of it. Working in realizability, where a notion of computation determines a model whose entailments carry explicit program evidence, we introduce simulations between effectful realizability cores, generalizing Longley's applicative morphisms to computation over an arbitrary strong monad. A single simulation transports the source logic along a ladder: it induces a morphism of the associated evidenced frames and, functorially, of the induced triposes. These passages are $2$-fully-faithful, so the three levels agree and a change of effect carries the entire higher-order program logic together with the evidence witnessing each derivation. A computationally dense simulation moreover computes a modality on the source logic, a nucleus through which the transport factors and which marks exactly the reasoning stable under the change, read off from the translation rather than postulated. This recovers known examples such as the double-negation modality of classical realizability, and examples such as sheafification arise from a modal refinement of the construction. Overall, the framework makes a change of effect a first-class object, one that can be composed, factored through its modality, and shown in cases not to exist, opening a path to transporting verified reasoning across effects.
- [6] arXiv:2611.18169 [pdf, html, other]
-
Title: The QBF Gallery 2026Comments: Open access versionSubjects: Logic in Computer Science (cs.LO)
The QBF Gallery 2026 is the latest evaluation event of (dependency) quantified Boolean formula (QBF) solving technology. Its goal is to assess the current state-of-the-art, enable the evaluation of novel solvers on newly curated benchmark instances and present the progress made since the previous competition. This report discusses the solvers, instances and tools submitted by the community and introduces new benchmark collections for evaluation. We evaluate solvers in three tracks, reflecting most common input formats in (dependency) QBF solving. In addition to those main evaluations, we investigate effects of preprocessing and include a track of new crafted benchmark families.
The results are analyzed using various metrics and complementary statistics on solver similarities, different memory limitations and performance across formula families. Finally, the dedicated benchmarks for each track are made available as an artifact to support future research and reproducible evaluation. - [7] arXiv:2611.18175 [pdf, html, other]
-
Title: Safety Analysis of Parameterized Networks with Shared CountersSubjects: Logic in Computer Science (cs.LO)
We study networks with an unbounded number of processes sharing some natural counters that can be decremented, incremented and tested to zero. We look at two safety problems: the first one asks whether there is a network with an execution bringing a process in a given final state and the other one asks the execution to bring all the processes in the final state. In their full generality, these two problems are undecidable, but we show that decidability can be regained by either using a single counter or by forbidding the use of zero-tests (as it is is the case in Vector Addition Systems with States). For these decidable cases, we obtain low complexity results, the problems being solvable either in non-deterministic logarithmic space or in polynomial time.
New submissions (showing 7 of 7 entries)
- [8] arXiv:2611.17742 (cross-list from cs.FL) [pdf, html, other]
-
Title: Analysing Busy Beaver Machines (Or How to Find Ossified Ocelots)Subjects: Formal Languages and Automata Theory (cs.FL); Logic in Computer Science (cs.LO)
The busy beaver problem involves working with machines which can produce very large numbers, both for the output of certain Turing machines and for the number of steps taken to execute them. Given that these numbers can involve thousands of digits, it is crucial to have a means of proving properties of the relevant machines which allow manipulation of such large numbers. In this paper we introduce the notion of \textit{shape computations} as a means of isolating key properties that allow efficient execution of the relevant Turing machines based on verifiable properties of state transitions. In particular, this notion allows us to provide an analytical result which demonstrates the quadratic relationship between the size of the output and the number of steps required to generate it. We have also developed an initial implementation of our approach, and we provide empirical evaluation of it on a suite of 240 example machines.
- [9] arXiv:2611.17884 (cross-list from math.LO) [pdf, html, other]
-
Title: HOL in HOL: mechanized soundness, completeness and consistency, with and without infinityChristoph Benzmüller (Otto-Friedrich-Universität Bamberg and Freie Universität Berlin), Daniel Kirchner (Otto-Friedrich-Universität Bamberg)Comments: 23 pages, 1 figure. Formal proof artifacts: Archive of Formal Proofs entries HOL_in_HOL_Deep and HOL_in_HOL_Deep_Infinity_ZFC (Isabelle2026). SubmittedSubjects: Logic (math.LO); Logic in Computer Science (cs.LO)
What can a logic certify about a copy of itself? For Church's simple theory of types, formalized as a deep embedding in Isabelle/HOL with Henkin semantics and a natural-deduction calculus, the answer has two tiers. On the first tier, plain Isabelle/HOL certifies the logic without an axiom of infinity, by a standard model with one individual. On the second tier, the logic with a Dedekind-style axiom of infinity is certified only in Isabelle/HOL extended by a large enough set-theoretic universe. Both tiers appear in Harrison's self-verification of HOL Light. What the present formalization adds is Henkin completeness, and with it a semantics that matches the calculus exactly, compactness and model existence on the first tier, and the boundary between the tiers. Comparing two ways of adding infinity to the object logic shows where the boundary lies. One is an infinite domain of individuals, expressed by the first-order sentences "there are at least $n$ individuals", each of which has a finite model; the other is the Dedekind axiom, a single sentence with no finite model, and there the first tier ends. In the calculus the axiom is strictly stronger than the sentences together: it derives each of them, but they do not derive it. The witness is a countable Henkin model in which every sentence holds and the axiom fails, because its function domain is too sparse for an injective, non-surjective self-map. On the second tier, the universe serves one purpose only: to prove the Dedekind axiom consistent. Everything that follows, completeness and even the countable Henkin model of the axiom, is obtained in plain Isabelle/HOL. The universe axiom is Harrison-style, realized in Paulson's ZFC_in_HOL with the domain of every type in $V_{\omega+\omega}$; with it, full classical higher-order logic with infinity and relational choice is consistent relative to set theory.
- [10] arXiv:2611.17937 (cross-list from cs.AI) [pdf, html, other]
-
Title: Tracing Actual Causes with Counterfactual Witness MapsComments: Accepted at NeurIPS 2026 (Main Track)Subjects: Artificial Intelligence (cs.AI); Logic in Computer Science (cs.LO)
Halpernian actual causation, the formal study of which events in a specific situation caused a specific outcome in acyclic structural causal models, underpins legal responsibility, moral blame, and the assessment of causal harm. Despite the rich logical framework, no prior sound and complete enumeration procedure is known for finding all actual causes in a given setting, blocking downstream tasks such as responsibility attribution, blame assessment, and causal-harm grading that aggregate over the full cause set. We close this gap by introducing witness targets: sets of joint configurations containing every counterfactual witness. In combination with an ancestor intervention grammar we derive a finite directed acyclic witness map. We prove that for every actual cause there exists a contingency set such that the joint intervention set appears as a node of this map, and present an algorithm for Tracing Actual Causes (TrAC) that is sound and complete for enumerating all actual causes of any target event. We compare TrAC empirically with existing single-cause baselines on random Boolean structural causal models, demonstrating practical feasibility for graphs of up to 15 nodes.
- [11] arXiv:2611.18369 (cross-list from cs.DS) [pdf, html, other]
-
Title: How rigid is maximum cardinality search? Stability and locality of MCS orderings under edge updates, verified in LeanComments: 14 pages, 1 table. Code and proofs: this https URL . Palomar registry: PALOMAR-2026-10-04-000009Subjects: Data Structures and Algorithms (cs.DS); Logic in Computer Science (cs.LO)
For which sets F of edge modifications do a graph G and the modified graph share a maximum cardinality search (MCS) ordering? We prove that they do whenever, along every proper common MCS prefix, each unchosen vertex's neighbour count in the second graph exceeds its count in the first by zero or one. In particular, inserting or deleting any matching, or flipping a single edge, preserves a common ordering, and under the same hypothesis every common MCS prefix extends to a full common ordering without backtracking. Neither part of the hypothesis can simply be dropped: inserting a triangle, a P_4 or a 2P_3 shows that the +1 bound cannot be relaxed to +2, and a disjoint mixed insert/delete pair shows that the one-directional condition is needed. For the canonical ordering (smallest-index tie-breaking) under a single-edge update, an insertion can first change the ordering only strictly between the endpoints' positions, and a deletion only at the later endpoint; when no break fires, the ordering is unchanged. A boolean-adjacency executable refines the abstract probe-then-repair update. All of these results, including the four obstructions, are proved in Lean 4 over Mathlib, re-checked by independent kernel checkers, and registered in the Palomar registry. On paper we further show that the first break of an insertion is located in O((deg(v)+1) log n) time, independent of the window length. We claim no worst-case asymptotic speedup over recomputation.
- [12] arXiv:2611.18541 (cross-list from math.RA) [pdf, html, other]
-
Title: No free lattice contains an infinite ascending chain of copies of FL(3)Comments: 59 pages, 13 figures; the main theorem is checked in Agda; the formal development is available at this https URLSubjects: Rings and Algebras (math.RA); Logic in Computer Science (cs.LO); Group Theory (math.GR); Logic (math.LO)
No free lattice contains an infinite strictly ascending chain of sublattices isomorphic to FL(3), the free lattice on three generators; this answers a question that R. A. Dean asked and the second author's 1997 notes on the problem left open. Every such chain would yield, inside FL(3), a coherent chain of proper self-embeddings $\Theta_0, \Theta_1, \Theta_2, \dots$ with $\Theta_k \circ \Theta_j = \Theta_j$ for $j < k$, so that each later embedding fixes the image of each earlier one pointwise. Every proper self-embedding of FL(3) whose fixed sublattice contains a free generating triple fixes one of the three generators, say $z$, because a power of it or of its dual lies above the identity, and a self-embedding that moves every generator and lies above the identity fixes at most eleven elements. Up to duality, a proper self-embedding fixing the image of such a $\Theta_1$ pointwise fixes only elements above $z \wedge (x \vee y)$, where no free generating triple containing $z$ can lie. We also verify the one-step example of the 1997 notes, prove that no step toward such a chain is self-similar, and show that the configuration the argument rules out at length three does occur at length two.
Without freeness the answer reverses: FL(3) contains an infinite strictly ascending chain of 3-generated sublattices, so the lattice analogue of Takahasi's chain condition for free groups fails. The theorem itself is checked by the Agda proof assistant under its safe flags, for free lattices over generators with decidable equality, and its formal proof uses no classical principle: finite searches and an induction on a finite set replace the infinite pigeonhole principle by which a chain yields a coherent chain.
Cross submissions (showing 5 of 5 entries)
- [13] arXiv:2502.02220 (replaced) [pdf, other]
-
Title: On the Existential Theory of the Reals Enriched with Integer Powers of a Computable NumberSubjects: Logic in Computer Science (cs.LO)
This paper investigates $\exists\mathbb{R}(r^{\mathbb{Z}})$, that is the extension of the existential theory of the reals by an additional unary predicate $r^{\mathbb{Z}}$ for the integer powers of a fixed computable real number $r > 0$. If all we have access to is a Turing machine computing $r$, it is not possible to decide whether an input formula from this theory satisfiable. However, we show an algorithm to decide this problem when: 1. $r$ is known to be transcendental, or 2. $r$ is a root of some given integer polynomial (that is, $r$ is algebraic). In other words, knowing the algebraicity of $r$ suffices to circumvent undecidability. Furthermore, we establish complexity results under the proviso that $r$ enjoys what we call a polynomial root barrier. Using this notion, we show that the satisfiability problem of $\exists\mathbb{R}(r^{\mathbb{Z}})$ is 1. in NEXPTIME if $r$ is a natural number, 2. in EXPSPACE if $r$ is an algebraic number, and 3. in 3EXP if $r$ belongs to a family of transcendental numbers including $Ï€$ and Euler's $e$. As a by-product of our results, we are able to remove the appeal to Schanuel's conjecture from the proof of decidability of the entropic risk threshold problem for stochastic games with rational probabilities, rewards and threshold [Baier et al., MFCS'23]: when the base of the entropic risk is Euler's $e$ and the aversion factor is a fixed algebraic number, the problem is in EXP.
- [14] arXiv:2503.04759 (replaced) [pdf, html, other]
-
Title: Games with $ω$-Automatic Preference RelationsComments: Extended version of a MFCS 2025 paperSubjects: Logic in Computer Science (cs.LO); Computer Science and Game Theory (cs.GT)
This paper investigates Nash equilibria (NEs) in multi-player turn-based games on graphs, where player preferences are modeled as $\omega$-automatic relations via deterministic parity automata. Unlike much of the existing literature, which focuses on specific reward functions, our results apply to any preference relation definable by an $\omega$-automatic relation. We analyze the computational complexity of determining the existence of an NE (possibly under some constraints), verifying whether a given strategy profile forms an NE, and checking whether a specific outcome can be realized by an NE. When a (constrained) NE exists, we show that there always exists one with finite-memory strategies. Finally, we explore fundamental properties of $\omega$-automatic relations and their implications for the existence of equilibria.
- [15] arXiv:2605.13348 (replaced) [pdf, html, other]
-
Title: Adequate Losses via Quantitative Linear LogicComments: Numerous tweaks and small corrections. To appear at POPL 2027Subjects: Logic in Computer Science (cs.LO); Logic (math.LO)
As neural components are increasingly embedded in existing symbolic software -- including safety-critical systems -- the question arises of how to specify and enforce the safety of the newly introduced neural parts. Unlike traditional logical specifications, these must be amenable not only to the standard Boolean interpretation, but also to training and optimisation. The latter calls for a quantitative interpretation of the logical syntax, subject to further requirements such as smoothness and differentiability. Moreover, the qualitative and quantitative sides of the logic must share a unifying proof-theoretic and categorical semantics. Finally, the new logic should link cleanly to the substructural and program logics that underpin the verification of existing symbolic programs. In this paper, we present a logic that ticks all of these boxes. We introduce a family of calculi, $p$QLL, indexed by a hardness degree $p$, prove a cut-elimination theorem for them, and establish completeness with respect to enriched residuated `soft' lattices. At $p = \infty$, $p$QLL reduces to multiplicative additive linear logic (MALL), and provability in $p$QLL converges to provability in MALL as $p \to \infty$. We express optimisation objectives in the syntax of this logic and prove the quantitative adequacy of neuro-symbolic loss functions -- a result that has eluded the neuro-symbolic machine learning community for nearly a decade.
- [16] arXiv:2608.02596 (replaced) [pdf, html, other]
-
Title: Staying Productive Under the Palm Trees: On Graded Coeffect Typing in the Tropical SemiringSubjects: Logic in Computer Science (cs.LO); Programming Languages (cs.PL)
We give a temporal reading of graded coeffects: tropical grades carry guards on infinite computation. To illustrate it, we first define $G_T$, a polymorphic calculus with guarded recursive types that guarantees productive infinite computation, in the form of hereditary head normalisation. The calculus supports stream computing via the Scott encoding, and embeds Nakano's later modality. We then introduce $I_T$, a graded intersection type system with guarded infinitary types for the pure {\lambda}-calculus, whose typability allows for an exact characterisation of hereditary head normalisation. We prove that the characterising typability predicate is $\Pi_0^2$, matching the recursion-theoretic complexity of the characterised property.
- [17] arXiv:2610.16473 (replaced) [pdf, other]
-
Title: Some complete $ω$-powers of a one-counter language in the difference hierarchyJacques Duparc (UNIL), Olivier Finkel (IMJ-PRG (UMR\_7586)), Dominique Lecomte (IMJ-PRG (UMR\_7586))Subjects: Logic in Computer Science (cs.LO); Computation and Language (cs.CL); Formal Languages and Automata Theory (cs.FL); Computer Science and Game Theory (cs.GT); General Topology (math.GN); Logic (math.LO)
Fix a finite alphabet $\Sigma$ having at least two letters, and natural numbers $n,k\geq 1$. We denote by $D_n(\mathbf{\Pi}^0_k)$ the class of differences of $n$ subsets of the Cantor space $\Sigma^\omega$ in $\mathbf{\Pi}^0_k$, and by $D^-_n(\mathbf{\Pi}^0_k)$ the class of complements of sets in $D_n(\mathbf{\Pi}^0_k)$. We prove, for any natural numbers $n,k\geq 1$, the existence of a finite alphabet $\Sigma$ having at least two letters and a finitary language $U_{n,k}$ over $\Sigma$ accepted by a one-counter automaton such that the $\omega$-power $$U_{n,k}^\infty:=\{ w_0w_1\cdots\in\Sigma^\omega\mid\forall i\in\omega ~~w_i\in U_{n,k}\}$$ is $D_{2n-1}(\mathbf{\Pi}^0_k)$-complete. We also prove a conditional result for the dual classes $D^-_{2n}(\mathbf{\Pi}^0_k)$: under the assumption that there exists a finitary language $V_{n,3}$ accepted by a one-counter automaton, such that its $\omega$-power $V_{n,3}^\infty$ is $D^-_{2n}(\mathbf{\Pi}^0_3)$-complete, there would also exist, for any integer $k > 3$, a finitary language $V_{n,k}$ accepted by a one-counter automaton, such that its $\omega$-power $V_{n,k}^\infty$ is $D^-_{2n}(\mathbf{\Pi}^0_k)$-complete. Finally we add another conditionnal result about Wadge degrees of rational $\mathbf{\Delta}^0_2$ omega powers, which completes the recent results of [FGL26].
- [18] arXiv:2611.16509 (replaced) [pdf, other]
-
Title: Sound Automatic Lock Placement for Concurrent Programs with PointersComments: 39 pages, 7 figuresSubjects: Logic in Computer Science (cs.LO)
We propose a lightweight method for automatic lock placement in concurrent POSIX programs with explicit pointer manipulation, such as C programs. Given a program that lacks sufficient user-placed mutexes, or contains none at all, our method introduces new mutexes to prevent data races. The method is formally proven to guarantee the absence of data races and mainly consists of three steps. The first step performs lockset analysis and may-happen-in-parallel analysis. The second step conducts a concurrent points-to analysis derived from a Steensgaard-like procedural analysis, where per-thread points-to graphs are unified using a special completion rule. The final step places locks to prevent data races while respecting a lock ordering to avoid deadlocks. In addition, user-annotated critical sections are protected through insertion of dedicated locks. Since lock placement is a complex and error-prone task, our method aims at helping developers write correct concurrent programs.
- [19] arXiv:2101.00834 (replaced) [pdf, html, other]
-
Title: Symbolic Control for Stochastic Systems via Finite Parity GamesJournal-ref: Majumdar, R., Mallik, K., Schmuck, A.K. and Soudjani, S., 2024. Symbolic control for stochastic systems via finite parity games. Nonlinear Analysis: Hybrid Systems, 51, p.101430Subjects: Systems and Control (eess.SY); Logic in Computer Science (cs.LO)
We consider the problem of computing the maximal probability of satisfying an omega-regular specification for stochastic nonlinear systems evolving in discrete time. The problem reduces, after automata-theoretic constructions, to finding the maximal probability of satisfying a parity condition on a (possibly hybrid) state space. While characterizing the exact satisfaction probability is open, we show that a lower bound on this probability can be obtained by (I) computing an under-approximation of the qualitative winning region, i.e., states from which the parity condition can be enforced almost surely, and (II) computing the maximal probability of reaching this qualitative winning region. The heart of our approach is a technique to symbolically compute the under-approximation of the qualitative winning region in step (I) via a finite-state abstraction of the original system as a 2.5-player parity game. Our abstraction procedure uses only the support of the probabilistic evolution; it does not use precise numerical transition probabilities. We prove that the winning set in the abstract 2.5-player game induces an under-approximation of the qualitative winning region in the original synthesis problem, along with a policy to solve it. By combining these contributions with (a) a symbolic fixpoint algorithm to solve 2.5-player games and (b) existing techniques for reachability policy synthesis in stochastic nonlinear systems, we get an abstraction-based algorithm for finding a lower bound on the maximal satisfaction probability. We have implemented the abstraction-based algorithm in Mascot-SDS (Majumdar et al., 2020), where we combined the outlined abstraction step with our recent tool FairSyn. We evaluated our implementation on the nonlinear model of a perturbed bistable switch from the literature. We outperform a recently proposed tool for solving this problem by a large margin.
- [20] arXiv:2601.21843 (replaced) [pdf, html, other]
-
Title: The Leibniz adjunction in homotopy type theory, with an application to simplicial type theoryComments: v4: Corrected links to Agda HTML. To appear at CSL 2027Subjects: Category Theory (math.CT); Logic in Computer Science (cs.LO); Logic (math.LO)
Simplicial type theory extends homotopy type theory and equips types with a notion of directed morphisms. A Segal type is defined to be a type in which these directed morphisms can be composed. We show that all higher coherences can be stated and derived if simplicial type theory is taken to be homotopy type theory with a postulated interval type. In technical terms, this means that if a type has unique fillers for $(2,1)$-horns, it has unique fillers for all inner $(n,k)$-horns. This generalizes a result of Riehl and Shulman for the case $n = 3, k \in \{1, 2\}$. Our main technical tool is the Leibniz adjunction: the pushout-product is left adjoint to the pullback-hom in the wild category of types. While this adjunction is well known for ordinary categories, it is much more involved for higher categories, and the fact that it can be proved for the wild category of types (a higher category without stated higher coherences) is non-trivial. We make profitable use of the equivalence between the wild category of maps and that of families. We have formalized the results in Cubical Agda.
- [21] arXiv:2605.10005 (replaced) [pdf, html, other]
-
Title: Hybrid Mechanical and Agentic Specification InferenceSubjects: Programming Languages (cs.PL); Artificial Intelligence (cs.AI); Logic in Computer Science (cs.LO); Software Engineering (cs.SE)
Adoption of formal verification has long been hindered by the cost of manual specification. To prove high-level properties, one must also write contracts for supporting functions, many of which are mechanical and low-level. Specification inference automatically derives such contracts from the program. We present a hybrid of mechanical and agentic inference for Move, a smart contract language, integrated into its verifier, the Move Prover. A large language model (LLM) agent drives inference and verification through a tool that calls the Move Prover and derives specifications from code by weakest-precondition (WP) analysis. We evaluate our approach on 26 targets, 24 of them extracted from public Move functions of the Aptos framework that have no specifications, under a frontier model and a mid-tier model of the same family (Sol 5.6 and Terra 5.6). With and without WP, the agent completes over 90% of its runs, so agentic inference is effective on its own. Adding WP lowers its cost by 11-21% overall and by 40-64% on targets without loops.
- [22] arXiv:2610.29771 (replaced) [pdf, html, other]
-
Title: Logics vs doctrines, a mirror symmetryComments: Corrected minor mistakes and introduced the notion of tightness in Section 5Subjects: Category Theory (math.CT); Logic in Computer Science (cs.LO); Logic (math.LO)
We study the relationship between doctrines, encoding 2-categories of theories in predicate logic, and fragments of geometric logic, defined through Kan injectivity in the 2-category of topoi. After a brief historical account of the notion of doctrine, we propose our working definition. Our main result then establishes a Galois connection between doctrines and subgeometric logics. This connection suggests a mirror symmetry between the world of doctrines and the world of logics, in which constructions and results on either side admit counterparts on the other. We develop this symmetry through constructions of syntactic categories and classifying topoi in both settings, recovering the familiar examples from categorical logic. We prove paired Diaconescu-type theorems and give symmetric descriptions of the two closure operators induced by the Galois connection. Finally, we characterise when passing from a doctrine to its closure induces a reflection between the corresponding 2-categories of algebras, and we relate this reflection to conceptual completeness.