Update cookies preferences

Abstract Recursion and Intrinsic Complexity [Hardback]

(University of California, Los Angeles)
  • Format: Hardback, 250 pages, height x width x depth: 235x157x18 mm, weight: 470 g, Worked examples or Exercises; 1 Halftones, black and white; 4 Line drawings, black and white
  • Series: Lecture Notes in Logic
  • Pub. Date: 06-Dec-2018
  • Publisher: Cambridge University Press
  • ISBN-10: 110841558X
  • ISBN-13: 9781108415583
Other books in subject:
  • Hardback
  • Price: 158,05 €
  • This book is not in stock. Book will arrive in about 2-4 weeks. Please allow another 2 weeks for shipping outside Estonia.
  • Quantity:
  • Add to basket
  • Delivery time 4-6 weeks
  • Add to Wishlist
Abstract Recursion and Intrinsic ComplexityLarger Image
  • Format: Hardback, 250 pages, height x width x depth: 235x157x18 mm, weight: 470 g, Worked examples or Exercises; 1 Halftones, black and white; 4 Line drawings, black and white
  • Series: Lecture Notes in Logic
  • Pub. Date: 06-Dec-2018
  • Publisher: Cambridge University Press
  • ISBN-10: 110841558X
  • ISBN-13: 9781108415583
Other books in subject:
Permanent link: https://www.kriso.ee/db/9781108415583.html
Keywords:
The author presents and applies a new framework for studying the complexity of algorithms. The book is aimed at logicians, computer scientists, mathematicians and philosophers who are interested in the theory of computation and its foundations. It includes an accessible introduction to abstract recursion theory and contains over 250 problems.

This book presents and applies a framework for studying the complexity of algorithms. It is aimed at logicians, computer scientists, mathematicians and philosophers interested in the theory of computation and its foundations, and it is written at a level suitable for non-specialists. Part I provides an accessible introduction to abstract recursion theory and its connection with computability and complexity. This part is suitable for use as a textbook for an advanced undergraduate or graduate course: all the necessary elementary facts from logic, recursion theory, arithmetic and algebra are included. Part II develops and applies an extension of the homomorphism method due jointly to the author and Lou van den Dries for deriving lower complexity bounds for problems in number theory and algebra which (provably or plausibly) restrict all elementary algorithms from specified primitives. The book includes over 250 problems, from simple checks of the reader's understanding, to current open problems.

Reviews

' the author presents basic methods, approaches and results of the theory of abstract (rst-order) recursion and its relevance to the foundations of the theory of algorithms and computational complexity ' Marat M. Arslanov, Mathematical Reviews Clippings

More info

