Definability and Transformations for Cost Logics and Automatic Structures
Definability and Transformations for Cost Logics and Automatic Structures
复制标题
成本逻辑和自动结构的可定义性和转换
DOI：
10.1007/978-3-662-44522-8_33
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Amaldev Manuel
中科院分区：
文献类型：
--
作者：
Martin Lang;Christof Löding;Amaldev Manuel
我们根据一阶逻辑提供了一类正则代价函数的新特征（Colcombet 2009）。这扩展了一个经典结果，即每种规则语言都可以通过有限词的无限树上的一阶公式来定义，该树具有相等长度的谓词测试词。此外，我们研究了成本逻辑的解释，并利用它们提供了资源自动结构类的不同特征，这是自动结构的定量版本。特别是，我们为一阶解释确定了一个完整的资源自动结构。
We provide new characterizations of the class of regular cost functions (Colcombet 2009) in terms of first-order logic. This extends a classical result stating that each regular language can be defined by a first-order formula over the infinite tree of finite words with a predicate testing words for equal length. Furthermore, we study interpretations for cost logics and use them to provide different characterizations of the class of resource automatic structures, a quantitative version of automatic structures. In particular, we identify a complete resource automatic structure for first-order interpretations.
登录
查看更多内容
n-tape 自动机识别的集合
影响因子：
0.9
作者：
S. Eilenberg;C. C. Elgot;J.C Shepherdson
通讯作者：
J.C Shepherdson
有限树上的正则成本函数
DOI：
--
发表时间：
2010
期刊：
2010 25th Annual IEEE Symposium on Logic in Computer Science
影响因子：
--
作者：
Thomas Colcombet;Christof Löding
通讯作者：
Christof Löding
具有资源的无限系统的建模和验证
DOI：
--
发表时间：
2013
期刊：
Log. Methods Comput. Sci.
影响因子：
--
作者：
Martin Lang;Christof Löding
通讯作者：
Christof Löding
DOI：
10.1016/0735-1097(96)00234-3
发表时间：
1996-09-01
影响因子：
24
作者：
Canobbio, MM;Mair, DD;Koos, BJ
通讯作者：
Koos, BJ
（广义）后继二（一）阶理论扩展的可判定性和不可判定性
影响因子：
0.6
作者：
C. C. Elgot;M. Rabin
通讯作者：
M. Rabin