| Presentation | 2019-01-16 Optimal Run Problem for Weighted Register Automata Reo Yoshimura, 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 define some decision problems for WRA and analyze their computational complexity. 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 the reduction, we abstract data values stored in registers by a register type, determined from binary relations (such as $=$, $<$, etc.) handled by WRA. 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 subclasssuch 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 automata / weight / data word / optimal run |
| Paper # | MSS2018-66,SS2018-37 |
| Date of Issue | 2019-01-08 (MSS, SS) |
| Conference Information | |
| Committee | MSS / SS |
|---|---|
| Conference Date | 2019/1/15(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Morikazu Nakamura(Univ. of Ryukyus) / Akio Nakata(Hiroshima City Univ.) |
| Vice Chair | Shigemasa Takai(Osaka Univ.) / Takashi Kobayashi(Tokyo Inst. of Tech.) |
| Secretary | Shigemasa Takai(Toshiba) / Takashi Kobayashi(Osaka Univ.) |
| Assistant | Hideki Kinjo(Okinawa Univ.) / Shinpei Hayashi(Tokyo Inst. of Tech.) |
| Paper Information | |
| Registration To | Technical Committee on Mathematical Systems Science and its applications / Technical Committee on Software Science |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Optimal Run Problem for Weighted Register Automata |
| Sub Title (in English) | |
| Keyword(1) | weighted register automata |
| Keyword(2) | weight |
| Keyword(3) | data word |
| Keyword(4) | optimal run |
| 1st Author's Name | Reo Yoshimura |
| 1st Author's Affiliation | Nagoya University(Nagoya Univ.) |
| 2nd Author's Name | Hiroyuki Seki |
| 2nd Author's Affiliation | Nagoya University(Nagoya Univ.) |
| Date | 2019-01-16 |
| Paper # | MSS2018-66,SS2018-37 |
| Volume (vol) | vol.118 |
| Number (no) | MSS-384,SS-385 |
| Page | pp.pp.61-66(MSS), pp.61-66(SS), |
| #Pages | 6 |
| Date of Issue | 2019-01-08 (MSS, SS) |