Read/write factorizable programs

被引:0
作者
Bhaskar, Siddharth [1 ]
Simonsen, Jakob Grue [1 ]
机构
[1] Univ Copenhagen, Copenhagen, Denmark
关键词
ORDER; COMPLEXITY; LANGUAGES; LOGSPACE;
D O I
10.1017/S0956796823000023
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
In the cons-free programming paradigm, we eschew constructors and program using only destructors. Cons-free programs in a simple first-order language with string data capture exactly P, the class of polynomial-time relations. By varying the underlying language and considering other data types, we can capture several other complexity classes. However, no cons-free programming language captures any functional complexity class for fundamental reasons. In this paper, we cleanly extend the cons-free paradigm to encompass functional complexity classes. Namely, we introduce programs with data that can either only be destructed or only be constructed, which we enforce by a type system on the program variables. We call the resulting programs read/write- (or RW-)factorizable, show that RW-factorizable string programs capture exactly the class FP of polynomial-time functions, and that tail-recursive RW-factorizable programs capture exactly the class FL of logarithmic-space functions. Finally, we state and solve the nontrivial problem of syntactic composition of two RW-factorizable programs.
引用
收藏
页数:50
相关论文
共 34 条
[1]  
Alton D.A., 1980, LONDON MATH SOC LECT, P248, DOI DOI 10.1007/CBO9780511629181.011
[2]  
Aubert C., 2022, LIPICS, V228
[3]   A combination framework for complexity [J].
Avanzini, Martin ;
Moser, Georg .
INFORMATION AND COMPUTATION, 2016, 248 :22-55
[4]   A Path Order for Rewrite Systems that Compute Exponential Time Functions [J].
Avanzini, Martin ;
Eguchi, Naohi ;
Moser, Georg .
22ND INTERNATIONAL CONFERENCE ON REWRITING TECHNIQUES AND APPLICATIONS (RTA'11), 2011, 10 :123-138
[5]   A new order-theoretic characterisation of the polytime computable functions [J].
Avanzini, Martin ;
Eguchi, Naohi ;
Moser, Georg .
THEORETICAL COMPUTER SCIENCE, 2015, 585 :3-24
[6]   Types for Complexity of Parallel Computation in Pi-calculus [J].
Baillot, Patrick ;
Ghyselen, Alexis .
ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS, 2022, 44 (03)
[7]   Implicit Computational Complexity of Subrecursive Definitions and Applications to Cryptographic Proofs [J].
Baillot, Patrick ;
Barthe, Gilles ;
Dal Lago, Ugo .
JOURNAL OF AUTOMATED REASONING, 2019, 63 (04) :813-855
[8]  
Bellantoni S., 1992, Proceedings of the Twenty-Fourth Annual ACM Symposium on the Theory of Computing, P283, DOI 10.1145/129712.129740
[9]  
Ben-Amram AM, 1998, LECT NOTES COMPUT SC, V1443, P271, DOI 10.1007/BFb0055060
[10]   Subclasses of Ptime Interpreted by Programming Languages [J].
Bhaskar, Siddharth ;
Kop, Cynthia ;
Simonsen, Jakob Grue .
THEORY OF COMPUTING SYSTEMS, 2023, 67 (03) :437-472