A Representation Theorem for Primitive Recursive Algorithms

• Autorzy: Andary P. , Patrou B. , Valarcher P.
• Języki publikacji: EN

Abstrakty

EN

We formalize the algorithms computing primitive recursive (PR) functions as the abstract state machines (ASMs) whose running length is computable by a PR function. Then we show that there exists a programming language (implementing only PR functions) by which it is possible to implement any one of the previously defined algorithms for the PR functions in such a way that their complexity is preserved.

Słowa kluczowe

EN

primitive recursion; algorithms; abstract state machines; structural complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 107, nr 4
• Strony: 313--330
• Opis fizyczny: Bibliogr. 22 poz.

Twórcy

autor

Andary P.

autor

Patrou B.

autor

Valarcher P.

• University of Rouen, Computer Scicence Dept., LITIS, Technopole Madrillet, F-76800 Saint Etienne du Rouvray, Rouen, France,

Bibliografia

• [1] Börger Egon and Stärk Robert. Abstract State Machines. Springer-Verlag (2003).
• [2] Brookes Stephen and Dancanet Denis. Sequential Algorithms, Deterministic Parallelism, and Intensional Expressiveness. POPL '95: Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, ACM Press (1995) 13-24.
• [3] Colson Loöıc. About primitive recursive algorithms. Theoretical Computer Science 83 (1991) 57-69.
• [4] Colson Löıc and Fredholm Daniel. System T, call-by-value and the minimum problem. Theoretical Computer Science 206 (1998) 301-315.
• [5] Coquand Thierry. Une preuve directe du Théor`eme d'ultime obstination. Comptes rendus de l'Académie des sciences 314(série I) (1992).
• [6] Crolard Tristan, Polonowski Emmanuel and Valarcher Pierre. Extending the LOOP language with Higher-Order Procedural variables in ACM-Transactions on Computational Logic, (2008)
• [7] Crolard Tristan, Lacas Samuel and Valarcher Pierre. On the expressive power of the For-language in Nordic Journal of Computing 13, (2006)
• [8] Dancanet Denis and Brookes Stephen. Programming language expressiveness and circuit complexity. In: International Conference on the Mathematical Foundations of Programming Semantics (1996).
• [9] David René. Un algorithme primitif récursif pour la fonction Inf. Compte rendu á l'académie des Sciences 317 (1993).
• [10] David René. On the asymptotic behaviour of primitive recursive algorithms. Theoretical Computer Science 266(1-2) (2001) 159-193.
• [11] DavisMartin D., Sigal Ron andWeyuker Elaine J. Computability, Complexity and Languages: Fundamentals of Theoretical Computer Science. Academic Press (2nd edition) (1994).
• [12] Dershowitz Nachum and Gurevich Yuri. A Natural Axiomatization of Church's Thesis Microsoft Research Technical Report MSR-TR-2007-85, July 2007.
• [13] van den Dries Lou. Generating the greatest common divisor, and limitations of primitive recursive algorithms. Found. Comput. Math. 3 (2003) 297-3224.
• [14] Escardo Martin H. On Lazy Natural Numbers with Applications to Computability Theory and Functional Programming. SIGACT News 24(1) (1993) 60-67.
• [15] Fredholm Daniel. Computing Minimum with Primitive Recursion over Lists. Theoretical Computer Science 163(1-2) (1996) 269-276.
• [16] Gurevich Yuri. Sequential Abstract State Machines capture sequential algorithms. ACM Trans. Computational Logic 1(1) (2000) 77-111.
• [17] Meyer Albert R. and Ritchie Dennis M. The complexity of loop programs. Proceedings of the ACM 22nd National Conference, ACM Press (1967) 465-469.
• [18] Moschovakis Yannis N. On primitive recursive algorithms and the greatest common divisor function. Theoretical Computer Science 301(1-3) (2003) 1-30.
• [19] Moschovakis Yannis N. and Paschalis V. Elementary algorithms and their implementations. New Computational Paradigms, ed. S. B. Cooper, Benedikt Lowe and Andrea Sorbi, Springer, (2008), pp. 81 - 118.
• [20] Peter Roza. Recursive Functions. Academic Press (1968).
• [21] Roberts Eric S. Loop exits and structured programming: reopening the debate. SIGCSE '95: Proceedings of the twenty-sixth SIGCSE technical symposium on Computer science education (1995) 268-272.
• [22] Valarcher Pierre. Intensionality vs Extensionality and Primitive Recursion. Proceedings of the Second Asian Computing Science Conference on Concurrency and Parallelism, Programming, Networking, and Security, LNCS 1179 (1996) 142-151