研究者詳細

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

24 件中 1 - 24 件目

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

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 

2014  Designing Garbage-Free Reversible Implementations of the Integer Cosine Transform  共著   
ACM Journal on Emerging Technologies in Computing Systems  , 11  , pp. 1-15  , 2014/11   

概要(Abstract) Discrete linear transformations are important tools in information processing. Many such transforms are injective and therefore prime candidates for a physically reversible implementation into hardware. We present here reversible integer cosine transformations on n input integers. The resulting reversible circuit is able to perform both the forward transform and the inverse transform. The detailed structure of such a reversible design strongly depends on the odd prime factors of the determinant of the transform: whether those are of the form 2k ± 1 or of the form 2k ± 2l ± 1 or neither of these forms. 

備考(Remarks)  

2014  可逆プログラミング言語の引数渡し機構の拡張  共著   
情報処理学会論文誌:プログラミング  , 情報処理学会  , 7  , 21-36  , 2014/08   

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

備考(Remarks)  

2012  Minimizing Garbage Size by Generating Reversible Simulations  共著   
Reversibility, cellular automata, and unconventional computation. Proceedings.  , IEEE Computer Society  , 379–387  , 2012/12/05   

概要(Abstract) Reversible simulations can realize any irreversible computation on any r-Turing complete reversible computation model at the expense of additional garbage output. The problem of minimizing the garbage size is an important issue in reversible simulations. We discuss the notion of the minimal garbage size of reversible simulations. Then, we propose a three-stage reversible simulation for minimizing garbage size, the first stage generates specialized irreversible programs, the second translates them into reversible simulations, and the third performs reversible simulation using the generated reversible programs. Two case studies on sorting algorithms suggest that the proposed method generates solutions with minimal garbage size. 

備考(Remarks) http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6424599&isnumber=6424528 

2011  Optimizing Input-Erasing Clean Reversible Simulation for Injective Functions  共著   
Multiple-Valued Logic and Soft Computing  , Old City Publishing  , Vol.18/no.1  , 5–24  , 2012/01   

概要(Abstract) Bennett showed that a clean reversible simulation of injective programs is possible without returning the input of a program as additional output. His method involves two computation and two uncomputation phases. This paper proposes an optimization of Bennett’s simulation that requires only half of the computation and uncomputation steps for a class of injective programs. A practical consequence is that the reversible simulation runs twice as fast as Bennett’s simulation. The proposed method is demonstrated by developing lossless encoders and decoders for run-length encoding and range coding. The range-coding program is further optimized by conserving the model over the text-generation phase. This paper may thus provide a new view on developing efficient reversible simulations for a certain class of injective functions. 

備考(Remarks) http://www.oldcitypublishing.com/journals/mvlsc-home/mvlsc-issue-contents/mvlsc-volume-18-number-1-2012/mvlsc-18-1-p-5-24/ 

2011  Towards a Reversible Functional Language  共著   
Lecture Notes in Computer Science  , Springer-Verlag  , Vol. 7165  , 14–29  , 2012   

概要(Abstract) We identify concepts of reversibility for a functional language
by means of a set of semantic rules with specific properties. These properties include injectivity along with local backward determinism, an important operational property for an efficient reversible language. We define a concise reversible first-order functional language in which access to the backward semantics is provided to the programmer by inverse function calls. Reversibility guarantees that in this language a backward run (inverse interpretation) is as fast as the corresponding forward run itself. By adopting a symmetric first-match policy for case expressions, we can write overlapping patterns in case branches, as is customary in ordinary functional languages, and also in leaf expressions, unlike existing inverse interpreter methods, which enables concise programs. In patterns, the use of a duplication/equality operator also simplifies inverse computation and program inversion. We discuss the advantages of a reversible functional language using example programs, including run-length encoding. Program inversion is seen to be as lightweight as for imperative
reversible languages and realized by recursive descent. Finally, we show
that the proposed language is r-Turing complete. 

備考(Remarks)  

2011  Static Task Scheduling Algorithms Based on Greedy Heuristics for Battery-Powered DVS Systems  共著   
IEICE Trans. on Information and Systems  , The Institute of Electronics, Information and Communication Engineers  , E93-D  , 2737-2746  , 2010/10   

