PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Powiadomienia systemowe
  • Sesja wygasła!
Tytuł artykułu

A Representation Theorem for Primitive Recursive Algorithms

Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
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.
Wydawca
Rocznik
Strony
313--330
Opis fizyczny
Bibliogr. 22 poz.
Twórcy
autor
autor
autor
  • University of Rouen, Computer Scicence Dept., LITIS, Technopole Madrillet, F-76800 Saint Etienne du Rouvray, Rouen, France, Philippe.Andary@univ-rouen.fr
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
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BUS8-0018-0015
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.