Weighted Register Automata and Weighted Logic on Data Words
Weighted Register Automata and Weighted Logic on Data Words
复制标题
加权寄存器自动机和数据字上的加权逻辑
DOI：
10.1007/978-3-319-46750-4_21
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
V. Perevoshchikov
中科院分区：
文献类型：
--
作者：
P. Babari;M. Droste;V. Perevoshchikov
数据字是成对的序列，其中第一个元素取自有限字母表，第二个元素取自无限数据域。寄存器自动机提供了一种广泛研究的数据字推理模型。在本文中，我们研究了具有无限数据域的系统定量方面的自动机模型，例如，在远程服务器上存储数据的成本或数据分析期间的资源消耗（例如内存、能源、时间）。我们在配备了二进制数据函数集合的可交换数据半环上引入了数据字的加权寄存器自动机，并研究了它们的闭包性质。与文献中考虑的其他模型不同，我们允许通过二进制数据关系的任意集合进行数据比较。这使我们能够将定时自动机和加权定时自动机合并到我们的框架中。在我们的主要结果中，我们通过加权存在单子二阶逻辑给出了加权寄存器自动机的逻辑表征；为了证明，我们采用了一类新的可确定的可见寄存器自动机。
Data words are sequences of pairs where the first element is taken from a finite alphabet and the second element is taken from an infinite data domain. Register automata provide a widely studied model for reasoning on data words. In this paper, we investigate automata models for quantitative aspects of systems with infinite data domains, e.g., the costs of storing data on a remote server or the consumption of resources (e.g., memory, energy, time) during a data analysis. We introduce weighted register automata on data words over commutative data semirings equipped with a collection of binary data functions, and we investigate their closure properties. Unlike the other models considered in the literature, we allow data comparison by means of an arbitrary collection of binary data relations. This enables us to incorporate timed automata and weighted timed automata into our framework. In our main result, we give a logical characterization of weighted register automata by means of weighted existential monadic second-order logic; for the proof we employ a new class of determinizable visibly register automata.
登录
查看更多内容
DOI：
10.1007/3-540-44685-0_17
发表时间：
2001
期刊：
2013 28th Annual ACM/IEEE Symposium on Logic in Computer Science
影响因子：
--
作者：
P. Bouyer;A. Petit;D. Thérien
通讯作者：
D. Thérien
捕获 EMSO 逻辑的数据字自动机
影响因子：
2.5
作者：
B. Bollig
通讯作者：
B. Bollig
在强大的可判定逻辑和定时自动机中指定定时状态序列
DOI：
--
发表时间：
1994
期刊：
Formal Techniques in Real-Time and Fault-Tolerant Systems
影响因子：
--
作者：
T. Wilke
通讯作者：
T. Wilke
用于加权时间自动机的 MSO 逻辑
影响因子：
0.8
作者：
Karin Quaas
通讯作者：
Karin Quaas