Adventures Between Lower Bounds and Higher Altitudes: Essays Dedicated to Juraj Hromkovič on the Occasion of His 60th Birthday

Description

This Festschrift volume is published in honor of Juraj Hromkovič on the occasion of his 60th birthday. Juraj Hromkovič is a leading expert in the areas of automata and complexity theory, algorithms for hard problems, and computer science education. The contributions in this volume reflect the breadth and impact of his work. The volume contains 35 full papers related to Juraj Hromkovič’s research. They deal with various aspects of the complexity of finite automata, the information content of online problems, stability of approximation algorithms, reoptimization algorithms, computer science education, and many other topics within the fields of algorithmics and complexity theory. Moreover, the volume contains a prologue and an epilogue of laudatios from several collaborators, colleagues, and friends. Front Matter ....Pages I-XXIV Front Matter ....Pages 1-1 Determinism and Nondeterminism in Finite Automata with Advice (Pavol Ďuriš, Rafael Korbaš, Rastislav Královič, Richard Královič)....Pages 3-16 A Survey on Fooling Sets as Effective Tools for Lower Bounds on Nondeterministic Complexity (Michal Hospodár, Galina Jirásková, Peter Mlynárčik)....Pages 17-32 Optimal 2DFA Algorithms for One-Way Liveness on Two and Three Symbols (Christos A. Kapoutsis)....Pages 33-48 Regularity of k-Abelian Equivalence Classes of Fixed Cardinality (Juhani Karhumäki, Markus A. Whiteland)....Pages 49-62 Reaction Systems, Transition Systems, and Equivalences (Jetty Kleijn, Maciej Koutny, Łukasz Mikulski, Grzegorz Rozenberg)....Pages 63-84 On Usefulness of Information: Framework and NFA Case (Branislav Rovan, Šimon Sádovský)....Pages 85-99 Parikh Matrices: Subword Indicators and Degrees of Ambiguity (Arto Salomaa)....Pages 100-112 Probabilism versus Alternation for Automata (Georg Schnitger)....Pages 113-126 Front Matter ....Pages 127-127 Classical and Quantum Computations with Restricted Memory (Farid Ablayev, Marat Ablayev, Kamil Khadiev, Alexander Vasiliev)....Pages 129-155 Stability of Reapproximation Algorithms for the \(\beta \)-Metric Traveling Salesman (Path) Problem (Annalisa D’Andrea, Luca Forlizzi, Guido Proietti)....Pages 156-171 Fully Online Matching with Advice on General Bipartite Graphs and Paths (Hans-Joachim Böckenhauer, Lucia Di Caro, Walter Unger)....Pages 172-190 Sequence Hypergraphs: Paths, Flows, and Cuts (Kateřina Böhmová, Jérémie Chalopin, Matúš Mihalák, Guido Proietti, Peter Widmayer)....Pages 191-215 Relative Worst-Order Analysis: A Survey (Joan Boyar, Lene M. Favrholdt, Kim S. Larsen)....Pages 216-230 Length-Weighted Disjoint Path Allocation (Elisabet Burjons, Fabian Frei, Jasmin Smula, David Wehner)....Pages 231-256 Universal Hashing via Integer Arithmetic Without Primes, Revisited (Martin Dietzfelbinger)....Pages 257-279 Small Complexity Gaps for Comparison-Based Sorting (Shogo Ehara, Kazuo Iwama, Junichi Teruyama)....Pages 280-296 Online Matching in Regular Bipartite Graphs with Randomized Adversary (Josep Fàbrega, Xavier Muñoz)....Pages 297-310 A Dynamic Distributed Data Structure for Top-k and k-Select Queries (Björn Feldkord, Manuel Malatyali, Friedhelm Meyer auf der Heide)....Pages 311-329 What Is Known About Vertex Cover Kernelization? (Michael R. Fellows, Lars Jaffke, Aliz Izabella Király, Frances A. Rosamond, Mathias Weller)....Pages 330-356 A Survey on the Complexity of Flood-Filling Games (Michael R. Fellows, Frances A. Rosamond, Maise Dantas da Silva, Uéverton S. Souza)....Pages 357-376 Infinity and Finite Arithmetic (Walter Gander)....Pages 377-392 A Modern View on Stability of Approximation (Ralf Klasing, Tobias Mömke)....Pages 393-408 \(\mathcal {NP}\)-Hardness of Equilibria in Case of Risk-Averse Players (Marios Mavronicolas, Burkhard Monien)....Pages 409-422 Firefly-Inspired Algorithm for Job Shop Scheduling (Joss Miller-Todd, Kathleen Steinhöfel, Patrick Veenstra)....Pages 423-433 Rendezvous of Asynchronous Mobile Robots with Lights (Takashi Okumura, Koichi Wada, Yoshiaki Katayama)....Pages 434-448 On the Advice Complexity of Online Edge- and Node-Deletion Problems (Peter Rossmanith)....Pages 449-462 Second Thoughts on the Second Law (Stefan Wolf)....Pages 463-476 Reoptimization of NP-Hard Problems (Anna Zych-Pawlewicz)....Pages 477-494 Front Matter ....Pages 495-495 CS Unplugged—How Is It Used, and Does It Work? (Tim Bell, Jan Vahrenhold)....Pages 497-521 Resurgence of Informatics Education in Schools (Valentina Dagienė)....Pages 522-537 The Adventure of Computer Science (Jens Gallenbacher)....Pages 538-548 Toward Scenario-Based Algorithmics (David Harel, Assaf Marron)....Pages 549-567 That Most Important Intersection (Lane A. Hemaspaandra)....Pages 568-589 Paving the Way for Computer Science in German Schools (Ulrik Schroeder, Nadine Bergner, Thiemo Leonhardt)....Pages 590-609 A Master Class on Recursion (Tom Verhoeff)....Pages 610-633 Front Matter ....Pages 635-635 About Place Cells and Grid Cells (Christos H. Papadimitriou)....Pages 637-640 Back Matter ....Pages 641-642