A Simple Construction Method of a Reversible Finite Automaton out of Fredkin Gates, and Its Related Problem

Kenichi MORITA

A Simple Construction Method of a Reversible Finite Automaton out of Fredkin Gates, and Its Related Problem

Kenichi MORITA

Full Text Views

0

Share
Cite this

Summary :

A reversible finite automaton (RFA) is a backward deterministic automaton, i.e., it can uniquely retrace its move sequence if the inverse sequence of its outputs is given. In this paper, we show a simple method to construct an RFA from Fredkin gates, which are reversible and bit-conserving logic gates, and unit wires (unit delays). The resulting circuit obtained by this method is garbage-less" in the sense that it has no inputs to which constants must be supplied nor outputs from which garbage signals are put out. We also show that a one-dimensional reversible partitioned cellular automaton, which are known to be computation universal, can be constructed from Fredkin gates and unit wires as a closed (thus garbage-less) infinite circuit.

Publication: IEICE TRANSACTIONS on transactions Vol.E73-E No.6 pp.978-984

Publication Date: 1990/06/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Automaton, Language and Theory of Computing

Authors

Kenichi MORITA

Keyword

Cite this

Copy

Kenichi MORITA, "A Simple Construction Method of a Reversible Finite Automaton out of Fredkin Gates, and Its Related Problem" in IEICE TRANSACTIONS on transactions, vol. E73-E, no. 6, pp. 978-984, June 1990, doi: .
Abstract: A reversible finite automaton (RFA) is a backward deterministic automaton, i.e., it can uniquely retrace its move sequence if the inverse sequence of its outputs is given. In this paper, we show a simple method to construct an RFA from Fredkin gates, which are reversible and bit-conserving logic gates, and unit wires (unit delays). The resulting circuit obtained by this method is garbage-less" in the sense that it has no inputs to which constants must be supplied nor outputs from which garbage signals are put out. We also show that a one-dimensional reversible partitioned cellular automaton, which are known to be computation universal, can be constructed from Fredkin gates and unit wires as a closed (thus garbage-less) infinite circuit.
URL: https://globals.ieice.org/en_transactions/transactions/10.1587/e73-e_6_978/_p

Copy

@ARTICLE{e73-e_6_978,
author={Kenichi MORITA, },
journal={IEICE TRANSACTIONS on transactions},
title={A Simple Construction Method of a Reversible Finite Automaton out of Fredkin Gates, and Its Related Problem},
year={1990},
volume={E73-E},
number={6},
pages={978-984},
abstract={A reversible finite automaton (RFA) is a backward deterministic automaton, i.e., it can uniquely retrace its move sequence if the inverse sequence of its outputs is given. In this paper, we show a simple method to construct an RFA from Fredkin gates, which are reversible and bit-conserving logic gates, and unit wires (unit delays). The resulting circuit obtained by this method is garbage-less" in the sense that it has no inputs to which constants must be supplied nor outputs from which garbage signals are put out. We also show that a one-dimensional reversible partitioned cellular automaton, which are known to be computation universal, can be constructed from Fredkin gates and unit wires as a closed (thus garbage-less) infinite circuit.},
keywords={},
doi={},
ISSN={},
month={June},}

Copy

TY - JOUR
TI - A Simple Construction Method of a Reversible Finite Automaton out of Fredkin Gates, and Its Related Problem
T2 - IEICE TRANSACTIONS on transactions
SP - 978
EP - 984
AU - Kenichi MORITA
PY - 1990
DO -
JO - IEICE TRANSACTIONS on transactions
SN -
VL - E73-E
IS - 6
JA - IEICE TRANSACTIONS on transactions
Y1 - June 1990
AB - A reversible finite automaton (RFA) is a backward deterministic automaton, i.e., it can uniquely retrace its move sequence if the inverse sequence of its outputs is given. In this paper, we show a simple method to construct an RFA from Fredkin gates, which are reversible and bit-conserving logic gates, and unit wires (unit delays). The resulting circuit obtained by this method is garbage-less" in the sense that it has no inputs to which constants must be supplied nor outputs from which garbage signals are put out. We also show that a one-dimensional reversible partitioned cellular automaton, which are known to be computation universal, can be constructed from Fredkin gates and unit wires as a closed (thus garbage-less) infinite circuit.
ER -