A Simple Construction Method of a Reversible Finite Automaton out of Fredkin Gates, and Its Related Problem
The Transactions of the IEICE Volume E73 Issue 6
Page 978-984
published_at 1990-06-25
アクセス数 : 411 件
ダウンロード数 : 78 件
今月のアクセス数 : 4 件
今月のダウンロード数 : 0 件
この文献の参照には次のURLをご利用ください : https://ir.lib.hiroshima-u.ac.jp/00048450
| File | |
| Title ( eng ) |
A Simple Construction Method of a Reversible Finite Automaton out of Fredkin Gates, and Its Related Problem
|
| Creator | |
| Source Title |
The Transactions of the IEICE
|
| Volume | E73 |
| Issue | 6 |
| Start Page | 978 |
| End Page | 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 |
reversible computing
reversible sequential machine
Fredkin gate
|
| Language |
eng
|
| Resource Type | journal article |
| Publisher |
電子情報通信学会
|
| Date of Issued | 1990-06-25 |
| Rights |
Copyright (c) 1990 IEICE
|
| Publish Type | Version of Record |
| Access Rights | open access |
| Source Identifier |
[ISSN] 0913-574X
[NCID] AA10684666
[URI] https://search.ieice.org/bin/summary.php?id=e73-e_6_978&category=E&lang=E&year=1990&abst=
[URI] https://search.ieice.org/
|
