STACS 95: 12th Annual Symposium on Theoretical Aspects of Computer Science Munich, Germany, March 2–4, 1995 Proceedings

On the synthesis of strategies in infinite games....Pages 1-13
Finding the maximum with linear error probabilities: a sequential analysis approach....Pages 14-25
Completeness and weak completeness under polynomial-size circuits....Pages 26-37
Communication complexity of key agreement on small ranges....Pages 38-49
Pseudorandom generators and the frequency of simplicity....Pages 50-59
Classes of bounded counting type and their inclusion relations....Pages 60-70
Lower bounds for depth-three circuits with equals and mod-gates....Pages 71-82
On realizing iterated multiplication by small depth threshold circuits....Pages 83-94
A random NP-complete problem for inversion of 2D cellular automata....Pages 95-106
On the subword equivalence problem for infinite words....Pages 107-118
On the separators on an infinite word generated by a morphism....Pages 119-130
Systolic tree ω-languages....Pages 131-142
Structural complexity of ω-automata....Pages 143-156
Algorithms explained by symmetries....Pages 157-167
Generalized scans and tri-diagonal systems....Pages 168-180
Two-dimensional pattern matching in linear time and small space....Pages 181-192
On-line and dynamic algorithms for shortest path problems....Pages 193-204
On compact representations of propositional circumscription....Pages 205-216
A set-theoretic translation method for (poly)modal logics....Pages 217-228
On the synthesis of discrete controllers for timed systems....Pages 229-242
A fully abstract semantics for causality in the π-calculus....Pages 243-254
On the sizes of permutation networks and consequences for efficient simulation of hypercube algorithms on bounded-degree networks....Pages 255-266
Exploiting storage redundancy to speed up randomized shared memory simulations....Pages 267-278
Interval routing schemes....Pages 279-290
A packet routing protocol for arbitrary networks....Pages 291-302
A family of tag systems for paperfolding sequences....Pages 303-312
Growing context-sensitive languages and Church-Rosser languages....Pages 313-324
Deterministic generalized automata....Pages 325-336
Optimal simulation of automata by neural nets....Pages 337-348
Concurrent process equivalences: Some decision problems....Pages 349-349
Optimal lower bounds on the multiparty communication complexity....Pages 350-360
Simultaneous messages vs. communication....Pages 361-372
Coding and strong coding in trace monoids....Pages 373-384
On codings of traces....Pages 385-396
Finding largest common embeddable subtrees....Pages 397-408
The χt-coloring problem....Pages 409-420
Expander properties in random regular graphs with edge faults....Pages 421-432
Dynamic analysis of the sizes of relations....Pages 433-444
On slender context-free languages....Pages 445-454
Partial derivatives of regular expressions and finite automata constructions....Pages 455-466
Dependence orders for computations of concurrent automata....Pages 467-478
On the undecidability of deadlock detection in families of nets....Pages 479-490
On the average running time of odd-even merge sort....Pages 491-502
Optimal average case sorting on arrays....Pages 503-514
Normal numbers and sources for BPP....Pages 515-526
Lower bounds on learning decision lists and trees....Pages 527-538
Line segmentation of digital curves in parallel....Pages 539-549
Computability of convex sets....Pages 550-561
Enumerating extreme points in higher dimensions....Pages 562-570
The number of views of piecewise-smooth algebraic objects....Pages 571-582
On the structure of log-space probabilistic complexity classes....Pages 583-596
Resource-bounded instance complexity....Pages 597-608
On the sparse set conjecture for sets with low density....Pages 609-618
Beyond P NP =NEXP....Pages 619-627
Malign distributions for average case circuit complexity....Pages 628-639
A possible code in the genetic code....Pages 640-651