Presents a new framework for the complexity of algorithms, for all readers interested in the theory of computation.
Introduction 1(6)
Chapter 1 Preliminaries
7(42)
1A Standard notations
7(8)
Partial functions
9(1)
Monotone and continuous functionals
10(2)
Trees
12(2)
Problems
14(1)
1B Continuous, call-by-value recursion
15(6)
The where -notation for mutual recursion
17(1)
Recursion rules
17(2)
Problems
19(2)
1C Some basic algorithms
21(8)
The merge-sort algorithm
21(2)
The Euclidean algorithm
23(1)
The binary (Stein) algorithm
24(1)
Horner's rule
25(1)
Problems
25(4)
1D Partial structures
29(7)
Φ-structures
30(2)
Substructures
32(1)
Diagrams
32(1)
Homomorphisms and em-beddings
33(1)
Substructure generation
33(1)
Certificates
34(1)
Problems
35(1)
1E Partial equational logic
36(13)
Syntax
36(2)
Semantics
38(1)
Explicit definability
39(3)
Problems
42(7)
Part I Abstract (first order) recursion
Chapter 2 Recursive (McCarthy) programs
49(54)
2A Syntax and semantics
49(9)
A-recursive functions and functionals
52(3)
Problems
55(3)
2B Simple fixed points and tail recursion
58(11)
Simple fixed points
58(1)
Pointed structures
59(1)
Tail recursion
60(1)
Tail recursive programs and functions
61(1)
Mutual tail recursion
61(2)
Relativization
63(1)
Problems
64(5)
2C Iterators
69(5)
Reduction of iteration to tail recursion
70(1)
Explicit representation
71(1)
Turing computability and recursion
71(2)
About implementations (I)
73(1)
Problems
73(1)
2D The recursive machine
74(8)
Reduction of recursion to iteration
78(1)
Symbolic computation
78(2)
Problems
80(2)
2E Finite nondeterminism
82(8)
Certificates and computations
83(1)
Fixed point semantics for nondeterministic programs
84(1)
Pratt's nuclid algorithm
85(1)
Problems
86(4)
2F Some standard models of computation
90(4)
Finite register machines
90(1)
Straight line programs
91(1)
Random Access Machines (RAMs)
91(2)
Problems
93(1)
2G Full vs. tail recursion (I)
94(5)
Examples where Tailrec° (A) C Rec° (A)
95(2)
Examples where Tailrec° (A) should be Rec° (A)
97(1)
Problems
98(1)
2H What is an algorithm?
99(4)
About implementations (II)
100(1)
Imperative vs. functional programming
101(1)
Proofs of correctness
101(2)
Chapter 3 Complexity theory for recursive programs
103(26)
3A The basic complexity measures
103(12)
The tree-depth complexity DAE(M)
104(3)
The sequential logical complexity Ls(M) (time)
107(1)
The parallel logical complexity LP(M)
108(2)
The number-of-calls complexity Cs(φ0)(M)
110(1)
The depth-of-calls complexity Cp(φ0)(M)
111(1)
Problems
112(3)
3B Complexity inequalities
115(14)
Recursive vs. explicit definability
115(2)
Tserunyan's inequalities
117(7)
Full vs. tail recursion (II)
124(1)
Problems
125(4)
Part II Intrinsic complexity
Chapter 4 The homomorphism method
129(30)
4A Uniformity of algorithms
129(4)
Processes
130(2)
Uniform processes
132(1)
Uniformity Thesis
132(1)
4B Examples and counterexamples
133(3)
An example of a non-uniform process
134(1)
Problems
135(1)
4C Complexity measures on uniform processes
136(5)
Substructure norms
136(2)
The time complexity on RAMs
138(1)
Problems
138(3)
4D Forcing ||-A and certification ||-AC
141(3)
The connection with Pratt certificates for primality
143(1)
Problems
144(1)
4E Intrinsic complexities of functions and relations
144(5)
Homomorphism Test
145(1)
The output complexities
146(1)
Explicit (term) reduction and equivalence
146(1)
Problems
147(1)
Obstruction to calls(A, R, x→) = 0
147(1)
Obstruction to depth(A, R, →x) = 0
148(1)
4F The best uniform process
149(3)
Optimality and weak optimality
150(1)
Problems
151(1)
4G Logical extensions
152(6)
The lower bound for comparison sorting
153(1)
Embedding Test
154(1)
Substructure norms on logical extensions
155(2)
Problems
157(1)
4H Deterministic uniform processes
158(1)
Problems
158(1)
Chapter 5 Lower bounds from Presburger Primitives
159(12)
5A Representing the numbers in Gm(Na, a→)
159(4)
Problems
162(1)
5B Primality from Lind
163(4)
Using non-trivial number theory
165(1)
Problems
166(1)
5C Good examples: perfect square, square-free, etc
167(1)
Problems
167(1)
5D Stein's algorithm is weakly depth-optimal from Lind
168(3)
Problems
170(1)
Chapter 6 Lower bounds from division with remainder
171(20)
6A Unary relations from Lin0[ ÷]
171(6)
Problems
177(1)
6B Three results from number theory
177(6)
Problems
181(2)
6C Coprimeness from Lin0[ ÷l;]
183(8)
Problems
189(2)
Chapter 7 Lower bounds from division and multiplication
191(12)
7A Polynomials and their heights
191(5)
7B Unary relations from Lin0[ ÷, .]
196(7)
Problems
202(1)
Chapter 8 Non-uniform complexity in N
203(6)
8A Non-uniform lower bounds from Lind
203(2)
Problems
205(1)
8B Non-uniform lower bounds from Lin0[ ÷]
205(4)
Problems
207(2)
Chapter 9 Polynomial nullity (0-testing)
209(28)
9A Preliminaries and notation
209(2)
The Substitution Lemma
210(1)
9B Generic {+, -}-optimality of Horner's rule
211(7)
Counting identity tests along with {+, - }
216(2)
9C Generic {+, -}-optimality of Horner's rule
218(11)
Counting identity tests along with {+, -}
225(1)
Counting everything
226(1)
Problems
226(3)
References
229(8)
Symbol index 237(2)
General index 239
Yiannis N. Moschovakis is Professor Emeritus and Distinguished Research Professor of Mathematics at the University of California, Los Angeles, and Professor Emeritus at the University of Athens. Among his many professional commendations he is a Fellow of the AMS and a corresponding member of the Academy of Athens. He has received Guggenheim and Sloan Fellowships and has been an invited speaker at the International Congress of Mathematicians. Professor Moschovakis has worked primarily in the theory of recursion, descriptive set theory and the foundations of the theory of algorithms and computation.