Unary resolution: characterizing \textsc{Ptime}

DOI10.1007/978-3-662-49630-5_22MaRDI QIDQ2811353zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

proof theorysaturationpushdown automatageometry of interactionmemoizationlogic programmingimplicit complexityunary queries

Mathematics Subject Classification ID

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)

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

Cites work

• scientific article; zbMATH DE number 125883 (Why is no real title available?)
• scientific article; zbMATH DE number 786500 (Why is no real title available?)
• A Machine-Oriented Logic Based on the Resolution Principle
• A Short Introduction to Implicit Computational Complexity
• A new recursion-theoretic characterization of the polytime functions
• An implicit characterization of PSPACE
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• Characterizingco-NLby a group action
• Elementary complexity and geometry of interaction
• Finitary semantics of linear logic and higher-order model-checking
• Functional programming in sublinear space
• Geometry of interaction. V: Logic in the hyperfinite factor
• Light types for polynomial time computation in lambda calculus
• Linear logic
• Linear logic and elementary time
• Linear logic by levels and bounded time complexity
• Logarithmic space and permutations
• Logic programming and logarithmic space
• Normativity in logic
• Notes on looping deterministic two-way pushdown automata
• On the sequential nature of unification
• Programming Languages and Systems
• Soft linear logic and polynomial time
• Term Rewriting and All That
• Time and tape complexity of pushdown automaton languages
• Unary resolution: characterizing \textsc{Ptime}
• Unification and Logarithmic Space

Cited in

(5)

• Interaction graphs: graphings
• Unary resolution: characterizing \textsc{Ptime}
• A correspondence between maximal abelian sub-algebras and linear logic fragments
• Geometry of resource interaction and Taylor-Ehrhard-Regnier expansion: \textit{a minimalist approach}
• scientific article; zbMATH DE number 6917940 (Why is no real title available?)

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)