Reversible Computation

1. Front Matter

   PDF

2. Theoretical Considerations

   1. Tutorial: Graphical Calculus for Quantum Circuits

      • Bob Coecke, Ross Duncan

      Pages 1-13

   2. One-Way Reversible Multi-head Finite Automata

      • Martin Kutrib, Andreas Malcher

      Pages 14-28

   3. A Deterministic Two-Way Multi-head Finite Automaton Can Be Converted into a Reversible One with the Same Number of Heads

      • Kenichi Morita

      Pages 29-43

   4. Undecidability of the Surjectivity of the Subshift Associated to a Turing Machine

      • Rodrigo Torres, Nicolas Ollinger, Anahí Gajardo

      Pages 44-56

3. Reversible Software and Languages

   1. Isomorphic Interpreters from Logically Reversible Abstract Machines

      • Roshan P. James, Amr Sabry

      Pages 57-71

   2. Synthesizing Loops for Program Inversion

      • Cong Hou, Daniel Quinlan, David Jefferson, Richard Fujimoto, Richard Vuduc

      Pages 72-84

   3. Frugal Encoding in Reversible \(\mathcal{MOQA}\): A Case Study for Quicksort

      • Diarmuid Early, Ang Gao, Michel Schellekens

      Pages 85-96

   4. Towards a General-Purpose, Reversible Language for Controlling Self-reconfigurable Robots

      • Ulrik Pagh Schultz

      Pages 97-111

4. Reversible and Quantum Circuits

   1. Reversible and Quantum Circuit Optimization: A Functional Approach

      • Zahra Sasanian, D. Michael Miller

      Pages 112-124

   2. Properties of Quantum Templates

      • Md. Mazder Rahman, Gerhard W. Dueck

      Pages 125-137

   3. Optimal 4-bit Reversible Mixed-Polarity Toffoli Circuits

      • Marek Szyprowski, Paweł Kerntopf

      Pages 138-151

   4. Design of an Online Testable Ternary Circuit from the Truth Table

      • Noor M. Nayeem, Jacqueline E. Rice

      Pages 152-159

5. Physical Realizations and Design

   1. Garbageless Reversible Implementation of Integer Linear Transformations

      • Stéphane Burignat, Kenneth Vermeirsch, Alexis De Vos, Michael Kirkedal Thomsen

      Pages 160-170

   2. Garbage-Free Reversible Integer Multiplication with Constants of the Form 2^k±2^l±1

      • Holger Bock Axelsen, Michael Kirkedal Thomsen

      Pages 171-182

   3. Property Checking of Quantum Circuits Using Quantum Multiple-Valued Decision Diagrams

      • Julia Seiter, Mathias Soeken, Robert Wille, Rolf Drechsler

      Pages 183-196

   4. Using πDDs in the Design of Reversible Circuits

      • Mathias Soeken, Robert Wille, Shin-ichi Minato, Rolf Drechsler

      Pages 197-203

6. Distributed Systems

   1. A Verification Technique for Reversible Process Algebra

      • Jean Krivine

      Pages 204-217

   2. A Reversible Process Calculus and the Modelling of the ERK Signalling Pathway

      • Iain Phillips, Irek Ulidowski, Shoji Yuen

      Pages 218-232

   3. Controlled Reversibility and Compensations

      • Ivan Lanese, Claudio Antares Mezzina, Jean-Bernard Stefani

      Pages 233-240

This book constitutes the refereed proceedings of the 4th International Workshop on Reversible Computation, RC 2012, held in Copenhagen, Denmark, in July 2012. The 19 contributions presented in this volume were carefully reviewed and selected from 46 submissions. The papers cover theoretical considerations, reversible software and reversible hardware, and physical realizations and applications in quantum computing.

• distributed systems
• finite automata
• program inversion
• quantum circuits
• reversible circuits
• algorithm analysis and problem complexity

• DIKU, Department of Computer Science, University of Copenhagen, Copenhagen, Denmark

  Robert Glück

• Department of Software Engineering, Nanzan University, Seto, Japan

  Tetsuo Yokoyama

Policies and ethics