概要(Abstract) We identify concepts of reversibility for a functional language by means of a set of semantic rules with specific properties. These properties include injectivity along with local backward determinism, an important operational property for an efficient reversible language. We define a concise reversible first-order functional language in which access to the backward semantics is provided to the programmer by inverse function calls. Reversibility guarantees that in this language a backward run (inverse interpretation) is as fast as the corresponding forward run itself. By adopting a symmetric first-match policy for case expressions, we can write overlapping patterns in case branches, as is customary in ordinary functional languages, and also in leaf expressions, unlike existing inverse interpreter methods, which enables concise programs. In patterns, the use of a duplication/equality operator also simplifies inverse computation and program inversion. We discuss the advantages of a reversible functional language using example programs, including run-length encoding. Program inversion is seen to be as lightweight as for imperative reversible languages and realized by recursive descent. Finally, we show that the proposed language is r-Turing complete. 

備考(Remarks)  

2009  Reversible Computation and Reversible Programming Languages  単著   
Electronic Notes in Theoretical Computer Science  , Elsevier  , 253(6)  , 71-81  , 2010/03   

概要(Abstract)  

備考(Remarks) 以下における招待講演を改訂したもの.
Reversible Computation 2009. 

2009  Heuristics for Static Voltage Scheduling Algorithms on Battery-Powered DVS Systems  未設定   
2009 International Conference on Embedded Software and Systems  , IEEE Computer Society  , 265-272  , 2009/05   

概要(Abstract) The principles for good design of battery-aware voltage scheduling algorithms for both aperiodic and periodic task sets on dynamic voltage scaling (DVS) systems are presented. The proposed algorithms are based on greedy heuristics suggested by several battery characteristics and Lagrange multipliers. To construct the proposed algorithms, we use the battery characteristics in the early stage of scheduling more properly. As a consequence, the proposed algorithms show superior results on synthetic examples of periodic and aperiodic tasks from the task sets which are excerpted from the comparative work, on uniprocessor platforms. Especially, for some large task sets, the proposed algorithms enable previously unschedulable task sets due to battery exhaustion to be schedulable. 

備考(Remarks)  

2008  動的電圧制御システムにおける評価戦略選択に基づく高効率消費エネルギー関数型プログラミング  共著  http://ci.nii.ac.jp/naid/110007970891 
情報処理学会論文誌:トランザクション「プログラミング」  , 情報処理学会  , Vol.2, No.2(PRO41)  , 54-69  , 2009/03   

概要(Abstract) 動的電圧制御 (DVS: dynamic voltage scaling) は,プロセッサへの供給電圧とその動作周波数をプログラム実行時に変化させる技術であり,現在,多くの商用プロセッサに実装されている.本稿では,デッドラインなどの制約のあるリアルタイムシステムを対象に,DVS システムにおいて動的エネルギー消費のより少ないプログラムを開発する方法論の 1 つを提示する.DVS システムで実行されるプログラムに動的エネルギー消費の最適化が有効であるためには,残り予測実行時間の実行早期の正確な見積りを容易にすることが重要である.そのため,プログラムは何を計算するかに加えどう計算するかをうまく指定する必要がある.しかし,プログラム改変によるエネルギー消費の最適化はプログラムのモジュール性を著しく損なう.本稿では,プログラムから独立し,エネルギー消費の最適化戦略を開発する手法を提案する.提案手法により,エネルギー消費の最適化を行うときに元のプログラムの部分正当性が容易に保存され,元のプログラムおよびエネルギー消費の最適化を行うための評価戦略が独立してそれぞれモジュール性を有するようになった.遅延評価などのプログラミング言語の特徴や構成的アルゴリズム論における組化などを活用することにより半自動化が実現できたことが,本開発法の特徴の 1 つである.本稿では,整列,選択,文字列検索などの基本的なアルゴリズムに提案手法を適用する.また,電力モデルを備えた命令セットシミュレータ(ISS: instruction set simulator)において実験を行い,エネルギー消費がどれだけ最適化されたかを評価する.基本的なアルゴリズムにおいて,本稿のアプローチが有効であることから,複雑なアルゴリズムに対しても本手法が効果的であることが期待される. 

備考(Remarks) 以下で発表したものを改訂したもの.
動的電圧制御システムにおけるエネルギー効率的な関数プログラム, 第71回情報処理学会プログラミング研究発表会. 

2008  A Generalized Framework for Energy Savings in Real-Time Multiprocessor Systems  共著   
Proceedings of 2008 International SoC Design Conference  , IEEE  , 727-732  , 2009/01   

概要(Abstract) A generalized dynamic energy performance scaling (DEPS) framework is proposed for exploring application-specific energy-saving potential in multiprocessor systems. This software-centric framework takes advantage of possible power control mechanisms to trade off performance for energy savings. Three existing technologies, i.e., dynamic hardware resource configuration (DHRC), dynamic voltage frequency scaling (DVFS), and dynamic power management (DPM), have been employed in this framework to achieve the maximal energy savings. The problem of determining the optimal task allocation and DEPS configurations is formulated as an integer linear programming (ILP) problem. Several practical issues such as how to reduce measurement and computation time and how to reduce the configuration overhead are also addressed. The effectiveness of DEPS is validated through a case study. 

