Cover Image

Complexities of Well-Quasi-Ordered Substructural Logics

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Galatos, Nikolaos, Greati, Vitor, Ramanayake, Revantha, John, Gavin St.
Format:	Preprint
Published:	2025
Subjects:	Logic in Computer Science Computational Complexity Logic 03B47, 03F52, 03G10, 06F05, 68Q25, 08B15, 03D20, 68Q17 F.4.1; F.2.2; F.1.3
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Deducibility in the full Lambek calculus with weakening is HAck-complete
by: Greati, Vitor, et al.
Published: (2024)

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

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

Computing Distinguishing Formulae for Threshold-Based Behavioural Distances
by: Forster, Jonas, et al.
Published: (2026)

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

Do not throw out the baby: Clarithmetics as alternatives to weak arithmetics
by: Japaridze, Giorgi
Published: (2026)

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

Quantitative Linear Logic
by: Capucci, Matteo, et al.
Published: (2026)

A Logspace Constructive Proof of L=SL
by: Buss, Sam, et al.
Published: (2025)

From Gödel incompleteness to the consistency of circuit lower bounds
by: Atserias, Albert, et al.
Published: (2026)

The Solver's Paradox in Formal Problem Spaces
by: Rosko, Milan
Published: (2025)

Adversarial Barrier in Uniform Class Separation
by: Rosko, Milan
Published: (2025)

The Orientation Boundary for Step-Duplicating Recursors: Mechanized Impossibility, Escape, and Certification
by: Rahnama, Moses
Published: (2025)

Algebraic Proof Theory for Infinitary Action Logic
by: Fussner, Wesley, et al.
Published: (2025)

Labelled Well Quasi Ordered Classes of Bounded Linear Clique-Width
by: Lopez, Aliaume
Published: (2024)

Quantitative Graded Semantics and Spectra of Behavioural Metrics
by: Forster, Jonas, et al.
Published: (2023)

A correspondence between the time and space complexity
by: Latkin, Ivan V.
Published: (2023)

A declarative approach to specifying distributed algorithms using three-valued modal logic
by: Gabbay, Murdoch J., et al.
Published: (2025)

A proof complexity conjecture and the Incompleteness theorem
by: Krajicek, Jan
Published: (2023)

A Modular Lean 4 Framework for Confluence and Strong Normalization of Lambda Calculi with Products and Sums
by: Ramos, Arthur, et al.
Published: (2025)

Generalized Kantorovich-Rubinstein Duality beyond Hausdorff and Kantorovich
by: Wild, Paul, et al.
Published: (2025)

Extended Nullstellensatz proof systems
by: Krajicek, Jan
Published: (2023)

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

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

Continuous and algebraic domains in univalent foundations
by: de Jong, Tom, et al.
Published: (2024)

Reversible computations are computations
by: Aubert, Clément, et al.
Published: (2025)

Normalization properties of $λμ$-calculus using realizability semantics
by: Battyanyi, Peter, et al.
Published: (2023)

A Cut-Free Sequent Calculus for the Analysis of Finite-Trace Properties in Concurrent Systems
by: Fusco, Ludovico, et al.
Published: (2025)

Universal Gluing and Contextual Choice: Categorical Logic and the Foundations of Analytic Approximation
by: Santacana, Andreu Ballus
Published: (2025)

Insignificant Choice Polynomial Time: A Logic Capturing PTIME
by: Schewe, Klaus-Dieter
Published: (2020)

Arithmetics within the Linear Time Hierarchy
by: Pollett, Chris
Published: (2025)

Computability of Initial Value Problems
by: Brattka, Vasco, et al.
Published: (2024)

Encoding Argumentation Frameworks to Propositional Logic Systems
by: Tang, Shuai, et al.
Published: (2025)

On the Various Translations between Classical, Intuitionistic and Linear Logic
by: Ferreira, Gilda, et al.
Published: (2024)

A Bisimulation-Invariance-Based Approach to the Separation of Polynomial Complexity Classes
by: Bruse, Florian, et al.
Published: (2026)

Matching logic -- a new axiomatization
by: Leuştean, Laurenţiu, et al.
Published: (2025)

Notes on applicative matching logic
by: Leuştean, Laurenţiu
Published: (2025)

Provability in BI's Sequent Calculus is Decidable
by: Gheorghiu, Alexander, et al.
Published: (2021)

Undecidability in Relevant Logic
by: Knudstorp, Søren Brinck
Published: (2026)

The Fractal Logic of Phi-adic Recursion
by: Rosko, Milan
Published: (2025)