Computing with New Resources: Essays Dedicated to Jozef Gruska on the Occasion of His 80th Birthday (Lecture Notes in Computer Science, 8808)

Professor Jozef Gruska is a well known computer scientist for his many and broad results. He was the father of theoretical computer science research in Czechoslovakia and among the first Slovak programmers in the early 1960s. Jozef Gruska introduced the descriptional complexity of grammars, automata, and languages, and is one of the pioneers of parallel (systolic) automata. His other main research interests include parallel systems and automata, as well as quantum information processing, transmission, and cryptography. He is co-founder of four regular series of conferences in informatics and two in quantum information processing and the Founding Chair (1989-96) of the IFIP Specialist Group on Foundations of Computer Science. Front Matter....Pages I-XXI Front Matter....Pages 1-1 Counting with Probabilistic and Ultrametric Finite Automata....Pages 3-16 Systolic Automata and P Systems....Pages 17-31 Soliton Automata with Multiple Waves....Pages 32-48 On Power Series over a Graded Monoid....Pages 49-55 Advances on Random Sequence Generation by Uniform Cellular Automata....Pages 56-70 On the Determinization Blowup for Finite Automata Recognizing Equal-Length Languages....Pages 71-82 Aspects of Reversibility for Classical Automata....Pages 83-98 A Weakly Universal Cellular Automaton in the Pentagrid with Five States....Pages 99-113 Minimum and non-Minimum Time Solutions to the Firing Squad Synchronization Problem....Pages 114-128 Time-Optimum Smaller-State Synchronizers for Cellular Automata....Pages 129-145 Front Matter....Pages 147-147 Computing Boolean Functions via Quantum Hashing....Pages 149-160 Complexity of Promise Problems on Classical and Quantum Automata....Pages 161-175 Quantum Complexity of Boolean Matrix Multiplication and Related Problems....Pages 176-191 Quantum Distributed Computing Applied to Grover’s Search Algorithm....Pages 192-199 Maximally Entangled State in Pseudo-Telepathy Games....Pages 200-207 Quantum Finite Automata: A Modern Introduction....Pages 208-222 Physical Aspects of Oracles for Randomness and Hadamard’s Conjecture....Pages 223-230 From Quantum Query Complexity to State Complexity....Pages 231-245 Front Matter....Pages 247-247 Small Universal Devices....Pages 249-263 A Technique to Obtain Hardness Results for Randomized Online Algorithms – A Survey....Pages 264-276 Front Matter....Pages 247-247 Integral Difference Ratio Functions on Integers....Pages 277-291 Conditional Lindenmayer Systems with Conditions Defined by Bounded Resources....Pages 292-306 Symmetries and Dualities in Name-Passing Process Calculi....Pages 307-322 Learning from Positive Data and Negative Counterexamples: A Survey....Pages 323-337 One-Sided Random Context Grammars: A Survey....Pages 338-351 How Can We Construct Reversible Machines Out of Reversible Logic Element with Memory?....Pages 352-366 On Evolutionary Approximation of Logic Circuits....Pages 367-378 A Distributed Computing Model for Dataflow, Controlflow, and Workflow in Fractionated Cyber-Physical Systems....Pages 379-393 On the Limit of Some Algorithmic Approach to Circuit Lower Bounds....Pages 394-405 Front Matter....Pages 407-407 P Systems with Anti-Matter....Pages 409-420 A Robust Universal Flying Amorphous Computer....Pages 421-435 Minimal Reaction Systems Defining Subset Functions....Pages 436-446 Front Matter....Pages 447-447 Grand Challenges of Informatics....Pages 449-461 Konrad Zuse’s Relationship to Informatics....Pages 462-471 Back Matter....Pages 473-473