研究者詳細

研究発表
分割表示   全件表示 >>

9 件中 1 - 9 件目

年度
Year
題目又はセッション名
Title or Name of Session
細目
Authorship
発表年月(日)
Date
発表学会等名称 Name, etc. of the conference at which the presentation is to be given, 主催者名称 Organizer, 掲載雑誌名等 Publishing Magazine,発行所 Publisher,巻/号 Vol./no.,頁数 Page nos.
2016  可逆プログラミング言語R-WHILEによる万能可逆チューリング機械の構成  共同  2017/03/16 
情報処理学会第79回全国大会  , 情報処理学会  , 1J-04  , 2   

概要(Abstract) 可逆プログラミング言語R-WHILEの計算モデルは,万能可逆チューリング機械と同じ計算能力があるとされている.しかし,筆者の知る限りにおいて,その具体的な証明についてはこれまで報告が無かった.本稿では任意の可逆チューリング機械を,意味が同じR-WHILEプログラムに変換できることを示す.このことにより,可逆万能チューリング機械のR-WHILEプログラムが構成できることを示す. 

備考(Remarks) https://www.gakkai-web.net/gakkai/ipsj/79/program79.html 

2016  Clean Reversible Simulation of Ranking Binary Trees  共同  2017/03/10 
The 19th JSSST Workshop on Programming and Programming Languages  , JSSST   

