42 件中 1 - 10 件目
| 年度 Year |
論文題目名 Title of the articles |
共著区分 Collaboration Classification |
NeoCILIUS 請求番号／資料ID Request No |
|---|---|---|---|
| 掲載誌名 Journal name，出版機関名 Publishing organization，巻／号 Vol./no.，頁数 Page nos.，発行年月（日） Date | |||
| 2023 | Reversible computing from a programming language perspective | 共著 | |
| Theoretical Computer Science ， Elsevier ， 953 ， 1-29 ， 2023/04/10 | |||
|
概要（Abstract）
Software plays a central role in all aspects of reversible computing systems, and a variety of reversible programming languages have been developed. This presentation highlights the principles and main ideas of reversible computing viewed from a programming language perspective with a focus on clean reversible languages. They are the building material for software that can reap the benefits of reversible hardware and interesting in their own right. |
|||
|
備考（Remarks） https://doi.org/10.1016/j.tcs.2022.06.010 |
|||
| 2022 | Reversible Programming: A Case Study of Two String-Matching Algorithms | 共著 | |
| Electronic Proceedings in Theoretical Computer Science ， Open Publishing Association ， 373 ， 1-13 ， 2022/11/22 | |||
|
概要（Abstract） String matching is a fundamental problem in algorithm. This study examines the development and construction of two reversible string-matching algorithms: a naive string-matching algorithm and the Rabin-Karp algorithm. The algorithms are used to introduce reversible computing concepts, beginning from basic reversible programming techniques to more advanced considerations about the injectivization of the polynomial hash-update function employed by the Rabin-Karp algorithm. The results are two clean input-preserving reversible algorithms that require no additional space and have the same asymptotic time complexity as their classic irreversible originals. This study aims to contribute to the body of reversible algorithms and to the discipline of reversible programming. |
|||
|
備考（Remarks） http://dx.doi.org/10.4204/EPTCS.373.1 |
|||
| 2022 | Making Programs Reversible with Minimal Extra Data | 共著 | |
| New Generation Computing ， Springer ， 40 ， 467–480 ， 2022/07/04 | |||
|
概要（Abstract） Reversible computing is an unconventional computing paradigm that comes with specific challenges. One of the important questions is the existence of reversible programs with minimal extra output (garbage data). To answer this question for programs that implement partial functions over countable domains, we introduce an order on infinite garbage sets and a notion of minimality. To this end, we present two methods for functions specified by decidable and semi-decidable predicates. Both methods are universal, which means they work for all programs specified by the predicates. They cover Bennett’s classic input-erasing reversible computation of injective functions. Hence, any program written in a Turing-complete programming language can be implemented with g-minimal garbage in an r-Turing-complete reversible programming language. This generality comes at the cost of a considerable runtime due to the generate-and-test approach. |
|||
|
備考（Remarks） https://link.springer.com/article/10.1007/s00354-022-00169-z |
|||
| 2022 | From Reversible Programming Languages to Reversible Metalanguages | 共著 | |
| Theoretical Computer Science ， Elsevier ， Vol.920 ， pp. 46-63 ， 2022/06/12 | |||
|
概要（Abstract） During the past decade reversible programming languages have been formalized using various established semantics frameworks. However, these semantics fail to effectively specify the distinct properties of reversible languages at the metalevel, even including the central question of whether the defined language is reversible. In this paper, we build a metalanguage foundation for reversible languages from categorical principles, based on the category of sets and partial injective functions. We exemplify our approach by a step-by-step development of the full semantics of an r-Turing complete reversible while-language with recursive procedures. The use of the metalanguage leads to a formalization of the reversible semantics. A language defined in the metalanguage is guaranteed to have reversibility and inverse semantics. Also, program inverters for this language are obtained for free. We further discuss applications and directions for reversible semantics. |
|||
|
備考（Remarks）
https://doi.org/10.1016/j.tcs.2022.02.024 |
|||
| 2021 | 素朴な方法とRabin-Karp法による可逆文字列照合アルゴリズム | 共著 | |
| 南山大学紀要アカデミア理工学編 ， 南山大学 ， 22 ， pp. 124-132 ， 2022/03 | |||
|
概要（Abstract） 可逆性を有効に活用した計算システムでは，アルゴリズムも可逆であることが望ましいことが少なくない．本稿では素朴な方法と Rabin と Karp による文字列照合アルゴリズムの可逆版をそれぞれ作成し，時間計算量，空間計算量，及びゴミの量の解析を行う．可逆アルゴリズムは全ステップが単射でなければならない．我々は Rabin–Karp アルゴリズムで用いられるハッシュ値を更新する写像が単射であることを示す．素朴な方法の可逆版は（非可逆である）素朴な方法と時間計算量が同じであるものを作成した．可逆なRabin–Karp アルゴリズムは，前処理と後処理を除いた計算の時間計算量が非可逆なものと同じものを作成した．両者とも，空間計算量は対応する非可逆アルゴリズムと同じであり，ゴミは入力のみである．提案した可逆アルゴリズムは可逆プログラミング言語 Janus を用いて実装して動作を確認した． |
|||
|
備考（Remarks） http://doi.org/10.15119/00003946 |
|||
| 2020 | Complete Transition Diagrams of Generic Hamiltonian Flows with a Few Heteroclinic Orbits | 共著 | |
| Discrete Mathematics, Algorithms and Applications ， World Scientific ， Vol. 13, No. 02 ， 2150023 ， 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 |
|||
Copyright(C) 2010 Software Research Associates, Inc. All Rights Reserved.