Computing with New Resources

1. Front Matter

   Pages I-XXI

   PDF

2. Computing with Automata: Classical, Cellular and Systolic

   1. Front Matter

      Pages 1-1

      PDF

   2. Counting with Probabilistic and Ultrametric Finite Automata

      • Kaspars Balodis

      Pages 3-16

   3. Systolic Automata and P Systems

      • Roberto Barbuti, Andrea Maggiolo-Schettini, Paolo Milazzo, Giovanni Pardini, Simone Tini

      Pages 17-31

   4. Soliton Automata with Multiple Waves

      • Henning Bordihn, Helmut Jürgensen, Heiko Ritter

      Pages 32-48

   5. On Power Series over a Graded Monoid

      • Zoltán Ésik, Werner Kuich

      Pages 49-55

   6. Advances on Random Sequence Generation by Uniform Cellular Automata

      • Enrico Formenti, Katsunobu Imai, Bruno Martin, Jean-Baptiste Yunès

      Pages 56-70

   7. On the Determinization Blowup for Finite Automata Recognizing Equal-Length Languages

      • Juhani Karhumäki, Alexander Okhotin

      Pages 71-82

   8. Aspects of Reversibility for Classical Automata

      • Martin Kutrib

      Pages 83-98

   9. A Weakly Universal Cellular Automaton in the Pentagrid with Five States

      • Maurice Margenstern

      Pages 99-113

   10. Minimum and non-Minimum Time Solutions to the Firing Squad Synchronization Problem

       • Margherita Napoli, Mimmo Parente

       Pages 114-128

   11. Time-Optimum Smaller-State Synchronizers for Cellular Automata

       • Hiroshi Umeo

       Pages 129-145

3. Computing with Quantum Resources

   1. Front Matter

      Pages 147-147

      PDF

   2. Computing Boolean Functions via Quantum Hashing

      • Farid Ablayev, Alexander Vasiliev

      Pages 149-160

   3. Complexity of Promise Problems on Classical and Quantum Automata

      • Maria Paola Bianchi, Carlo Mereghetti, Beatrice Palano

      Pages 161-175

   4. Quantum Complexity of Boolean Matrix Multiplication and Related Problems

      • François Le Gall

      Pages 176-191

   5. Quantum Distributed Computing Applied to Grover’s Search Algorithm

      • Debabrata Goswami

      Pages 192-199

   6. Maximally Entangled State in Pseudo-Telepathy Games

      • Laura Mančinska

      Pages 200-207

   7. Quantum Finite Automata: A Modern Introduction

      • A.C. Cem Say, Abuzer Yakaryılmaz

      Pages 208-222

   8. Physical Aspects of Oracles for Randomness and Hadamard’s Conjecture

      • Karl Svozil

      Pages 223-230

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.

• cellular automata
• circuit complexity
• computational complexity
• concurrency
• finite automata
• formal languages and automata theory
• history of computing
• logic
• quantum complexity theory
• quantum computing
• quantum technologies
• systolic automata
• theoretical computer science
• theory of computation
• algorithm analysis and problem complexity

• Department of Computer Science, The University of Auckland, Auckland, New Zealand

  Cristian S. Calude

• University of Latvia, Riga, Latvia

  Rūsiņš Freivalds

• School of Informatics, Kyoto University, Kyoto, Japan

  Iwama Kazuo

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.

Policies and ethics