Kleene and Buchi Theorems for Weighted Automata and Multi-valued Logics over Arbitrary Bounded Lattices

被引：0
作者：
Droste, Manfred [1 ]
Vogler, Heiko [2 ]
机构：
[1] Univ Leipzig, Inst Comp Sci, D-04109 Leipzig, Germany
[2] Tech Univ Dresden, Dept Comp Sci, D-01062 Dresden, Germany
来源：
DEVELOPMENTS IN LANGUAGE THEORY | 2010年 / 6224卷
关键词：
QUANTUM LOGIC; MODEL CHECKING; QUANTITATIVE LANGUAGES; MSO LOGICS; WORDS;
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We show that L-weighted automata, L-rational series, and L-valued monadic second-order logic have the same expressive power, for any bounded lattice L and for finite and infinite words. This extends classical results of Kleene and Buchi to arbitrary bounded lattices, without any distributivity assumption that is fundamental in the theory of weighted automata over semirings. In fact, we obtain these results for large classes of strong bimonoids which properly contain all bounded lattices.
引用
收藏
页码：160 / +
页数：5
相关论文
共 51 条
[1]  
[Anonymous], 2001, STUDIES LOGIC COMPUT
[2]  
[Anonymous], LNCS
[3]  
[Anonymous], 1960, Z. Math. Logik Grundlagen Math.
[4]  
[Anonymous], 1990, HDB THEORETICAL COMP
[5]  
[Anonymous], 1974, PURE APPL MATH
[6]  
[Anonymous], 1960, P INT C LOGIC METHOD
[7]  
[Anonymous], 2004, Infinite Words
[8]   The logic of quantum mechanics [J].
Birkhoff, G ;
von Neumann, J .
ANNALS OF MATHEMATICS, 1936, 37 :823-843
[9]  
Birkhoff G., 1961, AM MATH SOC C PUBL, V25
[10]   Weighted distributed systems and their logics [J].
Bollig, Benedikt ;
Meinecke, Ingmar .
LOGICAL FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2007, 4514 :54-+
123456