Proceedings / STACS 2006

More about the book

The Ubiquitous Digital Tree explores various computational theories and algorithms, including flat holonomies on automata networks and the interprocedural analysis of polynomial identities. It delves into external string sorting techniques that are faster and cache-oblivious, and discusses amortized rigidness in dynamic Cartesian trees. The text covers distribution-sensitive construction of minimum-redundancy prefix codes and critical exponents in fixed points of binary k-uniform morphisms. It examines equivalence of -algebras and cubic forms, complete codes in sofic shifts, and the complexities of Kolmogorov with error and recursion theorems. The book also investigates entanglement in interactive proof systems, quantum algorithms for matching and network flows, and improved analyses of string runs. It presents algorithms for demand-robust min-cut and shortest path problems, along with discussions on the exact price of anarchy in polynomial congestion games. Other topics include oblivious symmetric alternation, conflict-free colorings of rectangles, grid vertex-unfolding orthogonal polyhedra, and invariants of automatic presentations. Further, it addresses the accepting power of 2-tape Büchi automata, weighted picture automata, and Markov decision processes with multiple objectives. The text highlights algorithmic structures in cost-sharing mechanisms, convergence in potential games, and tradeoffs in superconcentrators. It c