Weighted automata and logics for infinite nested words
Weighted automata and logics for infinite nested words
复制标题
无限嵌套词的加权自动机和逻辑
DOI：
--
复制
发表时间：
2014
影响因子：
1
通讯作者：
Stefan Dück
中科院分区：
文献类型：
--
作者：
M. Droste;Stefan Dück
Alur和Madhusudan引入的嵌套词用于捕获具有线性和层次顺序的结构，例如XML文档，而不会丢失有价值的闭包属性。此外，Alur和Madhusudan引入了有限和无限嵌套词的自动机和等价逻辑，从而将Buchi定理推广到嵌套词。近年来，定量系统中权重的平均和折现计算引起了人们的极大兴趣。在这里，我们将介绍和研究无限嵌套词的加权自动机模型和加权MSO逻辑。作为权重结构，我们考虑包含权重的平均和折扣计算以及经典半环的估值单群。我们证明，在适当的假设下，两个变量。我们的加权逻辑的三个片段可以相互转换。此外，我们还证明了逻辑片段具有与加权嵌套词自动机相同的表达能力。
Nested words introduced by Alur and Madhusudan are used to capture structures with both linear and hierarchical order, e.g. XML documents, without losing valuable closure properties. Furthermore, Alur and Madhusudan introduced automata and equivalent logics for both finite and infinite nested words, thus extending Buchi's theorem to nested words. Recently, average and discounted computations of weights in quantitative systems found much interest. Here, we will introduce and investigate weighted automata models and weighted MSO logics for infinite nested words. As weight structures we consider valuation monoids which incorporate average and discounted computations of weights as well as the classical semirings. We show that under suitable assumptions, two resp. three fragments of our weighted logics can be transformed into each other. Moreover, we show that the logic fragments have the same expressive power as weighted nested word automata.
影响因子：
1
作者：
Droste, Manfred;Meinecke, Ingmar
通讯作者：
Meinecke, Ingmar