A Simple Construction Method of a Reversible Finite Automaton out of Fredkin Gates, and Its Related Problem
The Transactions of the IEICE E73 巻 6 号
978-984 頁
1990-06-25 発行
アクセス数 : 412 件
ダウンロード数 : 79 件
今月のアクセス数 : 5 件
今月のダウンロード数 : 1 件
この文献の参照には次のURLをご利用ください : https://ir.lib.hiroshima-u.ac.jp/00048450
| ファイル情報(添付) | |
| タイトル ( eng ) |
A Simple Construction Method of a Reversible Finite Automaton out of Fredkin Gates, and Its Related Problem
|
| 作成者 | |
| 収録物名 |
The Transactions of the IEICE
|
| 巻 | E73 |
| 号 | 6 |
| 開始ページ | 978 |
| 終了ページ | 984 |
| 抄録 |
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.
|
| 著者キーワード |
reversible computing
reversible sequential machine
Fredkin gate
|
| 言語 |
英語
|
| 資源タイプ | 学術雑誌論文 |
| 出版者 |
電子情報通信学会
|
| 発行日 | 1990-06-25 |
| 権利情報 |
Copyright (c) 1990 IEICE
|
| 出版タイプ | Version of Record（出版社版。早期公開を含む） |
| アクセス権 | オープンアクセス |
| 収録物識別子 |
[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/
|
