First-order linear logic without modalities is NEXPTIME-hard

DOI10.1016/0304-3975(94)00107-3zbMath0824.68023OpenAlexW2080492358MaRDI QIDQ1342252

Patrick D. Lincoln, Andrej Scedrov

Publication date: 11 January 1995

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

Full work available at URL: https://doi.org/10.1016/0304-3975(94)00107-3

zbMATH Keywords

nondeterministic Turing machineslogic programming simulation

Mathematics Subject Classification ID

Logic programming (68N17) Subsystems of classical logic (including intuitionistic logic) (03B20)

Related Items

A PSPACE-complete first-order fragment of computability logic, Extended Lambek Calculi and First-Order Linear Logic, Relating state-based and process-based concurrency through linear logic (full-version)

Uses Software

• Lolli

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Linear logic
• Decision problems for propositional linear logic
• Linearizing intuitionistic implication
• Constant-only multiplicative linear logic is NP-complete
• Alternation and the computational complexity of logic programs
• Classifying the computational complexity of problems
• Logic Programming with Focusing Proofs in Linear Logic