STACS 95

Table of Contents

1. Altmetric Badge
   Book Overview
2. Altmetric Badge
   Chapter 57 On the synthesis of strategies in infinite games
3. Altmetric Badge
   Chapter 58 Finding the maximum with linear error probabilities: a sequential analysis approach
4. Altmetric Badge
   Chapter 59 Completeness and weak completeness under polynomial-size circuits
5. Altmetric Badge
   Chapter 60 Communication complexity of key agreement on small ranges
6. Altmetric Badge
   Chapter 61 Pseudorandom generators and the frequency of simplicity
7. Altmetric Badge
   Chapter 62 Classes of bounded counting type and their inclusion relations
8. Altmetric Badge
   Chapter 63 Lower bounds for depth-three circuits with equals and mod-gates
9. Altmetric Badge
   Chapter 64 On realizing iterated multiplication by small depth threshold circuits
10. Altmetric Badge
    Chapter 65 A random NP-complete problem for inversion of 2D cellular automata
11. Altmetric Badge
    Chapter 66 On the subword equivalence problem for infinite words
12. Altmetric Badge
    Chapter 67 On the separators on an infinite word generated by a morphism
13. Altmetric Badge
    Chapter 68 Systolic tree ω-languages
14. Altmetric Badge
    Chapter 69 Structural complexity of ω-automata
15. Altmetric Badge
    Chapter 70 Algorithms explained by symmetries
16. Altmetric Badge
    Chapter 71 Generalized scans and tri-diagonal systems
17. Altmetric Badge
    Chapter 72 Two-dimensional pattern matching in linear time and small space
18. Altmetric Badge
    Chapter 73 On-line and dynamic algorithms for shortest path problems
19. Altmetric Badge
    Chapter 74 On compact representations of propositional circumscription
20. Altmetric Badge
    Chapter 75 A set-theoretic translation method for (poly)modal logics
21. Altmetric Badge
    Chapter 76 On the synthesis of discrete controllers for timed systems
22. Altmetric Badge
    Chapter 77 A fully abstract semantics for causality in the π-calculus
23. Altmetric Badge
    Chapter 78 On the sizes of permutation networks and consequences for efficient simulation of hypercube algorithms on bounded-degree networks
24. Altmetric Badge
    Chapter 79 Exploiting storage redundancy to speed up randomized shared memory simulations
25. Altmetric Badge
    Chapter 80 Interval routing schemes
26. Altmetric Badge
    Chapter 81 A packet routing protocol for arbitrary networks
27. Altmetric Badge
    Chapter 82 A family of tag systems for paperfolding sequences
28. Altmetric Badge
    Chapter 83 Growing context-sensitive languages and Church-Rosser languages
29. Altmetric Badge
    Chapter 84 Deterministic generalized automata
30. Altmetric Badge
    Chapter 85 Optimal simulation of automata by neural nets
31. Altmetric Badge
    Chapter 86 Concurrent process equivalences: Some decision problems
32. Altmetric Badge
    Chapter 87 Optimal lower bounds on the multiparty communication complexity
33. Altmetric Badge
    Chapter 88 Simultaneous messages vs. communication
34. Altmetric Badge
    Chapter 89 Coding and strong coding in trace monoids
35. Altmetric Badge
    Chapter 90 On codings of traces
36. Altmetric Badge
    Chapter 91 Finding largest common embeddable subtrees
37. Altmetric Badge
    Chapter 92 The χt-coloring problem
38. Altmetric Badge
    Chapter 93 Expander properties in random regular graphs with edge faults
39. Altmetric Badge
    Chapter 94 Dynamic analysis of the sizes of relations
40. Altmetric Badge
    Chapter 95 On slender context-free languages
41. Altmetric Badge
    Chapter 96 Partial derivatives of regular expressions and finite automata constructions
42. Altmetric Badge
    Chapter 97 Dependence orders for computations of concurrent automata
43. Altmetric Badge
    Chapter 98 On the undecidability of deadlock detection in families of nets
44. Altmetric Badge
    Chapter 99 On the average running time of odd-even merge sort
45. Altmetric Badge
    Chapter 100 Optimal average case sorting on arrays
46. Altmetric Badge
    Chapter 101 Normal numbers and sources for BPP
47. Altmetric Badge
    Chapter 102 Lower bounds on learning decision lists and trees
48. Altmetric Badge
    Chapter 103 Line segmentation of digital curves in parallel
49. Altmetric Badge
    Chapter 104 Computability of convex sets
50. Altmetric Badge
    Chapter 105 Enumerating extreme points in higher dimensions
51. Altmetric Badge
    Chapter 106 The number of views of piecewise-smooth algebraic objects
52. Altmetric Badge
    Chapter 107 On the structure of log-space probabilistic complexity classes
53. Altmetric Badge
    Chapter 108 Resource-bounded instance complexity
54. Altmetric Badge
    Chapter 109 On the sparse set conjecture for sets with low density
55. Altmetric Badge
    Chapter 110 Beyond P NP =NEXP
56. Altmetric Badge
    Chapter 111 Malign distributions for average case circuit complexity
57. Altmetric Badge
    Chapter 112 A possible code in the genetic code