Weighted Logics for Nested Words and Algebraic Formal Power Series
Weighted Logics for Nested Words and Algebraic Formal Power Series
复制标题
嵌套词和代数形式幂级数的加权逻辑
DOI：
10.2168/lmcs-6(1:5)2010
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Christian Mathissen
中科院分区：
文献类型：
--
作者：
Christian Mathissen
嵌套词是由Madhusudan和Alfred提出的一种递归程序模型，近年来引起了人们的广泛兴趣。本文引入了半环的数量扩张，研究了半环中的嵌套词元素的嵌套词列。我们证明了规则嵌套词序列与Droste和Gastin引入的加权逻辑中可定义的序列一致。为此，我们建立了一个嵌套的话和串-并行-biposets之间的连接。应用我们的结果，我们得到了代数形式幂级数的一个加权逻辑刻画。这推广了Lautemann，Schwentick和Therien关于上下文无关语言的结果。
Nested words, a model for recursive programs proposed by Alur and Madhusudan, have recently gained much interest. In this paper we introduce quantitative extensions and study nested word series which assign to nested words elements of a semiring. We show that regular nested word series coincide with series definable in weighted logics as introduced by Droste and Gastin. For this, we establish a connection between nested words and series-parallel-biposets. Applying our result, we obtain a characterization of algebraic formal power series in terms of weighted logics. This generalizes a result of Lautemann, Schwentick and Therien on context-free languages.
嵌套词的正则语言：不动点、自动机和同步
影响因子：
0.5
作者：
Arenas M
通讯作者：
Arenas M