22 Result(s)
-
Chapter and Conference Paper
Elements of a Reversible Object-Oriented Language
This paper presents initial ideas for the design and implementation of a reversible object-oriented language based on extending Janus with object-oriented concepts such as classes that encapsulate behavior and...
-
Chapter and Conference Paper
A Classical Propositional Logic for Reasoning About Reversible Logic Circuits
We propose a syntactic representation of reversible logic circuits in their entirety, based on Feynman’s control interpretation of Toffoli’s reversible gate set. A pair of interacting proof calculi for reasoni...
-
Chapter and Conference Paper
Reversible Shrinking Two-Pushdown Automata
The deterministic shrinking two-pushdown automata characterize the deterministic growing context-sensitive languages, known to be the Church-Rosser languages. Here, we initiate the investigation of reversible two...
-
Chapter and Conference Paper
Boosting Reversible Pushdown Machines by Preprocessing
It is well known that reversible finite automata do not accept all regular languages and that reversible pushdown automata do not accept all deterministic context-free languages. It is of significant interest ...
-
Chapter and Conference Paper
The Degree of Irreversibility in Deterministic Finite Automata
Recently, Holzer et al. gave a method to decide whether the language accepted by a given deterministic finite automaton (DFA) can also be accepted by some reversible deterministic finite automaton (REV-DFA), and ...
-
Chapter and Conference Paper
Join Inverse Categories as Models of Reversible Recursion
Recently, a number of reversible functional programming languages have been proposed. Common to several of these is the assumption of totality, a property that is not necessarily desirable, and certainly not r...
-
Chapter and Conference Paper
Programming Techniques for Reversible Comparison Sorts
A common approach to reversible programming is to reversibly simulate an irreversible program with the desired functionality, which in general puts additional pressure on the computational resources (time, spa...
-
Chapter and Conference Paper
Towards a Domain-Specific Language for Reversible Assembly Sequences
Programming industrial robots for small-sized batch production of assembly operations is challenging due to the difficulty of precisely specifying general yet robust assembly operations. We observe that as the...
-
Chapter and Conference Paper
A Hierarchy of Fast Reversible Turing Machines
Reversible Turing machines with a working tape and a one-way or two-way read-only input tape are considered. We investigate the classes of languages acceptable by such devices with small time bounds in the ran...
-
Chapter and Conference Paper
Strength of the Reversible, Garbage-Free 2 k ±1 Multiplier
Recently, a reversible garbage-free 2 k ±1 constant-multiplier circuit was presented by Axelsen and Thomsen. This was the first construction of a garbage-free, reversible circui...
-
Chapter and Conference Paper
Garbage-Free Reversible Integer Multiplication with Constants of the Form 2 k ±2 l ±1
Multiplication of integers is non-injective and, thus, requires garbage lines for any reversible logic implementation. However, multiplying with a fixed constant is injective, and should therefore be implementabl...
-
Chapter and Conference Paper
Reversible Representation and Manipulation of Constructor Terms in the Heap
We currently have limited understanding of how complex data (e.g. algebraic data types) can be represented and manipulated in reversible machine code, in particular without generating garbage. In this paper we pr...
-
Chapter and Conference Paper
Reversible Multi-head Finite Automata Characterize Reversible Logarithmic Space
Deterministic and non-deterministic multi-head finite automata are known to characterize the deterministic and non- deterministic logarithmic space complexity classes, respectively. Recently, Morita introduced re...
-
Chapter and Conference Paper
Time Complexity of Tape Reduction for Reversible Turing Machines
Studies of reversible Turing machines (RTMs) often differ in their use of static resources such as the number of tapes, symbols and internal states. However, the interplay between such resources and computational...
-
Chapter and Conference Paper
Towards a Reversible Functional Language
We identify concepts of reversibility for a functional language by means of a set of semantic rules with specific properties. These properties include injectivity along with local backward determinism, an impo...
-
Chapter and Conference Paper
A Reversible Processor Architecture and Its Reversible Logic Design
We describe the design of a purely reversible computing architecture, Bob, and its instruction set, BobISA. The special features of the design include a simple, yet expressive, locally-invertible instruction s...
-
Chapter and Conference Paper
A Simple and Efficient Universal Reversible Turing Machine
We construct a universal reversible Turing machine (URTM) from first principles. We take a strict approach to the semantics of reversible Turing machines (RTMs), under which they can compute exactly all injective
-
Chapter and Conference Paper
What Do Reversible Programs Compute?
Reversible computing is the study of computation models that exhibit both forward and backward determinism. Understanding the fundamental properties of such models is not only relevant for reversible programmi...
-
Chapter and Conference Paper
Clean Translation of an Imperative Reversible Programming Language
We describe the translation techniques used for the code generation in a compiler from the high-level reversible imperative programming language Janus to the low-level reversible assembly language PISA. Our tr...
-
Chapter and Conference Paper
Parallel Optimization of a Reversible (Quantum) Ripple-Carry Adder
The design of fast arithmetic logic circuits is an important research topic for reversible and quantum computing. A special challenge in this setting is the computation of standard arithmetical functions witho...
