Fundamentals of Computation Theory

Table of Contents

1. Altmetric Badge
   Book Overview
2. Altmetric Badge
   Chapter 1 Towards Axiomatic Basis of Inductive Inference
3. Altmetric Badge
   Chapter 2 Approximation Algorithms for Fractional Covering and Packing Problems, and Applications
4. Altmetric Badge
   Chapter 3 Challenges of Commutation
5. Altmetric Badge
   Chapter 4 Approximating Bounded Degree Instances of NP-Hard Problems
6. Altmetric Badge
   Chapter 5 Universal Algebra and Computer Science
7. Altmetric Badge
   Chapter 6 Quantum Algorithms
8. Altmetric Badge
   Chapter 7 A Discrete Approximation and Communication Complexity Approach to the Superposition Problem
9. Altmetric Badge
   Chapter 8 On Computational Power of Quantum Branching Programs
10. Altmetric Badge
    Chapter 9 Efficient Computation of Singular Moduli with Application in Cryptography
11. Altmetric Badge
    Chapter 10 Ambainis-Freivalds’ Algorithm for Measure-Once Automata
12. Altmetric Badge
    Chapter 11 Are There Essentially Incomplete Knowledge Representation Systems?
13. Altmetric Badge
    Chapter 12 Best Increments for the Average Case of Shellsort
14. Altmetric Badge
    Chapter 13 Approximating Minimum Cocolourings
15. Altmetric Badge
    Chapter 14 Curved Edge Routing
16. Altmetric Badge
    Chapter 15 Time/Space Efficient Compressed Pattern Matching
17. Altmetric Badge
    Chapter 16 Modelling Change with the Aid of Knowledge and Time
18. Altmetric Badge
    Chapter 17 If P ≠ NP then Some Strongly Noninvertible Functions Are Invertible
19. Altmetric Badge
    Chapter 18 Prediction-Preserving Reducibility with Membership Queries on Formal Languages
20. Altmetric Badge
    Chapter 19 Dense Families and Key Functions of Database Relation Instances
21. Altmetric Badge
    Chapter 20 On the Complexity of Decidable Cases of Commutation Problem for Languages
22. Altmetric Badge
    Chapter 21 Cones, Semi-AFPs, and AFPs of Algebraic Power Series
23. Altmetric Badge
    Chapter 22 New Small Universal Circular Post Machines
24. Altmetric Badge
    Chapter 23 Divisibility Monoids: Presentation, Word Problem, and Rational Languages
25. Altmetric Badge
    Chapter 24 Concurrency in Timed Automata
26. Altmetric Badge
    Chapter 25 How Powerful Are Infinite Time Machines?
27. Altmetric Badge
    Chapter 26 Equivalence Problem of Composite Class Diagrams
28. Altmetric Badge
    Chapter 27 Differential Approximation Results for the Traveling Salesman Problem with Distances 1 and 2
29. Altmetric Badge
    Chapter 28 On the Category of Event Structures with Dense Time
30. Altmetric Badge
    Chapter 29 Closure of Polynomial Time Partial Information Classes under Polynomial Time Reductions
31. Altmetric Badge
    Chapter 30 Monte-Carlo Polynomial versus Linear Time - The Truth-Table Case
32. Altmetric Badge
    Chapter 31 Relating Automata-Theoretic Hierarchies to Complexity-Theoretic Hierarchies
33. Altmetric Badge
    Chapter 32 Polynomial Time Algorithms for Finding Unordered Tree Patterns with Internal Variables
34. Altmetric Badge
    Chapter 33 Piecewise and Local Threshold Testability of DFA
35. Altmetric Badge
    Chapter 34 Compositional Homomorphisms of Relational Structures
36. Altmetric Badge
    Chapter 35 Representation of Autonomous Automata
37. Altmetric Badge
    Chapter 36 Quantum Reversibility and a New Model of Quantum Automaton
38. Altmetric Badge
    Chapter 37 Space-Efficient 1.5-Way Quantum Turing Machine
39. Altmetric Badge
    Chapter 38 A Combinatorial Aggregation Algorithm for Stationary Distribution of a Large Markov Chain
40. Altmetric Badge
    Chapter 39 A Primitive for Proving the Security of Every Bit and about Universal Hash Functions & Hard Core Bits
41. Altmetric Badge
    Chapter 40 Pythagorean Triples in Unification Theory of Nilpotent Rings
42. Altmetric Badge
    Chapter 41 Two-States Bilinear Intrinsically Universal Cellular Automata
43. Altmetric Badge
    Chapter 42 Linear Time Recognizer for Subsets of ℤ2
44. Altmetric Badge
    Chapter 43 Fuzzy Sets and Algorithms of Distributed Task Allocation for Cooperative Agents
45. Altmetric Badge
    Chapter 44 On Recursively Enumerable Subsets of N and Rees Matrix Semigroups over (Z3 ; + )
46. Altmetric Badge
    Chapter 45 Quantum Real - Time Turing Machine
47. Altmetric Badge
    Chapter 46 Mathematical Models and Optimal Algorithms of Dynamic Data Structure Control
48. Altmetric Badge
    Chapter 47 Linear Automata and Recognizable Subsets in Free Semirings
49. Altmetric Badge
    Chapter 48 On Logical Method for Counting Dedekind Numbers
50. Altmetric Badge
    Chapter 49 A General Method for Graph Isomorphism
51. Altmetric Badge
    Chapter 50 Designing PTASs for MIN-SUM Scheduling Problems
52. Altmetric Badge
    Chapter 51 On Robust Algorithms for the Maximum Weight Stable Set Problem
53. Altmetric Badge
    Chapter 52 Multicasting in Optical Networks
54. Altmetric Badge
    Chapter 53 Structured Randomized Rounding and Coloring
55. Altmetric Badge
    Chapter 54 Optimal Online Flow Time with Resource Augmentation
56. Altmetric Badge
    Chapter 55 New Results for Path Problems in Generalized Stars, Complete Graphs, and Brick Wall Graphs
57. Altmetric Badge
    Chapter 56 On Minimizing Average Weighted Completion Time: A PTAS for Scheduling General Multiprocessor Tasks
58. Altmetric Badge
    Chapter 57 Approximation Algorithms for Time-Dependent Orienteering
59. Altmetric Badge
    Chapter 58 On Complexity of Colouring Mixed Hypertrees
60. Altmetric Badge
    Chapter 59 Combining Arithmetic and Geometric Rounding Techniques for Knapsack Problems
61. Altmetric Badge
    Chapter 60 The Complexity of Maximum Matroid-Greedoid Intersection