↓ Skip to main content

Fundamentals of Computation Theory

Overview of attention for book
Cover of 'Fundamentals of Computation Theory'

Table of Contents

  1. Altmetric Badge
    Book Overview
  2. Altmetric Badge
    Chapter 1 The Complexity of Querying External Memory and Streaming Data
  3. Altmetric Badge
    Chapter 2 The Smoothed Analysis of Algorithms
  4. Altmetric Badge
    Chapter 3 Path Coupling Using Stopping Times
  5. Altmetric Badge
    Chapter 4 On the Incompressibility of Monotone DNFs
  6. Altmetric Badge
    Chapter 5 Bounds on the Power of Constant-Depth Quantum Circuits
  7. Altmetric Badge
    Chapter 6 Biautomatic Semigroups
  8. Altmetric Badge
    Chapter 7 Deterministic Automata on Unranked Trees
  9. Altmetric Badge
    Chapter 8 Decidable Membership Problems for Finite Recurrent Systems over Sets of Naturals
  10. Altmetric Badge
    Chapter 9 Generic Density and Small Span Theorem
  11. Altmetric Badge
    Chapter 10 Logspace Optimization Problems and Their Approximability Properties
  12. Altmetric Badge
    Chapter 11 A Faster and Simpler 2-Approximation Algorithm for Block Sorting
  13. Altmetric Badge
    Chapter 12 On the Power of Unambiguity in Alternating Machines
  14. Altmetric Badge
    Chapter 13 Translational Lemmas for Alternating TMs and PRAMs
  15. Altmetric Badge
    Chapter 14 Collapsing Recursive Oracles for Relativized Polynomial Hierarchies
  16. Altmetric Badge
    Chapter 15 Exact Algorithms for Graph Homomorphisms
  17. Altmetric Badge
    Chapter 16 Improved Algorithms and Complexity Results for Power Domination in Graphs
  18. Altmetric Badge
    Chapter 17 Clique-Width for Four-Vertex Forbidden Subgraphs
  19. Altmetric Badge
    Chapter 18 On the Complexity of Uniformly Mixed Nash Equilibria and Related Regular Subgraph Problems
  20. Altmetric Badge
    Chapter 19 Simple Stochastic Games and P-Matrix Generalized Linear Complementarity Problems
  21. Altmetric Badge
    Chapter 20 Perfect Reconstruction of Black Pixels Revisited
  22. Altmetric Badge
    Chapter 21 Adaptive Zooming in Point Set Labeling
  23. Altmetric Badge
    Chapter 22 On the Black-Box Complexity of Sperner’s Lemma
  24. Altmetric Badge
    Chapter 23 Property Testing and the Branching Program Size of Boolean Functions
  25. Altmetric Badge
    Chapter 24 Almost Optimal Explicit Selectors
  26. Altmetric Badge
    Chapter 25 The Delayed k -Server Problem
  27. Altmetric Badge
    Chapter 26 Leftist Grammars and the Chomsky Hierarchy
  28. Altmetric Badge
    Chapter 27 Shrinking Multi-pushdown Automata
  29. Altmetric Badge
    Chapter 28 A Simple and Fast Min-cut Algorithm
  30. Altmetric Badge
    Chapter 29 (Non)-Approximability for the Multi-criteria TSP (1,2)
  31. Altmetric Badge
    Chapter 30 Completeness and Compactness of Quantitative Domains
  32. Altmetric Badge
    Chapter 31 A Self-dependency Constraint in the Simply Typed Lambda Calculus
  33. Altmetric Badge
    Chapter 32 A Type System for Computationally Secure Information Flow
  34. Altmetric Badge
    Chapter 33 Algorithms for Graphs Embeddable with Few Crossings Per Edge
  35. Altmetric Badge
    Chapter 34 Approximation Results for the Weighted P 4 Partition Problems
  36. Altmetric Badge
    Chapter 35 The Maximum Resource Bin Packing Problem
  37. Altmetric Badge
    Chapter 36 Average-Case Non-approximability of Optimisation Problems
  38. Altmetric Badge
    Chapter 37 Relations Between Average-Case and Worst-Case Complexity
  39. Altmetric Badge
    Chapter 38 Reconstructing Many Partitions Using Spectral Techniques
  40. Altmetric Badge
    Chapter 39 Constant Time Generation of Linear Extensions
  41. Altmetric Badge
    Chapter 40 On Approximating Real-World Halting Problems
  42. Altmetric Badge
    Chapter 41 An Explicit Solution to Post’s Problem over the Reals
  43. Altmetric Badge
    Chapter 42 The Complexity of Semilinear Problems in Succinct Representation
  44. Altmetric Badge
    Chapter 43 On Finding Acyclic Subhypergraphs
  45. Altmetric Badge
    Chapter 44 An Improved Approximation Algorithm for TSP with Distances One and Two
  46. Altmetric Badge
    Chapter 45 New Applications of Clique Separator Decomposition for the Maximum Weight Stable Set Problem
  47. Altmetric Badge
    Chapter 46 On the Expressiveness of Asynchronous Cellular Automata
  48. Altmetric Badge
    Chapter 47 Tree Automata and Discrete Distributed Games
  49. Altmetric Badge
    Chapter 48 A New Linearizing Restriction in the Pattern Matching Problem
  50. Altmetric Badge
    Chapter 49 Fully Incremental LCS Computation
Overall attention for this book and its chapters
Altmetric Badge

Mentioned by

wikipedia
1 Wikipedia page

Readers on

mendeley
6 Mendeley
You are seeing a free-to-access but limited selection of the activity Altmetric has collected about this research output. Click here to find out more.
Title
Fundamentals of Computation Theory
Published by
Springer Berlin Heidelberg, September 2005
DOI 10.1007/11537311
ISBNs
978-3-54-028193-1, 978-3-54-031873-6
Editors

Liśkiewicz, Maciej, Reischuk, Rüdiger

Mendeley readers

Mendeley readers

The data shown below were compiled from readership statistics for 6 Mendeley readers of this research output. Click here to see the associated Mendeley record.

Geographical breakdown

Country Count As %
Unknown 6 100%

Demographic breakdown

Readers by professional status Count As %
Student > Master 2 33%
Lecturer 1 17%
Professor > Associate Professor 1 17%
Unknown 2 33%
Readers by discipline Count As %
Computer Science 2 33%
Mathematics 1 17%
Agricultural and Biological Sciences 1 17%
Unknown 2 33%