Unary Resolution: Characterizing Ptime
DOI10.1007/978-3-662-49630-5_22zbMath1475.68133OpenAlexW2499876473MaRDI QIDQ2811353
Thomas Seiller, Marc Bagnol, Clément Aubert
Publication date: 10 June 2016
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-662-49630-5_22
proof theorylogic programmingsaturationpushdown automatageometry of interactionmemoizationimplicit complexityunary queries
Formal languages and automata (68Q45) Logic in computer science (03B70) Logic programming (68N17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Proof-theoretic aspects of linear logic and other substructural logics (03F52)
Related Items (5)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Logarithmic space and permutations
- Geometry of interaction. V: Logic in the hyperfinite factor
- Linear logic
- Light types for polynomial time computation in lambda calculus
- Linear logic by levels and bounded time complexity
- A new recursion-theoretic characterization of the polytime functions
- Notes on looping deterministic two-way pushdown automata
- Linear logic and elementary time
- Soft linear logic and polynomial time
- Logic Programming and Logarithmic Space
- Unary Resolution: Characterizing Ptime
- Finitary Semantics of Linear Logic and Higher-Order Model-Checking
- An Implicit Characterization of PSPACE
- A Short Introduction to Implicit Computational Complexity
- Functional Programming in Sublinear Space
- On the sequential nature of unification
- Term Rewriting and All That
- Unification and Logarithmic Space
- Normativity in Logic
- Programming Languages and Systems
- A Machine-Oriented Logic Based on the Resolution Principle
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
- Time and tape complexity of pushdown automaton languages
- Characterizingco-NLby a group action
This page was built for publication: Unary Resolution: Characterizing Ptime
