2021-10-16T04:16:50Zhttps://nagoya.repo.nii.ac.jp/oaioai:nagoya.repo.nii.ac.jp:020014212021-09-10T02:31:22ZOptimal run problem for weighted register automataSeki, HiroyukiYoshimura, ReoTakata, Yoshiakiembargoed access© 2021. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/Weighted register automatonOptimal runRegister typeComplexityRegister automata (RA) are a computational model that can handle data values by adding registers to finite automata. Recently, weighted register automata (WRA) were proposed by extending RA so that weights can be specified for transitions. In this paper, we first investigate decidability and complexity of decision problems on the weights of runs in WRA. We then propose an algorithm for the optimal run problem related to the above decision problems. For this purpose, we use a register type as an abstraction of the contents of registers, which is determined by binary relations (such as =, <, etc.) handled by WRA. Also, we introduce a subclass where both the applicability of transition rules and the weights of transitions are determined only by a register type. We present a method of transforming a given WRA satisfying the assumption to a weighted directed graph such that the optimal run of WRA and the minimum weight path of the graph correspond to each other. Lastly, we discuss the optimal run problem for weighted timed automata as an example.Elsevier2023-01-042021-01-04engjournal articleAMhttp://hdl.handle.net/2237/0002001421https://nagoya.repo.nii.ac.jp/records/2001421https://doi.org/10.1016/j.tcs.2020.11.00303043975Theoretical Computer Science850185201https://nagoya.repo.nii.ac.jp/record/2001421/files/main-1101.pdfapplication/pdf468 KB2023-01-04