Cover Image

Hereditary First-Order Logic: the tractable quantifier prefix classes

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bodirsky, Manuel, Guzmán-Pro, Santiago
Format:	Preprint
Published:	2024
Subjects:	Logic Computational Complexity Discrete Mathematics Logic in Computer Science 03B16, 03B70, 03C13 F.1.3; F.4.1
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On the Computational Power of Extensional ESO
by: Bodirsky, Manuel, et al.
Published: (2025)

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

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

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

First-Order Fischer Servi Logic
by: Christensen, Ahmee
Published: (2024)

ProofCloud: A Proof Retrieval Engine for Verified Proofs in Higher Order Logic
by: Wang, Shuai
Published: (2024)

First-Order Coalition Logic
by: Catta, Davide, et al.
Published: (2025)

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

Local-Order-Invariant Logic on Classes of Bounded Degree
by: Aoki, Derek
Published: (2025)

Terminal Coalgebras and Non-wellfounded Sets in Homotopy Type Theory
by: Gylterud, Håkon Robbestad, et al.
Published: (2020)

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

Weihrauch problems as containers
by: Pradic, Cécilia, et al.
Published: (2025)

Normal forms in cubical type theory
by: Huang, Xu
Published: (2026)

Bennett's Conjecture in Lean 4: Counter-Models for the PSR-Reducibility of Spinoza's Propositions V and XIV
by: Nakamura, Yuki
Published: (2026)

Coalgebraic Satisfiability Checking for Arithmetic $μ$-Calculi
by: Hausmann, Daniel, et al.
Published: (2022)

A general approach to asymptotic elimination of aggregation functions and generalized quantifiers
by: Koponen, Vera, et al.
Published: (2023)

The Golden Path to Guarded Monotone Strict NP
by: Barsukov, Alexey, et al.
Published: (2023)

Two strong undefinability results in inquisitive and team semantics
by: Barbero, Fausto
Published: (2024)

DHoTT: A Temporal Extension of Homotopy Type Theory for Semantic Drift
by: Poernomo, Iman
Published: (2025)

ASP Chef grows Mustache to look better
by: Alviano, Mario, et al.
Published: (2025)

Univalent Material Set Theory
by: Gylterud, Håkon Robbestad, et al.
Published: (2023)

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

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

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

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

Strongly First Order Disjunctive Embedded Dependencies in Team Semantics
by: Galliani, Pietro
Published: (2025)

Proof-theoretic methods in quantifier-free definability
by: Kocsis, Zoltan A.
Published: (2023)

Extracting total Amb programs from proofs
by: Berger, Ulrich, et al.
Published: (2023)

On the expressive power of inquisitive epistemic logic
by: Ciardelli, Ivano, et al.
Published: (2023)

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

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

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

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

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

Proof Compression via Subatomic Logic and Guarded Substitutions
by: Barrett, Victoria, et al.
Published: (2025)

Nested Sequents for Intuitionistic Multi-Modal Logics: Modularity, Cut-Elimination, and Undecidability
by: Lyon, Tim S.
Published: (2025)

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

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

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)