A PSPACE-complete first-order fragment of computability logic

DOI10.1145/2559949zbMath1287.03067arXiv1201.4856OpenAlexW2105830064MaRDI QIDQ5410328

Matthew S. Bauer

Publication date: 16 April 2014

Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1201.4856

zbMATH Keywords

computational complexitygame semanticscomputability logicinteractive computation

Mathematics Subject Classification ID

Logic in computer science (03B70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

On the toggling-branching recurrence of computability logic ⋮ Build your own clarithmetic I: Setup and completeness

Cites Work

• Unnamed Item
• Unnamed Item
• Introduction to clarithmetic. II
• Introduction to clarithmetic. III
• Introduction to clarithmetic. I
• A game semantics for linear logic
• First-order linear logic without modalities is NEXPTIME-hard
• Introduction to computability logic
• From truth to computability. II.
• From truth to computability. I.
• Soundness and completeness of the Cirquent calculus system CL6 for computability logic
• Introduction to Cirquent Calculus and Abstract Resource Semantics
• In the beginning was game semantics
• Propositional computability logic I
• Propositional computability logic II

This page was built for publication: A PSPACE-complete first-order fragment of computability logic