Optimal run problem for weighted register automata
Optimal run problem for weighted register automata
复制标题
加权寄存器自动机的最优运行问题
DOI：
10.1016/j.tcs.2020.11.003
复制
发表时间：
2021
影响因子：
1.1
通讯作者：
Reo Yoshimura and Yoshiaki Takata
中科院分区：
文献类型：
--
作者：
Hiroyuki Seki;Reo Yoshimura and Yoshiaki Takata
寄存器自动机 (RA) 是一种计算模型，可以通过向有限自动机添加寄存器来处理数据值。最近，通过扩展 RA 提出了加权寄存器自动机（WRA），以便可以为转换指定权重。在本文中，我们首先研究 WRA 中运行权重决策问题的可判定性和复杂性。然后，我们提出了一种与上述决策问题相关的最优运行问题的算法。为此，我们使用寄存器类型作为寄存器内容的抽象，它由WRA处理的二进制关系（例如=、<等）确定。此外，我们引入了一个子类，其中转换规则的适用性和转换的权重仅由寄存器类型决定。我们提出了一种将满足假设的给定 WRA 转换为加权有向图的方法，使得 WRA 的最优运行和图的最小权重路径彼此对应。最后，我们以加权时间自动机的最优运行问题为例进行讨论。
Register 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.