STACS 96: 13th Annual Symposium on Theoretical Aspects of Computer Science Grenoble, France, February 22–24, 1996 Proceedings

Gilles Brassard (auth.), Claude Puech, Rüdiger Reischuk (eds.)3540609229, 9783540609223

This book constitutes the refereed proceedings of the 13th Symposium on Theoretical Aspects of Computer Science, STACS 96, held in Grenoble, France in February 1996.
The 52 revised papers presented were selected from a total of 185 submissions; also included are three invited papers. The volume addresses all current aspects of theoretical computer science and is organized in sections on complexity theory, automata theory, parallel algorithms, learning, parallel and distributed systems, cryptography, logic and database theory, algorithms, semantics and program verification, and communication complexity.

---

Table of contents :
New trends in quantum computing….Pages 1-10
Compressibility and resource bounded measure….Pages 11-24
On the complexity of random strings….Pages 25-36
Remarks on generalized Post Correspondence Problem….Pages 37-48
Cyclic languages and strongly cyclic languages….Pages 49-59
Resource-bounded balanced genericity, stochasticity and weak randomness….Pages 61-74
The complexity of generating and checking proofs of membership….Pages 75-86
Solvable black-box group problems are low for PP….Pages 87-97
Languages recognized by finite aperiodic groupoids….Pages 99-110
Star-height of an N -rational series….Pages 111-124
An aperiodic set of Wang cubes….Pages 125-135
Lyndon factorization of infinite words….Pages 137-146
Embedding graphs with bounded treewidth into optimal hypercubes….Pages 147-154
Parallel comparability graph recognition and modular decomposition….Pages 155-168
Fault-tolerant shared memory simulations….Pages 169-180
On word-level parallelism in fault-tolerant computing….Pages 181-192
Learning with confidence….Pages 193-204
Extracting best consensus motifs from positive and negative examples….Pages 205-218
PAC learning with simple examples….Pages 219-230
General inductive inference types based on linearly-ordered sets….Pages 231-242
On the power of non-observable actions in timed automata….Pages 243-253
Trace rewriting: Computing normal forms in time O ( n log n )….Pages 255-268
A decision procedure for well-formed linear quantum cellular automata….Pages 269-280
On the complexity of worst case and expected time in a circuit….Pages 281-292
On the existence of hard sparse sets under weak reductions….Pages 293-306
Optimal bounds on the approximation of boolean functions with consequences on the concept of hardness….Pages 307-318
Fine separation of average time complexity classes….Pages 319-330
Compositional specification of timed systems….Pages 331-343
Optimal tree-based one-time digital signature schemes….Pages 345-359
The action of a few random permutations on r -tuples and an application to cryptography….Pages 361-374
A unified and generalized treatment of authentication theory….Pages 375-386
Monadic second order logic on tree-like structures….Pages 387-398
On bijections vs. unary functions….Pages 399-413
The 3 Frenchmen method proves undecidability of the uniform boundedness for single recursive rule ternary DATALOG Programs….Pages 415-426
A combinatorial design approach to MAXCUT….Pages 427-438
Characterizing the complexity of subgraph isomorphism for graphs of bounded path-width….Pages 439-452
A characterization of the quadrilateral meshes of a surface which admit a compatible hexahedral mesh of the enclosed volume….Pages 453-464
On the expressivity of the modal mu-calculus….Pages 465-476
Read-once projections and formal circuit verification with binary decision diagrams….Pages 477-490
“Optimal” collecting semantics for analysis in a hierarchy of logic program semantics….Pages 491-502
Flip-flop nets….Pages 503-514
Lower bounds for compact routing….Pages 515-528
On the successor function in non-classical numeration systems….Pages 529-540
Minimal forbidden words and symbolic dynamics….Pages 541-553
Universal hashing and k -wise independent random variables via integer arithmetic without primes….Pages 555-566
Ranking and unranking trees using regular reductions….Pages 567-580
On competitive on-line paging with lookahead….Pages 581-592
Hypothesis testing in perfect phylogeny for a bounded number of characters….Pages 593-603
The “log rank” conjecture for modular communication complexity….Pages 605-616
Upper bounds on multiparty communication complexity of shifts….Pages 617-630
Some bounds on multiparty communication complexity of pointer jumping….Pages 631-642
Optimal schedules for d-D grid graphs with communication delays….Pages 643-654
Linear programming — Randomization and abstract frameworks….Pages 655-666
….Pages 667-687