研究者詳細

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

28 件中 1 - 10 件目

年度
Year
論文題目名
Title of the articles
共著区分
Collaboration
   Classification
NeoCILIUS
   請求番号/資料ID
Request No
掲載誌名 Journal name,出版機関名 Publishing organization,巻/号 Vol./no.,頁数 Page nos.,発行年月(日) Date
2018  可逆プログラミング言語R-WHILEの可逆チューリング完全性  共著   
電子情報通信学会和文論文誌D  , 電子情報通信学会  , J101-D, No.9  , 2018/09   

概要(Abstract) 任意の可逆プログラミング言語のプログラムで計算できるものが,可逆なR-WHILEプログラムによって計算できることを示す. 

備考(Remarks)  

2018  ハミルトン曲面流に対応する流れの向きを考慮した極大語の列挙アルゴリズム  共著   
電子情報通信学会論文誌 D  , 電子情報通信学会  , Vol.J101-D,No.8  , 2018/08   

概要(Abstract) ハミルトン曲面流を表す流れの向きを考慮した極大語の表現法,任意の長さの極大語をもれなく重複無く列挙するアルゴリズム,及びステートチャートによる極大語の生成方法の簡潔な表現を示した.本手法で向きを考慮した流れの総数を見積もれる.
 

備考(Remarks)  

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/06   

概要(Abstract) メモ化アルゴリズムの可逆版を提案する.本手法により得られるクリーン可逆プログラムは,可逆二進計数器を抽象解釈とする.単射な隣接2項間漸化式で表される任意の数列に対して償却定数時間で定数ゴミ使用量の可逆プログラムを得る方法を示す. 

備考(Remarks)  

2017  ハミルトン曲面流に対応する語の列挙アルゴリズム  共著   
電子情報通信学会和文論文誌D  , 電子情報通信学会  , Vol.J100-D, No.10  , pp. 892-894  , 2017/06   

概要(Abstract) ハミルトン曲面流に関する極大語の自然な分類が有限個であることを示し,その各分類の下での全ての極大語の列挙アルゴリズムの構成法を明らかにした.また,各分類において極大語の総数を求める方法を形式言語理論を応用して示した.
 

備考(Remarks)  

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

【reprint】Information and Media Technologies 11: 160-180 (2016) https://www.jstage.jst.go.jp/article/imt/11/0/11_160/_article 

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.

Despite these constraints, we show that reversible flowcharts are both expressive and robust: reversible flowcharts can simulate irreversible ones by adapting reversibilization techniques to the flowchart model. Thus, reversible flowcharts are r-Turing-complete, meaning that they can compute exactly all injective computable functions. Furthermore, structured reversible flowcharts are as expressive as unstructured ones, as shown by a reversible version of the classic Structured Program Theorem.

We illustrate how reversible flowcharts can be concretized with two example programming languages, complete with syntax and semantics: a low-level unstructured language and a high-level structured language. We introduce concrete tools such as program inverters and translators for both languages, which follow the structure suggested by the flowchart model. To further illustrate the different concepts and tools brought together in this paper, we present two major worked examples: a reversible permutation-to-code algorithm attributed to Dijkstra, and a simulation scheme for reversible Turing machines. By exhibiting a wide range of uses, we hope that the proposed reversible flowcharts can serve as a springboard for further theoretical research in reversible computing. 

備考(Remarks) http://dx.doi.org/10.1016/j.tcs.2015.07.046 

2015  Programming Techniques for Reversible Comparison Sorts  共著  10.1007/978-3-319-26529-2_22 
Lecture Notes in Computer Science  , Springer-Verlag  , 9458  , pp. 407-426  , 2015/12/09   

概要(Abstract) A common approach to reversible programming is to reversibly simulate an irreversible program with the desired functionality, which in general puts additional pressure on the computational resources (time, space.) If the same running time is required, ensuring a minimal space overhead is a significant programming challenge.

We introduce criteria for the optimality of reversible simulation: A reversible simulation is faithful if it incurs no asymptotic time overhead and bounds the space overhead (the garbage) by some function g(n), and hygienic if g is (asymptotically) optimal for faithful simulation.

We demonstrate the programming techniques used to develop faithful and hygienic reversible simulations of several well-known comparison sorts, e.g. insertion sort and quicksort, using representations of permutations in both the output and intermediate additional space required. 

備考(Remarks) https://doi.org/10.1007/978-3-319-26529-2_22 

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