Skip to main content
SpringerLink
Log in
Book cover

Computing with New Resources

Essays Dedicated to Jozef Gruska on the Occasion of His 80th Birthday

  • Book
  • © 2014

Overview

Editors:
  1. Cristian S. Calude

    1. Department of Computer Science, The University of Auckland, Auckland, New Zealand

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Rūsiņš Freivalds

    1. University of Latvia, Riga, Latvia

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Iwama Kazuo

    1. School of Informatics, Kyoto University, Kyoto, Japan

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  • Features high-quality, selected papers, and essays
  • Honors Jozef Gruska, the founder of theoretical computer science in Czechoslovakia
  • State of the art contents
  • Includes supplementary material: sn.pub/extras

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 8808)

Part of the book sub series: Theoretical Computer Science and General Issues (LNTCS)

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (34 chapters)

  1. Front Matter

    Pages I-XXI
    Download chapter PDF

  2. Computing with Automata: Classical, Cellular and Systolic

    1. Front Matter

      Pages 1-1
      Download chapter 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
      Download chapter 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
Back to top

Keywords

About this book

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.

Editors and Affiliations

  • 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

About the editors

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.

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation