STACS 96

Table of Contents

1. Altmetric Badge
   Book Overview
2. Altmetric Badge
   Chapter 1 New trends in quantum computing
3. Altmetric Badge
   Chapter 2 Compressibility and resource bounded measure
4. Altmetric Badge
   Chapter 3 On the complexity of random strings
5. Altmetric Badge
   Chapter 4 Remarks on generalized Post Correspondence Problem
6. Altmetric Badge
   Chapter 5 Cyclic languages and strongly cyclic languages
7. Altmetric Badge
   Chapter 6 Resource-bounded balanced genericity, stochasticity and weak randomness
8. Altmetric Badge
   Chapter 7 The complexity of generating and checking proofs of membership
9. Altmetric Badge
   Chapter 8 Observations on measure and lowness for Δ 2 P
10. Altmetric Badge
    Chapter 9 Solvable black-box group problems are low for PP
11. Altmetric Badge
    Chapter 10 Languages recognized by finite aperiodic groupoids
12. Altmetric Badge
    Chapter 11 Star-height of an N -rational series
13. Altmetric Badge
    Chapter 12 An aperiodic set of Wang cubes
14. Altmetric Badge
    Chapter 13 Lyndon factorization of infinite words
15. Altmetric Badge
    Chapter 14 Embedding graphs with bounded treewidth into optimal hypercubes
16. Altmetric Badge
    Chapter 15 Parallel comparability graph recognition and modular decomposition
17. Altmetric Badge
    Chapter 16 Fault-tolerant shared memory simulations
18. Altmetric Badge
    Chapter 17 On word-level parallelism in fault-tolerant computing
19. Altmetric Badge
    Chapter 18 Learning with confidence
20. Altmetric Badge
    Chapter 19 Extracting best consensus motifs from positive and negative examples
21. Altmetric Badge
    Chapter 20 PAC learning with simple examples
22. Altmetric Badge
    Chapter 21 General inductive inference types based on linearly-ordered sets
23. Altmetric Badge
    Chapter 22 On the power of non-observable actions in timed automata
24. Altmetric Badge
    Chapter 23 Trace rewriting: Computing normal forms in time O ( n log n )
25. Altmetric Badge
    Chapter 24 A decision procedure for well-formed linear quantum cellular automata
26. Altmetric Badge
    Chapter 25 On the complexity of worst case and expected time in a circuit
27. Altmetric Badge
    Chapter 26 On the existence of hard sparse sets under weak reductions
28. Altmetric Badge
    Chapter 27 Optimal bounds on the approximation of boolean functions with consequences on the concept of hardness
29. Altmetric Badge
    Chapter 28 Fine separation of average time complexity classes
30. Altmetric Badge
    Chapter 29 Compositional specification of timed systems
31. Altmetric Badge
    Chapter 30 Optimal tree-based one-time digital signature schemes
32. Altmetric Badge
    Chapter 31 The action of a few random permutations on r -tuples and an application to cryptography
33. Altmetric Badge
    Chapter 32 A unified and generalized treatment of authentication theory
34. Altmetric Badge
    Chapter 33 Monadic second order logic on tree-like structures
35. Altmetric Badge
    Chapter 34 On bijections vs. unary functions
36. Altmetric Badge
    Chapter 35 The 3 Frenchmen method proves undecidability of the uniform boundedness for single recursive rule ternary DATALOG Programs
37. Altmetric Badge
    Chapter 36 A combinatorial design approach to MAXCUT
38. Altmetric Badge
    Chapter 37 Characterizing the complexity of subgraph isomorphism for graphs of bounded path-width
39. Altmetric Badge
    Chapter 38 A characterization of the quadrilateral meshes of a surface which admit a compatible hexahedral mesh of the enclosed volume
40. Altmetric Badge
    Chapter 39 On the expressivity of the modal mu-calculus
41. Altmetric Badge
    Chapter 40 Read-once projections and formal circuit verification with binary decision diagrams
42. Altmetric Badge
    Chapter 41 “Optimal” collecting semantics for analysis in a hierarchy of logic program semantics
43. Altmetric Badge
    Chapter 42 Flip-flop nets
44. Altmetric Badge
    Chapter 43 Lower bounds for compact routing
45. Altmetric Badge
    Chapter 44 On the successor function in non-classical numeration systems
46. Altmetric Badge
    Chapter 45 Minimal forbidden words and symbolic dynamics
47. Altmetric Badge
    Chapter 46 Universal hashing and k -wise independent random variables via integer arithmetic without primes
48. Altmetric Badge
    Chapter 47 Ranking and unranking trees using regular reductions
49. Altmetric Badge
    Chapter 48 On competitive on-line paging with lookahead
50. Altmetric Badge
    Chapter 49 Hypothesis testing in perfect phylogeny for a bounded number of characters
51. Altmetric Badge
    Chapter 50 The “log rank” conjecture for modular communication complexity
52. Altmetric Badge
    Chapter 51 Upper bounds on multiparty communication complexity of shifts
53. Altmetric Badge
    Chapter 52 Some bounds on multiparty communication complexity of pointer jumping
54. Altmetric Badge
    Chapter 53 Optimal schedules for d-D grid graphs with communication delays
55. Altmetric Badge
    Chapter 54 Linear programming — Randomization and abstract frameworks