Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Browse by topic Browse by titles Authors Reviewers Browse by issue Browse Help
  Browse All Reviews > Theory Of Computation (F) > Mathematical Logic And Formal Languages (F.4) > Mathematical Logic (F.4.1) > Recursive Function Theory (F.4.1...)  
  1-7 of 7 Reviews about "Recursive Function Theory (F.4.1...)": Date Reviewed
  Computability theory: an introduction to recursion theory
Enderton H., ACADEMIC PRESS, Boston, MA, 2010. 192 pp.  Type: Book (978-0-123849-58-8)

Computability is concerned with the question of what computers can do in principle. Since Enderton directly contributed to the very areas that this book covers (computability and computational complexity), he is able to provide a conci...

Jun 24 2011
  The tree equivalence of linear recursion schemes
Sabelfeld V. Theoretical Computer Science 238(1-2): 1-29, 2000.  Type: Article

The author proposes a logically complete system of transformation rules that preserve tree equivalence, and presents a polynomial-time algorithm for deciding the tree equivalence of linear polyadic recursion schemes, which runs in time...

May 1 2000
  An inherently iterative algorithm for the Grzegorczyk hierarchy
Matthews R. Theoretical Computer Science 125(2): 355-360, 1994.  Type: Article

Extending results of Grossman and Zeitman [1] on an inherently iterative algorithm for the classical Ackermann’s function, the author develops an analogous algorithm for the more logically interesting Grzegorczyk hierarchy [2...

Aug 1 1995
  Higher recursion theory
Sacks G., Springer-Verlag New York, Inc., New York, NY, 1990.  Type: Book (9780387193052)

Classical recursion theory (CRT) applies to essentially finite sets of natural numbers. CRT predicates can be defined using the first-order predicate calculus (PC) with quantification over the natural numbers, &ohgr;. CRT was defin...

Feb 1 1992
  Generation of invertible functions
Jacopini G., Mentrasti P. Theoretical Computer Science 66(3): 289-297, 1989.  Type: Article

A partial function is invertible if and only if it is one-to-one. The authors provide a formalism for the invertible partial recursive functions of one argument. They show that this class of partial recursive functions is the cl...

Aug 1 1990
  Reflexive structures: an introduction to computability theory
Sanchis L., Springer-Verlag New York, Inc., New York, NY, 1988.  Type: Book (9789780387967288)

This book is devoted to a deep and interesting study of sets and functions on natural numbers in terms of three properties intimately connected with the notion of computability: (1) closure (especially recursion and minimization), (2) ...

Jul 1 1989
  Recursively enumerable sets and degrees
Soare R., Springer-Verlag New York, Inc., New York, NY, 1987.  Type: Book (9789780387152998)

This is a major and comprehensive treatise on classical recursion theory. It is a self-contained, highly readable, and excellently organized book whose coverage extends from the foundations of the theory of computable functions to the ...

Mar 1 1988
Display per page
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2023 ThinkLoud®
Terms of Use
| Privacy Policy