分割表示   全件表示 >>

37 件中 1 - 10 件目

Title of the articles
Request No
掲載誌名 Journal name,出版機関名 Publishing organization,巻/号 Vol./no.,頁数 Page nos.,発行年月(日) Date
2020  Complete Transition Diagrams of Generic Hamiltonian Flows with a Few Heteroclinic Orbits  共著   
Discrete Mathematics, Algorithms and Applications  , World Scientific  , 2020/09   

概要(Abstract) We study the transition graph of generic Hamiltonian surface flows, whose vertices are the topological equivalence classes of generic Hamiltonian surface flows and whose edges are the generic transitions. Using the transition graph, we can describe time evaluations of generic Hamiltonian surface flows (e.g. fluid phenomena) as walks on the graph. We propose a method for constructing the complete transition graph of all generic Hamiltonian flows. In fact, we construct two complete transition graphs of Hamiltonian surface flows having three and four genus elements. Moreover, we demonstrate that a lower bound on the transition distance between two Hamiltonian surface flows with any number of genus elements can be calculated by solving an integer programming problem using vector representations of Hamiltonian surface flows. 

備考(Remarks) https://doi.org/10.1142/S1793830921500233 

2020  Reversible Programs Have Reversible Semantics  共著   
In: Sekerinski E. et al. (eds) Formal Methods. FM 2019 International Workshops (FM 2019), Lecture Notes in Computer Science   , Springer-Verlag  , Vol.12233  , pp. 413–427  , 2020/08/10   

概要(Abstract) During the past decade, reversible programming languages have been formalized using various established semantic frameworks. However, these semantics fail to effectively specify the distinct properties of reversible languages at the metalevel, and even neglect the central question of whether the defined language is reversible. In this paper, we build on a metalanguage foundation for reversible languages based on the category of sets and partial injective functions. We exemplify our approach through step-by-step development of the full semantics of an r-Turing complete reversible while-language with recursive procedures. This yields a formalization of the semantics in which the reversibility of the language and its inverse semantics are immediate, as well as the inversion of programs written in the language. We further discuss applications and future research directions for reversible semantics. 

備考(Remarks) https://doi.org/10.1007/978-3-030-54997-8_26 

2019  Analyzing Trade-offs in Reversible Linear and Binary Search Algorithms  共著   
Proceedings of the Third Workshop on Software Foundations for Data Interoperability (SFDI2019+), October 28, 2019, Fukuoka, Japan  , pp.1-5  , 2019/10/23   

概要(Abstract) Reversible algorithms are algorithms in which each step represents a partial injective function; they are useful for performance optimization in reversible systems. In this study, using Janus, a reversible imperative high-level programming language, we have developed reversible linear and binary search algorithms. We have analyzed the non-trivial space-time trade-offs between them, focusing on the memory usage disregarding original inputs and outputs, the size of the output garbage disregarding the original inputs, and the maximum amount of traversal of the input. The programs in this study can easily be adapted to other reversible programming languages. Our analysis reveals that the change of the output data and/or the data structure affects the design of efficient reversible algorithms. For example, the number of input data traversals depends on whether the search has succeeded or failed, while it expectedly never changes in corresponding irreversible linear and binary searches. Our observations indicate the importance of the selection of data structures and what is regarded as the output with the aim of the reversible algorithm design. 

備考(Remarks) https://arxiv.org/abs/1911.05900

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://doi.org/10.14923/transinfj.2018JDL8021 

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


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