研究者詳細

学術論文
分割表示   全件表示 >>

32 件中 1 - 10 件目

年度
Year
論文題目名
Title of the articles
共著区分
Collaboration
   Classification
NeoCILIUS
   請求番号/資料ID
Request No
掲載誌名 Journal name,出版機関名 Publishing organization,巻/号 Vol./no.,頁数 Page nos.,発行年月(日) Date
2019  Reversible Programs Have Reversible Semantics  共著   
2019/10   

概要(Abstract)  

備考(Remarks)  

2019  Constructing a Binary Tree from its Traversals by Reversible Recursion and Iteration  共著   
Information Processing Letters  , Elsevier  , 147  , 32-37  , 2019/07   

概要(Abstract) We cast two algorithms generating the inorder and preorder traversals of a binary tree in the context of reversible computing nearly three decades after they were first examined in the light of program inversion. The reversible traversals directly define the inverse algorithms that reconstruct the tree. They have the same linear time and space requirements as the traversals. A while-language is extended with reversible recursion. 

備考(Remarks) https://doi.org/10.1016/j.ipl.2019.03.002 

2018  多重連結領域上の安定非圧縮流のプリミティブな局所構造変換  共著   
電子情報通信学会和文論文誌D  , 電子情報通信学会  , Vol.J102-D, No.3  , 235-238  , 2019/03/01   

概要(Abstract) 局所構造変換を繰り返し適用して,一般に観測される多重連結領域上の非圧縮流の全トポロジーを構成できることを示した.3種類の初期大域構造に対して,7種類の局所構造を置換するアプローチを取った. 

備考(Remarks) http://search.ieice.org/bin/summary.php?id=j102-d_3_235&category=-D&year=2019&lang=J&abst= 

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  , 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) doi: 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

2018/01/19に早期公開,2018/05に公開 

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= 

Page: [<<PREV] [1] [2] [3] [4] [NEXT>>]