Cons-free Programs and Complexity Classes between LOGSPACE and PTIME

2020/08/07 by Neil D. Jones, Siddharth Bhaskar, Cynthia Kop +1
Computer Science · #cs.CC #cs.PL

paper · pdf · doi:10.4204/eptcs.320.5

published as EPTCS 320, 2020, pp. 65-79 · In Proceedings VPT/HCVS 2020, arXiv:2008.02483

arxiv created 2020/08/07 · arxiv updated 2020/08/10

Abstract

Programming language concepts are used to give some new perspectives on a long-standing open problem: is logspace = ptime ?

Citations

• Proceedings 8th International Workshop on Verification and Program Transformation and 7th Workshop on Horn Clauses for Verification and Synthesis