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

Wolfgang Thomas (auth.), Ernst W. Mayr, Claude Puech (eds.)3540590420, 9783540590422

This book presents the proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science (STACS 95), held in Munich, Germany in March 1995.
Besides three invited talks, the book contains revised versions of 53 research papers selected from a total of 180 submissions. The contributions address all current aspects of theoretical computer science; they are organized in sections on complexity theory, automata theory, algorithms, logic, theory of parallel computing, communication theory, graph theory and databases, and computational geometry.

---

Table of contents :
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