Fundamentals of Computation Theory

Table of Contents

1. Altmetric Badge
   Book Overview
2. Altmetric Badge
   Chapter 44 On strong separations from AC o
3. Altmetric Badge
   Chapter 45 Number theoretic algorithms and cryptology
4. Altmetric Badge
   Chapter 46 Computations over infinite groups
5. Altmetric Badge
   Chapter 47 Efficiency of Monte Carlo algorithms in numerical analysis
6. Altmetric Badge
   Chapter 48 Approximation algorithms for counting problems in finite fields
7. Altmetric Badge
   Chapter 49 Lower bounds for deterministic and nondeterministic branching programs
8. Altmetric Badge
   Chapter 50 Graph theoretical methods for the design of parallel algorithms
9. Altmetric Badge
   Chapter 51 Lattice basis reduction: Improved practical algorithms and solving subset sum problems
10. Altmetric Badge
    Chapter 52 Information-based complexity: Recent results and open problems
11. Altmetric Badge
    Chapter 53 A survey of some aspects of computational learning theory
12. Altmetric Badge
    Chapter 54 Recent progress in circuit and communication complexity
13. Altmetric Badge
    Chapter 55 The consistency of a noninterleaving and an interleaving model for full TCSP
14. Altmetric Badge
    Chapter 56 A geometrical bound for integer programming with polynomial constraints
15. Altmetric Badge
    Chapter 57 A characterization of binary search networks
16. Altmetric Badge
    Chapter 58 About the effect of the number of successful paths in an infinite tree on the recognizability by a finite automaton with Buchi conditions
17. Altmetric Badge
    Chapter 59 Deterministic dequeue automata and LL(1) parsing of breadth-depth grammars
18. Altmetric Badge
    Chapter 60 The complexity of computing maximal word functions
19. Altmetric Badge
    Chapter 61 Unambiguity and fewness for logarithmic space
20. Altmetric Badge
    Chapter 62 Differential resultants and subresultants
21. Altmetric Badge
    Chapter 63 Unifying binary-search trees and permutations
22. Altmetric Badge
    Chapter 64 Computational complexity and hardest languages of automata with abstract storages
23. Altmetric Badge
    Chapter 65 Systolic Y-tree automata: closure properties and decision problems
24. Altmetric Badge
    Chapter 66 A new partition lemma for planar graphs and its application to circuit complexity
25. Altmetric Badge
    Chapter 67 Some notes on threshold circuits, and multiplication in depth 4
26. Altmetric Badge
    Chapter 68 Nonlinear lower bounds on the number of processors of circuits with sublinear separators
27. Altmetric Badge
    Chapter 69 On space-bounded synchronized alternating turing machines
28. Altmetric Badge
    Chapter 70 Improving the critical density of the Lagarias-Odlyzko attack against subset sum problems
29. Altmetric Badge
    Chapter 71 Optimal versus stable in Boolean formulae
30. Altmetric Badge
    Chapter 72 The Gauß lattice basis reduction algorithm succeeds with any norm
31. Altmetric Badge
    Chapter 73 Regularity of one-letter languages acceptable by 2-way finite probabilistic automata
32. Altmetric Badge
    Chapter 74 On the semantics of atomized statements — the parallel-choice option —
33. Altmetric Badge
    Chapter 75 Automatic proof methods for algebraic specifications
34. Altmetric Badge
    Chapter 76 On the complexity of graph reconstruction
35. Altmetric Badge
    Chapter 77 An optimal adaptive in-place sorting algorithm
36. Altmetric Badge
    Chapter 78 Data structures maxima
37. Altmetric Badge
    Chapter 79 Average-case analysis of equality of binary trees under the BST probability model
38. Altmetric Badge
    Chapter 80 On the subsets of rank two in a free monoid: A fast decision algorithm
39. Altmetric Badge
    Chapter 81 Exact analysis of three tree contraction algorithms
40. Altmetric Badge
    Chapter 82 Degrees of nondeterminism for pushdown automata
41. Altmetric Badge
    Chapter 83 Optimal embedding of a toroidal array in a linear array
42. Altmetric Badge
    Chapter 84 Boolean functions with a large number of subfunctions and small complexity and depth
43. Altmetric Badge
    Chapter 85 Adaptive linear list reorganization for a system processing set queries
44. Altmetric Badge
    Chapter 86 On the decidability of integer subgraph problems on context-free graph languages