| Presentation | 2019-10-24 Computing Optimal Weight in Weighted Register Automata and Related Decision Problems Reo Yoshimura, Yoshiaki Takata, Hiroyuki Seki, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | weighted register automataweightdata wordoptimal runweighted timed automata |
| Paper # | SS2019-16,DC2019-44 |
| Date of Issue | 2019-10-17 (SS, DC) |
| Conference Information | |
| Committee | DC / SS |
|---|---|
| Conference Date | 2019/10/24(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Kumamoto Univ. |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | Software Systems, etc. |
| Chair | Satoshi Fukumoto(Tokyo Metropolitan Univ.) / Akio Nakata(Hiroshima City Univ.) |
| Vice Chair | Hiroshi Takahashi(Ehime Univ.) / Takashi Kobayashi(Tokyo Inst. of Tech.) |
| Secretary | Hiroshi Takahashi(Nihon Univ.) / Takashi Kobayashi(Chiba Univ.) |
| Assistant | / Shinpei Hayashi(Tokyo Inst. of Tech.) |
| Paper Information | |
| Registration To | Technical Committee on Dependable Computing / Technical Committee on Software Science |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Computing Optimal Weight in Weighted Register Automata and Related Decision Problems |
| Sub Title (in English) | |
| Keyword(1) | weighted register automataweightdata wordoptimal runweighted timed automata |
| 1st Author's Name | Reo Yoshimura |
| 1st Author's Affiliation | Nagoya University(Nagoya Univ.) |
| 2nd Author's Name | Yoshiaki Takata |
| 2nd Author's Affiliation | Kochi University of Technology(Kochi-tech.) |
| 3rd Author's Name | Hiroyuki Seki |
| 3rd Author's Affiliation | Nagoya University(Nagoya Univ.) |
| Date | 2019-10-24 |
| Paper # | SS2019-16,DC2019-44 |
| Volume (vol) | vol.119 |
| Number (no) | SS-246,DC-247 |
| Page | pp.pp.19-24(SS), pp.19-24(DC), |
| #Pages | 6 |
| Date of Issue | 2019-10-17 (SS, DC) |