Ramified Corecurrence and Logspace

DOI10.1016/J.ENTCS.2011.09.025zbMath1342.68139OpenAlexW2094867196WikidataQ113318220 ScholiaQ113318220MaRDI QIDQ5739361

Ramyaa Ramyaa, Daniel Leivant

Publication date: 15 July 2016

Published in: Electronic Notes in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.entcs.2011.09.025

zbMATH Keywords

ramificationlogarithmic spaceimplicit computational complexitycoinductive datacorecurrencelazy corecurrencestream automata

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (5)

Computation by interaction for space-bounded functional programming ⋮ Parsimonious Types and Non-uniform Computation ⋮ Unnamed Item ⋮ Intuitionistic fixed point logic ⋮ Characterizing polynomial time complexity of stream programs using interpretations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Functional interpretations of feasibly constructive arithmetic
• Bounded arithmetic for NC, ALogTIME, L and NL
• A new recursion-theoretic characterization of the polytime functions
• LOGSPACE and PTIME characterized by programming languages
• Neat function algebraic characterizations of LOGSPACE and LINSPACE
• On non-determinacy in simple computing devices
• Interpretation of Stream Programs: Characterizing Type 2 Polynomial Time Complexity
• Some Programming Languages for Logspace and Ptime
• Space Lower Bounds for Maze Threadability on Restricted Machines
• Automatic Sequences
• Feasible Functions over Co-inductive Data
• Programming Languages and Systems
• Global and Local Space Properties of Stream Programs

This page was built for publication: Ramified Corecurrence and Logspace