備考(Remarks)  

2008  Reversible Flowchart Languages and the Structured Reversible Program Theorem  共著   
Automata, Languages and Programming  , Springer  , LNCS 5126  , 258-270  , 2008/08   

概要(Abstract) Many irreversible computation models have reversible counterparts, but these are poorly understood at present. We introduce reversible flowcharts with an assertion operator and show that any reversible flowchart can be simulated by a structured reversible flowchart using only three control flow operators. Reversible flowcharts are r-Turing-complete, meaning that they can simulate reversible Turing machines without garbage data. We also demonstrate the injectivization of classical flowcharts into reversible flowcharts. The reversible flowchart computation model provides a theoretical justification for low-level machine code for reversible microprocessors as well as high-level block structured reversible languages. We give examples for both such languages and illustrate them with a lossless encoder for permutations given by Dijkstra. 

備考(Remarks)  

2007  Reversible Machine Code and Its Abstract Processor Architecture  共著   
Computer Science -- Theory and Applications  , Springer  , LNCS 4649  , 56-69  , 2007/09   

概要(Abstract)  

備考(Remarks) 以下で発表したものを改訂したもの.
Second International Symposium on Computer Science in Russia, CSR 2007, 

2006  Program Optimizations and Transformations in Calculation Form  共著   
Generative and Transformational Techniques in Software Engineering  , Springer  , LNCS 4143  , 144-168  , 2006/11   

概要(Abstract) The world of program optimization and transformation takes on a new fascination when viewed through the lens of program calculation. Unlike the traditional fold/unfold approach to program transformation on arbitrary programs, the calculational approach imposes restrictions on program structures, resulting in some suitable calculational forms such as homomorphisms and mutumorphisms that enjoy a collection of generic algebraic laws for program manipulation. In this tutorial, we will explain the basic idea of program calculation, demonstrate that many program optimizations and transformations, such as the optimization technique known as loop fusion and the parallelization transformation, can be concisely reformalized in calculational form, and show that program transformation in calculational forms is of higher modularity and more suitable for efficient implementation. 

備考(Remarks) 以下を改訂したもの.
Program Optimizations and Transformations in Calculation Form, Ralf Lämmel, João Saraiva and Joost Visser (Eds.) Summer School on Generative and Transformational Techniques in Software Engineering,
Technical Report TR-CCTC/DI-35, Centro de Ciências e Tecnologias de Computaçã, Departamento Informática, Universidade do Minho, Braga, Portugal, pp. 41-66, July 4-8, 2005. 

2004  決定論的2階パターンとプログラム変換への応用  共著   
コンピュータソフトウェア  , 日本ソフトウェア科学会  , Vol. 21、No. 5  , 71-76  , 2004/09   

概要(Abstract)  

備考(Remarks)  

2004  Deterministic Second-Order Patterns  共著   
Information Processing Letters  , Elsevier  , 89(6)  , 309-314  , 2004/03   

概要(Abstract)  

備考(Remarks)  

2003  Deterministic Higher-Order Patterns for Program Transformation  共著   
Logic Based Program Synthesis and Transformation  , Springer  , LNCS 3018  , 128-142  , 2004/08   

概要(Abstract)  

備考(Remarks) 以下を改訂したもの.
Deterministic Second-order Patterns in Program Transformation. Maurice Bruynooghe (Ed.), In Preproceedings of the International Symposium on Logic Based Program Synthesis and Transformation (LOPSTR), pp. 165-178, Uppsala, Sweden, August 2003. Technical Report CW 365 at Dept. of Computer Science, K.U.Leuven, Leuven, Belgium. August 25-27, 2003, Uppsala, Sweden. 

2002  Yicho - A System for Programming Program Calculations  共著   
Mathematical Engineering Technical Reports  , the University of Tokyo  , 7  , 1-17  , 2002/06   

概要(Abstract)  

備考(Remarks)  

2002  変換戦略の記述に基づくプログラムの自動生成システムの実装  共著   
情報処理学会論文誌:トランザクション「プログラミング」  , 情報処理学会  , Vol. 43 No. SIG3  , 62-77  , 2002/03   

概要(Abstract)  

備考(Remarks) 最大マーク付け問題の効率的プログラムの自動生成(情報処理学会第36回プログラミング研究会)を改訂したもの 

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