Power Search
Low Price Guarantee
We Take School POs
Subrecursive Programming Systems: Complexity & Succinctness Softcover Repri Edition
Contributor(s): Royer, James S. (Author), Case, John (Author)

View larger image

 ISBN: 1461266807     ISBN-13: 9781461266808
Publisher: Birkhauser
OUR PRICE: $104.49  

Binding Type: Paperback - See All Available Formats & Editions
Published: October 2012
Qty:

Click for more in this series: Progress in Theoretical Computer Science
Additional Information
BISAC Categories:
- Computers | Software Development & Engineering - General
- Computers | Programming - General
Dewey: 005.131
Series: Progress in Theoretical Computer Science
Physical Information: 0.55" H x 6.14" W x 9.21" L (0.82 lbs) 253 pages
 
Descriptions, Reviews, Etc.
Publisher Description:
1.1. What This Book is About This book is a study of - subrecursive programming systems, - efficiency/program-size trade-offs between such systems, and - how these systems can serve as tools in complexity theory. Section 1.1 states our basic themes, and Sections 1.2 and 1.3 give a general outline of the book. Our first task is to explain what subrecursive programming systems are and why they are of interest. 1.1.1. Subrecursive Programming Systems A subrecursive programming system is, roughly, a programming language for which the result of running any given program on any given input can be completely determined algorithmically. Typical examples are: 1. the Meyer-Ritchie LOOP language MR67, DW83], a restricted assem- bly language with bounded loops as the only allowed deviation from straight-line programming; 2. multi-tape 'lUring Machines each explicitly clocked to halt within a time bound given by some polynomial in the length ofthe input (see BH79, HB79]); 3. the set of seemingly unrestricted programs for which one can prove 1 termination on all inputs (see Kre51, Kre58, Ros84]); and 4. finite state and pushdown automata from formal language theory (see HU79]). lOr, more precisely, the collection of programs, p, ofsome particular general-purpose programming language (e.g., Lisp or Modula-2) for which there is a proof in some par- ticular formal system (e.g., Peano Arithmetic) that p halts on all inputs.
 
Customer ReviewsSubmit your own review
 
To tell a friend about this book, you must Sign In First!