Cover Image

Reasonable Space for the $λ$-Calculus, Logarithmically

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Accattoli, Beniamino, Lago, Ugo Dal, Vanoni, Gabriele
Format:	Preprint
Published:	2022
Subjects:	Logic in Computer Science Computational Complexity Programming Languages
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Multi types and reasonable space
by: Accattoli, Beniamino, et al.
Published: (2022)

The Vanilla Sequent Calculus is Call-by-Value (Fresh Perspective)
by: Accattoli, Beniamino
Published: (2024)

Interaction Equivalence
by: Accattoli, Beniamino, et al.
Published: (2024)

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

Exponentials as Substitutions and the Cost of Cut Elimination in Linear Logic
by: Accattoli, Beniamino
Published: (2022)

Positive Focusing is Directly Useful
by: Accattoli, Beniamino, et al.
Published: (2024)

Positive Sharing and Abstract Machines
by: Accattoli, Beniamino, et al.
Published: (2025)

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

A Characterization of Basic Feasible Functionals Through Higher-Order Rewriting and Tuple Interpretations
by: Baillot, Patrick, et al.
Published: (2024)

Kleene algebra with commutativity conditions is undecidable
by: de Amorim, Arthur Azevedo, et al.
Published: (2024)

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

Monadic Intersection Types, Relationally (Extended Version)
by: Gavazzo, Francesco, et al.
Published: (2024)

Complete and tractable machine-independent characterizations of second-order polytime
by: Hainry, Emmanuel, et al.
Published: (2022)

LFPL: Revisited and Mechanized
by: Glover, Nathaniel, et al.
Published: (2026)

Reversible Computation with Stacks and "Reversible Management of Failures"
by: Palazzo, Matteo, et al.
Published: (2025)

Program Synthesis is $Σ_3^0$-Complete
by: Kim, Jinwoo
Published: (2024)

Mirroring Call-by-Need, or Values Acting Silly
by: Accattoli, Beniamino, et al.
Published: (2024)

Interaction Improvement
by: Lancelot, Adrienne, et al.
Published: (2026)

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

IMELL Cut Elimination with Linear Overhead
by: Accattoli, Beniamino, et al.
Published: (2024)

Counting and Sampling Traces in Regular Languages
by: de Colnet, Alexis, et al.
Published: (2025)

Cypher is Turing-Complete: A Formal Proof via 2-Counter Machine Simulation
by: Halftermeyer, Pierre
Published: (2026)

Quantum First-Order Logics That Capture Logarithmic-Time/Space Quantum Computability
by: Yamakami, Tomoyuki
Published: (2025)

Towards a Characterization of Two-way Bijections in a Reversible Computational Model
by: Palazzo, Matteo, et al.
Published: (2025)

A faster FPRAS for #NFA
by: Meel, Kuldeep S., et al.
Published: (2023)

The Functional Machine Calculus III: Control
by: Heijltjes, Willem
Published: (2025)

Functional Array Programming in an Extended Pi-Calculus
by: Hüttel, Hans, et al.
Published: (2024)

On Decidable and Undecidable Extensions of Simply Typed Lambda Calculus
by: Kobayashi, Naoki
Published: (2024)

Non-commutative linear logic fragments with sub-context-free complexity
by: Nishimiya, Yusaku, et al.
Published: (2025)

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

On Probabilistic and Causal Reasoning with Summation Operators
by: Ibeling, Duligur, et al.
Published: (2024)

Intersection Types for a Computational Lambda-Calculus with Global State
by: de'Liguoro, Ugo, et al.
Published: (2021)

Polynomial Calculus sizes over the Boolean and Fourier bases are incomparable
by: Mouli, Sasank
Published: (2024)

Functional variant of Polynomial Analogue of Gandy's Fixed Point Theorem
by: Nechesov, Andrey
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)