| 講演名 | 2019-10-24 Computing Optimal Weight in Weighted Register Automata and Related Decision Problems 吉村 玲勇(名大), 高田 喜朗(高知工科大), 関 浩之(名大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | |
| 抄録(英) | Register automaton (RA) is a computational model that can handle data values by adding registers to finite automaton. Recently, weighted register automaton (WRA) was proposed by extending RA so that weights can be specified for transitions. In this paper, we first show the undecidability of basic decision problems for WRA. We also define an optimal run problem for WRA and propose an algorithm for the problem by reducing it to the minimum weight path problem for directed graphs. For a subclass where the applicability of transition rules and weights are determined only by register type, we present a method of constructing a directed graph from a given WRA in the subclass such that the optimal run of WRA and the minimum weight path of the graph correspond to each other. |
| キーワード(和) | |
| キーワード(英) | weighted register automataweightdata wordoptimal runweighted timed automata |
| 資料番号 | SS2019-16,DC2019-44 |
| 発行日 | 2019-10-17 (SS, DC) |
| 研究会情報 | |
| 研究会 | DC / SS |
|---|---|
| 開催期間 | 2019/10/24(から2日開催) |
| 開催地（和） | 熊本大学 |
| 開催地（英） | Kumamoto Univ. |
| テーマ（和） | ソフトウェアシステムとディペンダブルコンピューティングおよび一般 |
| テーマ（英） | Software Systems, etc. |
| 委員長氏名（和） | 福本 聡(首都大東京) / 中田 明夫(広島市大) |
| 委員長氏名（英） | Satoshi Fukumoto(Tokyo Metropolitan Univ.) / Akio Nakata(Hiroshima City Univ.) |
| 副委員長氏名（和） | 高橋 寛(愛媛大) / 小林 隆志(東工大) |
| 副委員長氏名（英） | Hiroshi Takahashi(Ehime Univ.) / Takashi Kobayashi(Tokyo Inst. of Tech.) |
| 幹事氏名（和） | 新井 雅之(日大) / 難波 一輝(千葉大) / 肥後 芳樹(阪大) / 島 和之(広島市大) |
| 幹事氏名（英） | Masayuki Arai(Nihon Univ.) / Kazuteru Namba(Chiba Univ.) / Yoshiki Higo(Osaka Univ.) / Kazuyuki Shima(Hiroshima City Univ.) |
| 幹事補佐氏名（和） | / 林 晋平(東工大) |
| 幹事補佐氏名（英） | / Shinpei Hayashi(Tokyo Inst. of Tech.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Dependable Computing / Technical Committee on Software Science |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | |
| サブタイトル（和） | |
| タイトル（英） | Computing Optimal Weight in Weighted Register Automata and Related Decision Problems |
| サブタイトル（和） | |
| キーワード(1)（和/英） | / weighted register automataweightdata wordoptimal runweighted timed automata |
| 第 1 著者 氏名（和/英） | 吉村 玲勇 / Reo Yoshimura |
| 第 1 著者 所属（和/英） | 名古屋大学(略称：名大) Nagoya University(略称：Nagoya Univ.) |
| 第 2 著者 氏名（和/英） | 高田 喜朗 / Yoshiaki Takata |
| 第 2 著者 所属（和/英） | 高知工科大学(略称：高知工科大) Kochi University of Technology(略称：Kochi-tech.) |
| 第 3 著者 氏名（和/英） | 関 浩之 / Hiroyuki Seki |
| 第 3 著者 所属（和/英） | 名古屋大学(略称：名大) Nagoya University(略称：Nagoya Univ.) |
| 発表年月日 | 2019-10-24 |
| 資料番号 | SS2019-16,DC2019-44 |
| 巻番号（vol） | vol.119 |
| 号番号（no） | SS-246,DC-247 |
| ページ範囲 | pp.19-24(SS), pp.19-24(DC), |
| ページ数 | 6 |
| 発行日 | 2019-10-17 (SS, DC) |