Cover Image

Deducibility in the full Lambek calculus with weakening is HAck-complete

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Greati, Vitor, Ramanayake, Revantha
Format:	Preprint
Published:	2024
Subjects:	Logic in Computer Science Computational Complexity Logic 03B47 F.4.1; F.2.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Hypersequent Calculi Have Ackermannian Complexity
by: Balasubramanian, A. R., et al.
Published: (2026)

Complexities of Well-Quasi-Ordered Substructural Logics
by: Galatos, Nikolaos, et al.
Published: (2025)

Predicative Ordinal Recursion on the Constructive Veblen Hierarchy
by: Tabatabai, Amirhossein Akbar, et al.
Published: (2025)

Finite Hilbert systems for Weak Kleene logics
by: Greati, Vitor, et al.
Published: (2024)

Axiomatizing the Logic of Ordinary Discourse
by: Greati, Vitor, et al.
Published: (2024)

Propositional Dynamic Logic has Craig Interpolation: a tableau-based proof
by: Borzechowski, Manfred, et al.
Published: (2025)

Generating proof systems for three-valued propositional logics
by: Greati, Vitor, et al.
Published: (2024)

Conjunctive categorial grammars and Lambek grammars with additives
by: Kuznetsov, Stepan L., et al.
Published: (2024)

Complexity Results in Team Semantics: Nonemptiness Is Not So Complex
by: Anttila, Aleksi, et al.
Published: (2025)

The logic of bunched implications is undecidable
by: Galatos, Nick, et al.
Published: (2026)

Complexity of Nonassociative Lambek Calculus with classical logic
by: Płaczek, Paweł
Published: (2024)

On the Satisfaction Probabilities of $k$-CNF Formulas
by: Tantau, Till
Published: (2022)

Relational Models for the Lambek Calculus with Intersection and Constants
by: Kuznetsov, Stepan L.
Published: (2022)

Constant time testability of first-order logic with modulo counting on finitary graphs
by: Adler, Isolde, et al.
Published: (2026)

A Proof-Theoretic Approach to the Semantics of Classical Linear Logic
by: Barroso-Nascimento, Victor, et al.
Published: (2025)

A Theory for Probabilistic Polynomial-Time Reasoning
by: Chen, Lijie, et al.
Published: (2026)

The Fluted Fragment with Transitive Relations
by: Pratt-Hartmann, Ian, et al.
Published: (2020)

A Note on the Complexity of the Satisfiability Problem for Graded Modal Logics
by: Kazakov, Yevgeny, et al.
Published: (2009)

Unravelling Abstract Cyclic Proofs into Proofs by Induction
by: Grotenhuis, Lide, et al.
Published: (2026)

Three Fixed-Dimension Satisfiability Semantics for Quantum Logic: Implications and an Explicit Separator
by: Higuchi, Joaquim Reizi
Published: (2026)

Thoughts on sub-Turing interactive computability
by: Japaridze, Giorgi
Published: (2024)

Coinductive proof search for polarized logic with applications to full intuitionistic propositional logic
by: Santo, José Espírito, et al.
Published: (2020)

What If Turing Had Preceded Gödel?
by: Oberhoff, Sebastian
Published: (2024)

Glivenko's theorems from an ecumenical perspective
by: Pereira, Luiz Carlos, et al.
Published: (2026)

Semi-Substructural Logics à la Lambek
by: Wan, Cheng-Syuan
Published: (2024)

A propositional cirquent calculus for computability logic
by: Japaridze, Giorgi
Published: (2024)

The Directed Van Kampen Theorem in Lean
by: Basold, Henning, et al.
Published: (2023)

Axiomatization of approximate exclusion
by: Häggblom, Matilda
Published: (2024)

Inclusion with repetitions and Boolean constants -- implication problems revisited
by: Häggblom, Matilda
Published: (2025)

Axiomatizing approximate inclusion
by: Häggblom, Matilda
Published: (2025)

How to play the Accordion: Uniformity and the (non-)conservativity of the linear approximation of the λ-calculus (extended version)
by: Cerda, Rémy, et al.
Published: (2023)

Internal Effectful Forcing in System T
by: Escardo, Martin H., et al.
Published: (2025)

Polynomial-time Tractable Problems over the $p$-adic Numbers
by: Fehm, Arno, et al.
Published: (2025)

On the existence of strong proof complexity generators
by: Krajicek, Jan
Published: (2022)

Discernment is all you need
by: Fuenmayor, David
Published: (2026)

Structure-Guided Automated Reasoning
by: Bannach, Max, et al.
Published: (2023)

A Coherence Construction for the Propositional Universe
by: Huang, Xu
Published: (2024)

Agent Interpolation for Knowledge
by: Bílková, Marta, et al.
Published: (2025)

Knowability as continuity: a topological account of informational dependence
by: Baltag, Alexandru, et al.
Published: (2024)

Reasoning Around Paradox with Grounded Deduction
by: Ford, Bryan
Published: (2024)