Cover Image

A Characterization of Basic Feasible Functionals Through Higher-Order Rewriting and Tuple Interpretations

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Baillot, Patrick, Lago, Ugo Dal, Kop, Cynthia, Vale, Deivid
Format:	Preprint
Published:	2024
Subjects:	Logic in Computer Science Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Higher-Order Constrained Dependency Pairs for (Universal) Computability
by: Guo, Liye, et al.
Published: (2024)

Reasonable Space for the $λ$-Calculus, Logarithmically
by: Accattoli, Beniamino, et al.
Published: (2022)

Flexible Type-Based Resource Estimation in Quantum Circuit Description Languages
by: Colledan, Andrea, et al.
Published: (2024)

Templates in Rewriting Induction
by: Hagens, Kasper, et al.
Published: (2026)

Bounded Rewriting Induction for LCSTRSs
by: Hagens, Kasper, et al.
Published: (2026)

Linearization via Rewriting (Long Version)
by: Lago, Ugo Dal, et al.
Published: (2025)

Feasibly Constructive Proof of Schwartz-Zippel Lemma and the Complexity of Finding Hitting Sets
by: Atserias, Albert, et al.
Published: (2024)

On Higher Order Busy Beaver Function
by: Cao, Zining
Published: (2025)

A weakly monotonic, logically constrained, HORPO-variant
by: Kop, Cynthia
Published: (2024)

Functional variant of Polynomial Analogue of Gandy's Fixed Point Theorem
by: Nechesov, Andrey
Published: (2024)

The Power of Negation in Higher-Order Datalog
by: Charalambidis, Angelos, et al.
Published: (2025)

On the Complexity of the Skolem Problem at Low Orders
by: Bacik, Piotr, et al.
Published: (2025)

The Complexity and Expressive Power of Second-Order Extended Logic
by: Feng, Shiguang, et al.
Published: (2022)

From Time to Space: The Impact of Linearity in Higher-Order Datalog
by: Charalambidis, Angelos, et al.
Published: (2026)

On Higher-Order Probabilistic Verification via the Weighted Relational Model of Linear Logic
by: Lago, Ugo Dal, et al.
Published: (2026)

On the Number of Quantifiers Needed to Define Boolean Functions
by: Carmosino, Marco, et al.
Published: (2024)

Characterizing Small Circuit Classes from FAC^0 to FAC^1 via Discrete Ordinary Differential Equations
by: Antonelli, Melissa, et al.
Published: (2025)

$Π_{2}^{P}$ vs PSpace Dichotomy for the Quantified Constraint Satisfaction Problem
by: Zhuk, Dmitriy
Published: (2024)

Proof Complexity of Linear Logics
by: Tabatabai, Amirhossein Akbar, et al.
Published: (2026)

An order out of nowhere: a new algorithm for infinite-domain CSPs
by: Mottet, Antoine, et al.
Published: (2023)

The Proof Analysis Problem
by: Arteche, Noel, et al.
Published: (2025)

Proof complexity of positive branching programs
by: Das, Anupam, et al.
Published: (2021)

Parallelism and Adaptivity in Student-Teacher Witnessing
by: Ježil, Ondřej, et al.
Published: (2026)

Effective Versions of Strong Measure Zero
by: Rayman, Matthew
Published: (2025)

The complete classification for quantified equality constraints
by: Zhuk, Dmitriy, et al.
Published: (2021)

Meta-Mathematics of Computational Complexity Theory
by: Oliveira, Igor C.
Published: (2025)

On the consistency of stronger lower bounds for NEXP
by: Thapen, Neil
Published: (2025)

Verifying Procedural Programs via Constrained Rewriting Induction
by: Fuhs, Carsten, et al.
Published: (2014)

Feasibility of Primality in Bounded Arithmetic
by: Jalali, Raheleh, et al.
Published: (2025)

Proof Complexity and Feasible Interpolation
by: Tabatabai, Amirhossein Akbar
Published: (2025)

Local vs. Global Interpretability: A Computational Complexity Perspective
by: Bassan, Shahaf, et al.
Published: (2024)

On Randomized Computational Models and Complexity Classes: a Historical Overview
by: Antonelli, Melissa, et al.
Published: (2024)

On The Metric Nature of (Differential) Logical Relations
by: Lago, Ugo Dal, et al.
Published: (2025)

On the Metric Nature of (Differential) Logical Relations
by: Lago, Ugo Dal, et al.
Published: (2026)

What makes an Ensemble (Un) Interpretable?
by: Bassan, Shahaf, et al.
Published: (2025)

Devil's Games and $\text{Q}\mathbb{R}$: Continuous Games complete for the First-Order Theory of the Reals
by: Meijer, Lucas, et al.
Published: (2025)

Hard to Explain: On the Computational Hardness of In-Distribution Model Interpretation
by: Amir, Guy, et al.
Published: (2024)

A SUBSET-SUM Characterisation of the A-Hierarchy
by: Gutleben, Jan, et al.
Published: (2024)

A characterization of efficiently compilable constraint languages
by: Berkholz, Christoph, et al.
Published: (2023)

Proceedings of the 19th International Workshop on Logical and Semantic Frameworks, with Applications
by: Kop, Cynthia, et al.
Published: (2025)