On the public citation graph
Lambda calculus characterizations of poly-time
0 signed · 64 inferred · view as graph
Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.
Is this your work? Sign in with ORCID and put your name on the
claims that are yours.
Reference health. See whether every reference in this work resolves to a
known work and none has been retracted — and get a dated CiteStamped
badge you can embed.
What this work says
Outgoing claims: the papers this work cites, builds on, or argues with.
inferredcites →https://doi.org/10.1006/inco.1994.1038openalex-snapshot
A Foundational Delineation of Poly-time
inferredcites →https://doi.org/10.1007/3-540-06859-7_148openalex-snapshot
Towards a theory of type structure
inferredcites →https://doi.org/10.1007/978-1-4612-3466-1_16openalex-snapshot
Subrecursion and lambda representation over free algebras
inferredcites →https://doi.org/10.1007/bf01201998openalex-snapshot
A new recursion-theoretic characterization of the polytime functions
inferredcites →https://doi.org/10.1007/bf02276799openalex-snapshot
Definierbare Funktionen imλ-Kalkül mit Typen
inferredcites →https://doi.org/10.1016/0168-0072(86)90055-2openalex-snapshot
Fixed-point extensions of first-order logic
inferredcites →https://doi.org/10.1016/0304-3975(79)90007-0openalex-snapshot
The typed λ-calculus is not elementary recursive
inferredcites →https://doi.org/10.1016/0304-3975(85)90135-5openalex-snapshot
Automatic synthesis of typed Λ-programs on term algebras
inferredcites →https://doi.org/10.1016/0304-3975(87)90077-6openalex-snapshot
Word operation definable in the typed λ-calculus
inferredcites →https://doi.org/10.1016/0304-3975(92)90020-gopenalex-snapshot
A simple proof of a theorem of Statman
inferredcites →https://doi.org/10.1016/0890-5401(90)90006-4openalex-snapshot
Inductive definitions over finite structures
inferredcites →https://doi.org/10.1016/0890-5401(91)90053-5openalex-snapshot
Finitely stratified polymorphism
inferredcites →https://doi.org/10.1016/c2009-0-14341-6openalex-snapshot
The Lambda Calculus - Its Syntax and Semantics
inferredcites →https://doi.org/10.1016/s0019-9958(86)80029-8openalex-snapshot
Relational queries computable in polynomial time
inferredcites →https://doi.org/10.1109/lics.1991.151625openalex-snapshot
A foundational delineation of computational feasibility
inferredcites →https://doi.org/10.1109/sct.1992.215394openalex-snapshot
Functional characterizations of uniform log-depth and polylog-depth circuit families
inferredcites →https://doi.org/10.1137/0216051openalex-snapshot
Languages that Capture Complexity Classes
inferredcites →https://doi.org/10.1145/158511.158659openalex-snapshot
Stratified functional programs and computational complexity
inferredcites →https://doi.org/10.1145/322358.322370openalex-snapshot
The Expressiveness of Simple and Second-Order Type Structures
inferredcites →https://doi.org/10.1145/800070.802186openalex-snapshot
The complexity of relational query languages (Extended Abstract)
inferredcites →https://doi.org/10.1145/800135.804411openalex-snapshot
A programming language theorem which is independent of Peano Arithmetic
inferredcites →https://doi.org/10.2307/2270886openalex-snapshot
Alan Cobham. The intrinsic computational difficulty of functions. Logic, methodology and philosophy of science, Proceedings of the 1964 International Congress, edited by Yehoshua Bar-Hillel, Studies in logic and the foundations of mathematics, North-Holland Publishing Company, Amsterdam 1965, pp.…
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1006/inco.1996.0055openalex-snapshot
Database Query Languages Embedded in the Typed Lambda Calculus
inferred← citeshttps://doi.org/10.1007/3-540-58201-0_60openalex-snapshot
An analysis of the Core-ML language: Expressive power and type reconstruction
inferred← citeshttps://doi.org/10.1007/3-540-62592-5_61openalex-snapshot
Syntactic characterization in Lisp of the polynomial complexity classes and hierarchy
inferred← citeshttps://doi.org/10.1007/978-3-030-06170-8_2openalex-snapshot
Theoretical Computer Science: Computational Complexity
inferred← citeshttps://doi.org/10.1007/978-3-030-85315-0_20openalex-snapshot
ComplexityParser: An Automatic Tool for Certifying Poly-Time Complexity of Java Programs
inferred← citeshttps://doi.org/10.1007/978-3-031-47963-2_8openalex-snapshot
Towards the Complexity Analysis of Programming Language Proof Methods
inferred← citeshttps://doi.org/10.1007/978-3-032-31348-5_5openalex-snapshot
The New French School of Philosophy of Computing
inferred← citeshttps://doi.org/10.1007/978-3-642-11957-6_7openalex-snapshot
A PolyTime Functional Language from Light Linear Logic
inferred← citeshttps://doi.org/10.1007/978-3-642-17517-6_27openalex-snapshot
Interpretation of Stream Programs: Characterizing Type 2 Polynomial Time Complexity
inferred← citeshttps://doi.org/10.1007/978-3-642-22993-0_22openalex-snapshot
The Role of Polymorphism in the Characterisation of Complexity by Soft Types
inferred← citeshttps://doi.org/10.1007/978-3-642-31485-8_3openalex-snapshot
A Short Introduction to Implicit Computational Complexity
inferred← citeshttps://doi.org/10.1007/978-94-010-0413-8_13openalex-snapshot
Feasible Computation with Higher Types
inferred← citeshttps://doi.org/10.1016/j.ic.2015.12.011openalex-snapshot
The role of polymorphism in the characterisation of complexity by soft types
inferred← citeshttps://doi.org/10.1016/j.tcs.2006.03.019openalex-snapshot
An arithmetic for polynomial-time computation
inferred← citeshttps://doi.org/10.1016/j.tcs.2015.03.005openalex-snapshot
Realizability models for a linear dependent PCF
inferred← citeshttps://doi.org/10.1017/s0960129511000685openalex-snapshot
On quasi-interpretations, blind abstractions and implicit complexity
inferred← citeshttps://doi.org/10.1109/lics.1993.287575openalex-snapshot
Database query languages embedded in the typed lambda calculus
inferred← citeshttps://doi.org/10.1109/lics.1996.561337openalex-snapshot
On the expressive power of simply typed and let-polymorphic lambda calculi
inferred← citeshttps://doi.org/10.1109/lics.2000.855758openalex-snapshot
A syntactical analysis of non-size-increasing polynomial time computation
inferred← citeshttps://doi.org/10.1109/lics.2001.932498openalex-snapshot
Light affine lambda calculus and polytime strong normalization
inferred← citeshttps://doi.org/10.1109/lics.2002.1029842openalex-snapshot
Calibrating computational feasibility by abstraction rank
inferred← citeshttps://doi.org/10.1109/lics.2006.37openalex-snapshot
Obsessional Cliques: A Semantic Characterization of Bounded Time Complexity
inferred← citeshttps://doi.org/10.1109/lics.2011.41openalex-snapshot
A Type System for Complexity Flow Analysis
inferred← citeshttps://doi.org/10.1109/sfcs.1998.743522openalex-snapshot
A characterization of NC by tree recurrence
inferred← citeshttps://doi.org/10.1145/182591.182615openalex-snapshot
Functional database query languages as typed lambda calculi of fixed order (extended abstract)
inferred← citeshttps://doi.org/10.1145/2159531.2159540openalex-snapshot
An Implicit Characterization of PSPACE
inferred← citeshttps://doi.org/10.2168/lmcs-3(4:10)2007openalex-snapshot
Verification of Ptime Reducibility for system F Terms: Type Inference in Dual Light Affine Logic
inferred← citeshttps://doi.org/10.2178/bsl/1122038991openalex-snapshot
Tiering as a Recursion Technique
inferred← citeshttps://doi.org/10.4204/eptcs.23.3openalex-snapshot
Church => Scott = Ptime: an application of resource sensitive realizability
inferred← citeshttps://doi.org/10.4230/lipics.csl.2021.34openalex-snapshot
Typable Fragments of Polynomial Automatic Amortized Resource Analysis
inferred← citeshttps://doi.org/10.46298/lmcs-18(1:33)2022openalex-snapshot
A tier-based typed programming language characterizing Feasible Functionals
inferred← citeshttps://doi.org/10.46298/lmcs-21(1:5)2025openalex-snapshot
Complete and tractable machine-independent characterizations of second-order polytime
inferred← citeshttps://doi.org/10.48550/arxiv.1006.0030openalex-snapshot
An Implicit Characterization of PSPACE
inferred← citeshttps://doi.org/10.70675/2ba96c68z9506z47e0z8d13zf4cb43296358openalex-snapshot
Sized Types Methods and their Applications to Complexity Analysis in Pi-Calculus
inferred← citeshttps://doi.org/10.70675/3b6c23dezc274z4bf0zbb66z44b63eeb61e7openalex-snapshot
On the Resolution Semiring
inferred← citeshttps://doi.org/10.7146/brics.v8i46.21706openalex-snapshot
The Implicit Computational Complexity of Imperative Programming Languages
inferred← citeshttps://doi.org/10.7561/sacs.2014.2.177openalex-snapshot
Probabilistic Recursion Theory and Implicit Computational Complexity
Editorial review for independent work. ICSAC — the Institute for Complexity
Science and Advanced Computing — runs a structured editorial panel for researchers
publishing outside journals, and publishes on CiteStamp rails. Submission is free
and goes through ORCID: icsacinstitute.org/submit.