STACS 98: 15th Annual Symposium on Theoretical Aspects of Computer Science Paris, France, February 25–27, 1998 Proceedings

Random graphs, random walks, differential equations and the probabilistic analysis of algorithms....Pages 1-2
Distributed online frequency assignment in cellular networks....Pages 3-13
Floats, integers, and single source shortest paths....Pages 14-24
A synthesis on partition refinement: A useful routine for strings, graphs, boolean matrices and automata....Pages 25-38
Simplifying the modal mu-calculus alternation hierarchy....Pages 39-49
On disguised double horn functions and extensions....Pages 50-60
The complexity of propositional linear temporal logics in simple cases....Pages 61-72
Searching constant width mazes captures the A C 0 hierarchy....Pages 73-83
Nearly optimal language compression using extractors....Pages 84-93
Random sparse bit strings at the threshold of adjacency....Pages 94-104
Lower bounds for randomized read- k -times branching programs....Pages 105-115
Inducing an order on cellular automata by a grouping operation....Pages 116-127
Attractors of D -dimensional Linear Cellular Automata....Pages 128-138
Optimal simulations between unary automata....Pages 139-149
Shuffle of ω -words: Algebraic aspects....Pages 150-160
A generalization of resource-bounded measure, with an application (Extended abstract)....Pages 161-171
The complexity of modular graph automorphism....Pages 172-182
Unary quantifiers, transitive closure, and relations of large degree....Pages 183-193
On the structure of valiant's complexity classes....Pages 194-204
On the existence of polynomial time approximation schemes for OBDD minimization....Pages 205-215
Complexity of problems on graphs represented as OBDDs....Pages 216-226
Equivalence test and ordering transformation for parity-OBDDs of different variable ordering....Pages 227-237
Size and structure of random ordered binary decision diagrams....Pages 238-248
Provable security for block ciphers by decorrelation....Pages 249-275
On the approximation of finding A(nother) Hamiltonian cycle in cubic Hamiltonian graphs....Pages 276-286
The mutual exclusion scheduling problem for permutation and comparability graphs....Pages 287-297
Massaging a linear programming solution to give a 2-approximation for a generalization of the vertex cover problem....Pages 298-308
Partially persistent search trees with transcript operations....Pages 309-319
Relating hierarchies of word and tree automata....Pages 320-331
Languages defined with modular counting quantifiers....Pages 332-343
Hierarchies of principal twist-closed trios....Pages 344-355
Radix representations of algebraic number fields and finite automata....Pages 356-365
Sorting and searching on the word RAM....Pages 366-398
Communication-efficient deterministic parallel algorithms for planar point location and 2d Voronoi Diagram....Pages 399-409
On Batcher's merge sorts as parallel sorting algorithms....Pages 410-420
Minimum spanning trees for minor-closed graph classes in parallel....Pages 421-431
Optimal broadcasting in almost trees and partial k -trees....Pages 432-443
Local normal forms for first-order logic with applications to games and automata....Pages 444-454
Axiomatizing the equational theory of regular tree languages....Pages 455-465
A Logical Characterization of Systolic Languages....Pages 466-476
Optimal proof systems for propositional logic and complete sets....Pages 477-487
The (parallel) approximability of non-boolean satisfiability problems and restricted integer programming....Pages 488-498
Interactive protocols on the reals....Pages 499-510
Result-indistinguishable zero-knowledge proofs: Increased power and constant-round protocols....Pages 511-521
Bounded size dictionary compression: SC k -completeness and NC algorithms....Pages 522-532
Expressive completeness of LTrL on finite traces: An algebraic proof....Pages 533-543
On uniform DOL words....Pages 544-554
Series-parallel posets: Algebra, automata and languages....Pages 555-565
On the expected number of nodes at level k in 0-balanced trees....Pages 566-576
Cell flipping in permutation diagrams....Pages 577-586
Construction of non-intersecting colored flows through a planar cellular figure....Pages 587-595
Recursively enumerable reals and chaitin Ω numbers....Pages 596-606
Uniformly defining complexity classes of functions....Pages 607-617
Recognizability equals monadic second-order definability for sets of graphs of bounded tree-width....Pages 618-628