Unary resolution: characterizing \textsc{Ptime}
DOI10.1007/978-3-662-49630-5_22zbMATH Open1475.68133OpenAlexW2499876473MaRDI QIDQ2811353FDOQ2811353
Authors: Clément Aubert, Marc Bagnol, Thomas Seiller 
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
Recommendations
- Polynomial time in untyped elementary linear logic
- scientific article; zbMATH DE number 6917940
- A characterisation of \textbf{P} by \textbf{DLOGTIME}-uniform families of polarizationless P systems using only dissolution rules
- Non-uniform polytime computation in the infinitary affine lambda-calculus
- Bounded linear logic: A modular approach to polynomial-time computability
proof theorysaturationpushdown automatageometry of interactionmemoizationlogic programmingimplicit complexityunary queries
Formal languages and automata (68Q45) Logic programming (68N17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Logic in computer science (03B70) Proof-theoretic aspects of linear logic and other substructural logics (03F52)
Cites Work
- Linear logic
- Light types for polynomial time computation in lambda calculus
- A new recursion-theoretic characterization of the polytime functions
- Linear logic and elementary time
- Soft linear logic and polynomial time
- Elementary complexity and geometry of interaction
- Logarithmic space and permutations
- Functional programming in sublinear space
- Normativity in Logic
- Geometry of interaction. V: Logic in the hyperfinite factor
- Programming Languages and Systems
- On the sequential nature of unification
- Term Rewriting and All That
- A Machine-Oriented Logic Based on the Resolution Principle
- Time and tape complexity of pushdown automaton languages
- Unary Resolution: Characterizing Ptime
- Title not available (Why is that?)
- Characterizingco-NLby a group action
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
- Title not available (Why is that?)
- Linear logic by levels and bounded time complexity
- Notes on looping deterministic two-way pushdown automata
- Logic Programming and Logarithmic Space
- An Implicit Characterization of PSPACE
- A Short Introduction to Implicit Computational Complexity
- Finitary Semantics of Linear Logic and Higher-Order Model-Checking
- Unification and Logarithmic Space
Cited In (5)
This page was built for publication: Unary resolution: characterizing \textsc{Ptime}
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2811353)
