Richard M. Karp (auth.), Michel Morvan, Christoph Meinel, Daniel Krob (eds.)3540642307, 9783540642305
The volume presents three invited surveys together with 52 revised full papers selected from a total of 155 submissions. The papers are organized in topical sections on algorithms and data structures, logic, complexity, and automata and formal languages.
Table of contents :
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
Reviews
There are no reviews yet.