The Power of the Weak
The Power of the Weak
复制标题
弱者的力量
DOI：
10.1145/3372392
复制
发表时间：
2020
影响因子：
0.5
通讯作者：
Carreiro F
中科院分区：
文献类型：
--
作者：
Carreiro F
形式验证逻辑研究中的一个里程碑式的结果是雅宁和Walukiewicz定理，指出模态μ-演算（μML）在标记转移系统（LTS）上等价于标准一元二阶逻辑（SMSO）。我们的工作证明了两个同类结果，一个是关于μML的无交替或无以太片段μNML的模态侧结果，另一个是关于弱一元二阶逻辑WMSO的二阶侧结果。在二叉树的设置中，通过显式函数访问节点的左和右后继，已知WMSO等价于无交替μ演算的适当版本。我们的分析表明，一旦我们考虑，如雅宁和Walukiewicz所做的，标准的模态μ演算，解释任意LTSs. First定理，我们证明的是，在LTSs，μNML是等价模双相似性oetherianMSO（NMSO），SMSO的一个新引入的变种，其中二阶量化的范围仅在“反向良基”子集。我们的第二个定理从WMSO出发，证明了它等价于由连续性概念定义的μNML片段的模双相似性。类似于雅宁和Walukiewicz的结果，我们的证明是自动机理论的性质：作为另一个贡献，我们引入了奇偶自动机类的特点表现力的WMSO和NMSO（树模型）和μCML和μNML（所有的过渡系统）。
A landmark result in the study of logics for formal verification is Janin and Walukiewicz’s theorem, stating that the modal μ-calculus (μML) is equivalent modulo bisimilarity to standard monadic second-order logic (here abbreviated as SMSO) over the class of labelled transition systems (LTSs for short). Our work proves two results of the same kind, one for the alternation-free ornoetherianfragment μNML of μML on the modal side and one for WMSO, weak monadic second-order logic, on the second-order side. In the setting of binary trees, with explicit functions accessing the left and right successor of a node, it was known that WMSO is equivalent to the appropriate version of alternation-free μ-calculus. Our analysis shows that the picture changes radically once we consider, as Janin and Walukiewicz did, the standard modal μ-calculus, interpreted over arbitrary LTSs.The first theorem that we prove is that, over LTSs, μNML is equivalent modulo bisimilarity tonoetherianMSO (NMSO), a newly introduced variant of SMSO where second-order quantification ranges over “conversely well-founded” subsets only. Our second theorem starts from WMSO and proves it equivalent modulo bisimilarity to a fragment of μNML defined by a notion of continuity. Analogously to Janin and Walukiewicz’s result, our proofs are automata-theoretic in nature: As another contribution, we introduce classes of parity automata characterising the expressiveness of WMSO and NMSO (on tree models) and of μCML and μNML (for all transition systems).
登录
查看更多内容
任意分支度无限树上的一元二阶逻辑的表达性
DOI：
--
发表时间：
2012
期刊：
影响因子：
--
作者：
Fabio Zanasi;J. V. Benthem;Alessandro Facchini;Helle Hvid Hansen;Benedikt Löwe;Y. Venema
通讯作者：
Y. Venema
描述无限树上的 EF 和传递图上的模态逻辑
DOI：
10.1007/978-3-642-22993-0_28
发表时间：
2011
期刊：
Fundam. Informaticae
影响因子：
--
作者：
B. T. Cate;Alessandro Facchini
通讯作者：
Alessandro Facchini
影响因子：
0.3
作者：
Facundo Carreiro;Alessandro Facchini;Y. Venema;F. Zanasi
通讯作者：
F. Zanasi
模态μ微积分无交替片段的表征定理
DOI：
10.1109/lics.2013.54
发表时间：
2013
期刊：
2013 28th Annual ACM/IEEE Symposium on Logic in Computer Science
影响因子：
--
作者：
Alessandro Facchini;Y. Venema;F. Zanasi
通讯作者：
F. Zanasi
DOI：
10.1007/3-540-61604-7_60
发表时间：
1996-08
期刊：
--
影响因子：
--
作者：
David Janin;I. Walukiewicz
通讯作者：
David Janin;I. Walukiewicz