42 件中 11 - 20 件目
| 年度 Year |
論文題目名 Title of the articles |
共著区分 Collaboration Classification |
NeoCILIUS 請求番号／資料ID Request No |
|---|---|---|---|
| 掲載誌名 Journal name，出版機関名 Publishing organization，巻／号 Vol./no.，頁数 Page nos.，発行年月（日） Date | |||
| 2018 | 二分木の辞書順のランク計算の効率的なクリーン可逆シミュレーション | 共著 | |
| 電子情報通信学会和文論文誌D ， 電子情報通信学会 ， Vol.J102-D, No.3 ， pp. 130-140 ， 2019/03/01 | |||
|
概要（Abstract） 可逆システム上で非可逆プログラムの可逆シミュレーションを実現するとき，既知の一般解法を用いると，元の入出力の走査回数と，元の入出力用以外のメモリ使用量が増え，元の出力以外を出力してクリーンでなくなってしまうという問題が起こる．しかし，非可逆なアルゴリズムに対して，経験と勘を元に個別の非可逆プログラムの効率的なクリーン可逆シミュレーションが実現されてきている．本稿では，可逆計算システムで用いる可逆アルゴリズムとして，二分木の列挙，二分木の辞書順のランク計算，および辞書順における次の二分木の生成の効率的なクリーン可逆シミュレーションの構築をする．これらは基礎的な可逆アルゴリズムであるので，他の可逆アルゴリズムの一部として使用されたり，可逆アルゴリズムの構築法が利用されたりすることが期待される．また，二分木のランク計算に関する効率的な可逆プログラムの整備を進めることで類似するランク計算やさらには現時点では困難な一般の効率的可逆シミュレーションの自動導出が可能になることが期待される．本稿の可逆プログラムは全てオンラインインタプリタで実行して振る舞いを確かめることが可能である． |
|||
|
備考（Remarks） 10.14923/transinfj.2018PDP0021 |
|||
| 2018 | 可逆プログラミング言語R-WHILEの可逆チューリング完全性 | 共著 | |
| 電子情報通信学会和文論文誌D ， 電子情報通信学会 ， J101-D, No.9 ， pp. 1372-1375 ， 2018/09/01 | |||
|
概要（Abstract） 任意の可逆プログラミング言語のプログラムで計算できるものが，可逆なR-WHILEプログラムによって計算できることを示す． |
|||
|
備考（Remarks） DOI: 10.14923/transinfj.2018JDL8008 |
|||
| 2018 | ハミルトン曲面流に対応する流れの向きを考慮した極大語の列挙アルゴリズム | 共著 | |
| 電子情報通信学会論文誌 D ， 電子情報通信学会 ， Vol.J101-D, No.8 ， pp. 1220-1222 ， 2018/08/01 | |||
|
概要（Abstract）
ハミルトン曲面流を表す流れの向きを考慮した極大語の表現法，任意の長さの極大語をもれなく重複無く列挙するアルゴリズム，及びステートチャートによる極大語の生成方法の簡潔な表現を示した．本手法で向きを考慮した流れの総数を見積もれる． |
|||
|
備考（Remarks） http://search.ieice.org/bin/summary.php?id=j101-d_8_1220&category=D&year=2018&lang=J&abst= |
|||
| 2017 | Clean Reversible Simulation of Ranking Binary Trees | 共著 | |
| Reversibility and Universality ， Springer-Verlag ， Vol.30 ， pp. 243-267 ， 2018/03 | |||
|
概要（Abstract） We propose clean reversible simulations of ranking binary trees and unranking as reversible algorithms for reversible computing systems, which are useful for enumerating and randomly generating binary trees. Algorithms for ranking binary trees and their inverses have been studied since the 1970s. Each of these algorithms can be converted into a reversible simulation by saving all data and control information otherwise lost, and each pair of ranking and unranking reversible pro- grams can be combined to realize a clean reversible simulation by using the Bennett method. However, such a clean reversible simulation requires multiple traversal of the given data and/or intermediate data as well as additional storage proportional to the length of the computation. We show that for Knott's ranking and unranking algorithms, additional storage usage can be reduced by using the proper assertions of reversible loops in embedded reversible simulations. We also show a clean reversible simulation that involves only one traversal. The running time and memory usage of the proposed clean reversible simulations are asymptotically equivalent to those of the original programs by Knott with intermediate garbage of constant size. In general, the derivation strategy of efficient reversible programs from irreversible ones has not yet been established, and this study can be seen as one of the case studies. All the reversible programs presented in this paper can be run on an interpreter of the reversible programming language Janus. |
|||
|
備考（Remarks） https://doi.org/10.1007/978-3-319-73216-9_11 |
|||
| 2017 | 可逆ビンソート | 単著 | |
| 電子情報通信学会論文誌 D ， 電子情報通信学会 ， Vol.J101-D, No.5 ， pp. 791-793 ， 2018/01/19 | |||
|
概要（Abstract） 非比較ソートであるビンソートの可逆シミュレーションを示し，効率的な非可逆ビンソートに対して時間/空間計算量が共に線形で出力ゴミが入力データと漸近的に同じ大きさの置換を表す配列になることを示す． |
|||
|
備考（Remarks）
DOI: 10.14923/transinfj.2017JDL8021 |
|||
| 2017 | 可逆プログラムのための償却定数時間かつ定数ゴミ使用量のメモ化 | 単著 | |
| 電子情報通信学会和文論文誌D ， 電子情報通信学会 ， Vol.J100-D, No.10 ， pp. 895-896 ， 2017/10/01 | |||
|
概要（Abstract） メモ化アルゴリズムの可逆版を提案する．本手法により得られるクリーン可逆プログラムは，可逆二進計数器を抽象解釈とする．単射な隣接2項間漸化式で表される任意の数列に対して償却定数時間で定数ゴミ使用量の可逆プログラムを得る方法を示す． |
|||
|
備考（Remarks） https://search.ieice.org/bin/summary.php?id=j100-d_10_895 |
|||
| 2017 | ハミルトン曲面流に対応する語の列挙アルゴリズム | 共著 | |
| 電子情報通信学会和文論文誌D ， 電子情報通信学会 ， Vol.J100-D, No.10 ， pp. 892-894 ， 2017/10/01 | |||
|
概要（Abstract）
ハミルトン曲面流に関する極大語の自然な分類が有限個であることを示し，その各分類の下での全ての極大語の列挙アルゴリズムの構成法を明らかにした．また，各分類において極大語の総数を求める方法を形式言語理論を応用して示した． |
|||
|
備考（Remarks） http://search.ieice.org/bin/summary.php?id=j100-d_10_892&category=D&year=2017&lang=J&abst= |
|||
| 2017 | A Minimalist's Reversible While Language | 共著 | |
| IEICE on Information and Systems ， Institute of Electronics, Information and Communication Engineers ， Vol.E100-D/No.5 ， pp. 1026-1034 ， 2017/05/01 | |||
|
概要（Abstract） The paper presents a small reversible language R-CORE, a structured imperative programming language with symbolic tree-structured data (S-expressions). The language is reduced to the core of a reversible language, with a single command for reversibly updating the store, a single reversible control-flow operator, a limited number of variables, and data with a single atom and a single constructor. Despite its extreme simplicity, the language is reversibly universal, which means that it is as powerful as any reversible language can be, while it is linear-time self-interpretable, and it allows reversible programming with dynamic data structures. The four-line program inverter for R-CORE is among the shortest existing program inverters, which demonstrates the conciseness of the language. The translator to R-CORE, which is used to show the formal properties of the language, is clean and modular, and it may serve as a model for related reversible translation problems. The goal is to provide a language that is sufficiently concise for theoretical investigations. Owing to its simplicity, the language may also be used for educational purposes. |
|||
|
備考（Remarks） http://doi.org/10.1587/transinf.2016EDP7274 |
|||
| 2016 | A Linear-Time Self-Interpreter of a Reversible Imperative Language | 共著 | |
| Computer Software ， Japan Society for Software Science and Technology (JSSST) ， 3 ， pp. 108–128 ， 2016/08/10 | |||
|
概要（Abstract） A linear-time reversible self-interpreter in an r-Turing complete reversible imperative language is presented. The proposed imperative language has reversible structured control flow operators and symbolic tree-structured data (S-expressions). The latter data structures are dynamically allocated and enable reversible simulation of programs of arbitrary size and space consumption. As self-interpreters are used to show a number of fundamental properties in classic computability and complexity theory, the present study of an efficient reversible self-interpreter is intended as a basis for future work on reversible computability and complexity theory as well as programming language theory for reversible computing. Although the proposed reversible interpreter consumes superlinear space, the restriction of the number of variables in the source language leads to linear-time reversible simulation. |
|||
|
備考（Remarks）
http://doi.org/10.11309/jssst.33.3_108 |
|||
| 2015 | Fundamentals of reversible flowchart languages | 共著 | doi:10.1016/j.tcs.2015.07.046 |
| Theoretical Computer Science ， Elsevier ， 611 ， 87-115 ， 2016/01/18 | |||
|
概要（Abstract）
This paper presents the fundamentals of reversible flowcharts. Reversible flowcharts are intended to naturally represent the structure and control flow of reversible (imperative) programming languages in a simple computation model in the same way classical flowcharts do for conventional languages. Although reversible flowcharts are superficially similar to classical flowcharts, there are crucial differences: atomic steps are limited to locally invertible operations, and join points require an explicit orthogonalizing conditional expression. |
|||
|
備考（Remarks） http://dx.doi.org/10.1016/j.tcs.2015.07.046 |
|||
Copyright(C) 2010 Software Research Associates, Inc. All Rights Reserved.