Implicit computational complexity and the exponential time-space classes

被引：0

作者：

Caporaso, Salvatore ^{[1
]}

Covino, Emanuele ^{[1
]}

Gissi, Paolo ^{[1
]}

Pani, Giovanni ^{[1
]}

机构：

[1] Univ Bari, Dipartimento Informat, Via Orabona, I-70125 Bari, Italy

来源：

PROCEEDINGS OF THE 6TH WSEAS INTERNATIONAL CONFERENCE ON TELECOMMUNICATIONS AND INFORMATICS (TELE-INFO '07)/ 6TH WSEAS INTERNATIONAL CONFERENCE ON SIGNAL PROCESSING (SIP '07) | 2007年

关键词：

implicit computational complexity; exponential time; exponential space; time-space classes;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

We extend the Implicit Computational Complexity program, promoted by Leivant and by other scholars, to all complexity classes DTIMESPACEF(f (n), g (n)), between DTIMEF(n) and DSPACEF(n(nc)). Let clps (alpha, n) denote the result of replacing w by n in Cantor normal form for alpha < w(ww). A hierarchy TS alpha beta is defined by means of a very restricted form of substitution, and of two un-limited operators (simultaneous predicative recurrence and constructive diagonalization), and it is proved that DTIMESPACEF(n(clps(beta,n)), n(clps(alpha,n))) = TS alpha beta. For example DTIMESPACEF(n(2), n(n)) = TSww,2.

引用

页码：65 / +

页数：2

共 12 条

[1] Extending the implicit computational complexity approach to the sub-elementary time-space classes
Covino, E
Pani, G
Caporaso, S
ALGORITHMS AND COMPLEXITY, 2000, 1767 : 239 - 252
[2] An implicit recursive language for the polynomial time-space complexity classes
Covino, E
Pani, G
JOURNAL OF UNIVERSAL COMPUTER SCIENCE, 2002, 8 (01): : 75 - 84
[3] Quantum implicit computational complexity
Dal Lago, Ugo
Masini, Andrea
Zorzi, Margherita
THEORETICAL COMPUTER SCIENCE, 2010, 411 (02) : 377 - 409
[4] Reversible computing and implicit computational complexity
Kristiansen, Lars
SCIENCE OF COMPUTER PROGRAMMING, 2022, 213
[5] Probabilistic Recursion Theory and Implicit Computational Complexity
Dal Lago, Ugo
Zuppiroli, Sara
Gabbrielli, Maurizio
SCIENTIFIC ANNALS OF COMPUTER SCIENCE, 2014, 24 (02) : 177 - 216
[6] Implicit Computational Complexity of Subrecursive Definitions and Applications to Cryptographic Proofs
Patrick Baillot
Gilles Barthe
Ugo Dal Lago
Journal of Automated Reasoning, 2019, 63 : 813 - 855
[7] Characterizing polynomial and exponential complexity classes in elementary lambda-calculus
Baillot, Patrick
De Benedetti, Erika
Della Rocca, Simona Ronchi
INFORMATION AND COMPUTATION, 2018, 261 : 55 - 77
[8] Generalised dynamic ordinals - Universal measures for implicit computational complexity
Beckmann, Arnold
Logic Colloquium '02, 2006, 27 : 48 - 74
[9] Formally Verified Resource Bounds through Implicit Computational Complexity
Rusch, Neea
COMPANION PROCEEDINGS OF THE 2022 ACM SIGPLAN INTERNATIONAL CONFERENCE ON SYSTEMS, PROGRAMMING, LANGUAGES, AND APPLICATIONS: SOFTWARE FOR HUMANITY, SPLASH COMPANION 2022, 2022, : 17 - 20
[10] Implicit Computational Complexity of Subrecursive Definitions and Applications to Cryptographic Proofs
Baillot, Patrick
Barthe, Gilles
Dal Lago, Ugo
JOURNAL OF AUTOMATED REASONING, 2019, 63 (04) : 813 - 855

← 1 2 →