概要(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 them can be made to be a reversible simulation by saving all the data and control information otherwise lost, and each pair of ranking and unranking reversible programs can be combined to realize a clean reversible simulation. 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 the 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. All the reversible programs presented in this paper can be run on an interpreter of the reversible programming language Janus. 

備考(Remarks)  

2016  二分木のランク計算のクリーン可逆シミュレーション  共同  2016/09/07 
日本ソフトウェア科学会第33回大会  , 日本ソフトウェア科学会   

概要(Abstract) 可逆計算システムで用いる可逆アルゴリズムのひとつとして,二分木の列挙やランダム生成に有用な二分木のランク・アンランク計算のクリーン可逆シミュレーションを提案する.二分木のランク計算やその逆計算を行う非可逆アルゴリズムは1970年代から研究が行われてきており,これらの成果を用いてランク計算の関数とその逆関数のそれぞれの可逆シミュレーションを組み合わせてクリーン可逆シミュレーションを行うことはできる.しかし,こうした可逆シミュレーションでは,複数回のパスおよびに実行時間に比例した大きさのメモリが必要である.これに対してわれわれの可逆シミュレーションは,1パスで,漸近的な実行時間とメモリ使用量が元のアルゴリズムと同じである.本稿中の可逆プログラムは,可逆言語Janusの処理系で動作を確認できる. 

備考(Remarks)  

2015  On the Theory of Reversible Flowchart Languages  単独  2015/06/10 
Quantum Programming and Circuits Workshop  , University of Waterloo   

概要(Abstract) Flowcharts are a fundamental tool used pervasively in computer science. In this talk, we survey the fundamental properties of reversible flowcharts, which are classical flowcharts with restrictions on join points and atomic step operators. Reversible flowcharts are as expressive as any reversible computation models such as reversible Turing machines and are able to simulate any irreversible computation. The theoretical basis of structured programming in high-level reversible languages is provided by a reversible version of the Structured Program Theorem. We illustrate the design of high-level and low-level reversible programming languages and their translators, based on the reversible flowchart model. We highlight their features by demonstrating a reversible version of Dijkstra's permutation-to-code algorithm. 

備考(Remarks) https://uwaterloo.ca/institute-for-quantum-computing/conferences/quantum-programming-and-circuits-workshop 

2014  A Linear-Time Reversible Self-Interpreter  共同  2015/3/06 
第17回プログラミングおよびプログラミング言語ワークショップ  , 日本ソフトウェア科学会  , pp. 1-18   

概要(Abstract) This paper explores a novel combination of language features in re- versible programming languages. The two imperative languages that we introduce have reversible structured control flow operators and symbolic tree-structured data (S-expressions). The latter allows to model many familiar data structures in an easy way, which is more difficult in existing reversible imperative languages, which so far only provide integers, stacks and arrays as data types. Most importantly, it is shown for the first time in a most expressive reversible imperative language that tree-structured data enable efficient self-interpretation in the sense of Jones. We prove that the languages are r-Turing complete (most expressive), i.e. they are computationally as powerful as any reversible language can get, and cleanly reversible, i.e. programs can run backward without first tracing a forward computation. The languages presented here are two new versatile instances of our structured reversible flowchart paradigm, and intended to serve as a basis for future studies of reversible programming languages, transformation and algorithms. 

備考(Remarks) http://www-kb.is.s.u-tokyo.ac.jp/ppl2015/ 

2013  可逆プログラミング言語の引数渡し機構の拡張  共同  2014/03/18 
第98回プログラミング研究会  , 情報処理学会  , 2013-5-(6)   

概要(Abstract) 本稿では,可逆プログラミング言語Janus の引数渡し機構を拡張して,その拡張言語が可逆であることを示す.参照渡しのモデル化には,同一の参照をもつかもしれない複数の変数名が同じ記憶場所を指せるメモリモデルが必要である.これは既存のJanus で用いられていた状態モデルでは直接には扱うことができない.この問題を解決するために,われわれは,環境・記憶域モデルを導入して意味論を改良した.この結果,プロシージャの実引数には,局所変数や局所配列変数だけでなく大域変数や添字付き配列変数の参照,および同一の参照をもつ複数の構文対象も渡せるようになった.拡張言語が可逆であることの保証には,環境と記憶域の更新が可逆であることの保証が必要がある.これらの更新は,制限された可逆操作のみ用いて実現することで,可逆であることを保証する.われわれは,拡張言語が他にも既存のJanusの良い性質を保っていることを示す.すなわち,任意の文やプロシージャ呼び出しの逆実行ができること,および任意の文に対して逆文が存在してそれを求めるプログラム逆変換器が構成できることを示す.さらに,われわれは,プログラミング言語を可逆にするために課されていた代入の構文上の制限を緩和する.このことが原因で起こる記憶域の不正な更新は,大域のプログラム解析をせずとも,効率的に検知することができる.われわれが新たに定義した意味論は,既存の構文では同一の意味が与えられるという点で,既存言語からの単純な拡張となっている. 

備考(Remarks)  

2013  リストの可逆分割アルゴリズムを利用したゴミ情報が最適な可逆クイック整列法の生成  共同  2014/03/13 
第76回全国大会  , 情報処理学会   

概要(Abstract) 本論文では文献[1] におけるゴミ情報の生成・マージの手法を応用し,より一般性の高い手法を提案する.文献[1] では,ゴミ情報量が最適なリストの可逆分割アルゴリズムを提案している.ここではさらに提案したアルゴリズムを利用してクイックソートを生成し,分割の際のゴミ情報量が最適であること,再帰呼び出しの際にゴミ情報の最適な伝播が実現できていることの2 点を示している.しかし,この手法はクイックソートに特有のサブプロシージャに対して最適なゴミ情報の生成を保証することにより実現されており,この手法をそのまま他のアルゴリズムに応用することが難しい.そこで,本研究ではアルゴリズムのより小さな構成要素に最適なゴミ情報を生成させ,それらの最適性を保ったままより大きな構成要素へとマージを行う手法を提案し,既存の手法の応用性を高める.なお,ここではゴミ情報とは非可逆アルゴリズムを可逆化する際に記録する必要があり,可逆化する前の非可逆アルゴリズムにおいては記録する必要のない情報を表す. 

備考(Remarks)  

2013  引数渡し機構をもつ可逆プログラミング言語の可逆性  共同  2014/03/11 
第76回全国大会  , 情報処理学会   

概要(Abstract) 計算過程が可逆とは,任意の状態でその直前と直後の状態が存在すればそれぞれ必ず一意に定まることをいう.可逆プログラミング言語とは,そのプログラムの実行過程が必ず可逆になるような言語設計がなされているプログラミング言語であり,可逆論理回路の設計[1] やプログラミング言語理論の研究対象[2] として使われている.そうした言語のひとつであるJanusでは,構文規則や意味規則における制限によって可逆性を実現しており,その結果,可逆プログラムでのみ可能な逆実行をするための機構を備えている.現在のJanus[3] は,引数機構が未整備のために可読性や簡潔性が欠如していると考えられる点がある.原因のひとつとして,状態モデルによって識別子のみを渡すことのできる引数渡し機構が用いられていることが挙げられる.このため,識別子以外の式の評価値や参照を渡すことが困難であった.そこで,我々は左辺値を意味領域に含むことのできる環境・記憶域モデルを採用し,可逆性をもつ値渡しと参照渡しの機構を実現する.Janus では,複合代入演算の左辺に出現した識別子が右辺に出現してはならないという制約があるが,この拡張により,プログラム全域のプログラム解析をしなくてもその複合代入演算文の実行時にその文の情報だけからこの制約の確認ができるようになる.また,引数を伴うプロシージャ呼出しが,より読みやすく簡潔に記述できるようになる.本稿では,引数渡し機構を拡張して表現力の増したJanus が可逆性をもつことの説明の概略を示す. 

備考(Remarks)  

2011  A High-Level Reversible Programming Language  単独  2011/12/12 
Dagstuhl Seminar on Design of Reversible and Quantum Circuits   

概要(Abstract)  

備考(Remarks)  

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