Logics with counting and equivalence
Logics with counting and equivalence
复制标题
具有计数和等价的逻辑
DOI：
10.1145/2603088.2603117
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Pratt-Hartmann I
中科院分区：
文献类型：
--
作者：
Pratt-Hartmann I
我们考虑带计数的一阶逻辑的两个变量片段，满足一个可区分的二元谓词被解释为等价的规定。证明了该逻辑的可满足性问题和有限可满足性问题都是NExpTime-完全的。进一步证明了具有计数和两个等价性的二元一阶逻辑的相应问题都是不可判定的。
We consider the two-variable fragment of first-order logic with counting, subject to the stipulation that a single distinguished binary predicate be interpreted as an equivalence. We show that the satisfiability and finite satisfiability problems for this logic are both NExpTime-complete. We further show that the corresponding problems for two-variable first-order logic with counting andtwoequivalences are both undecidable.
登录
查看更多内容
具有传递性的二变量保护逻辑的计数
DOI：
--
发表时间：
2005
期刊：
Symposium on Theoretical Aspects of Computer Science
影响因子：
--
作者：
Lidia Tendera
通讯作者：
Lidia Tendera
具有一个传递关系的 FO^2 是可判定的
DOI：
--
发表时间：
2013
期刊：
Symposium on Theoretical Aspects of Computer Science
影响因子：
--
作者：
W. Szwast;Lidia Tendera
通讯作者：
Lidia Tendera
具有等价闭包的二变量一阶逻辑
DOI：
--
发表时间：
2012
期刊：
2012 27th Annual IEEE Symposium on Logic in Computer Science
影响因子：
--
作者：
Emanuel Kieronski;Jakub Michaliszyn;Ian Pratt;Lidia Tendera
通讯作者：
Lidia Tendera
具有等价关系的二变量一阶逻辑的有限可满足性
DOI：
--
发表时间：
2009
期刊：
2009 24th Annual IEEE Symposium on Logic In Computer Science
影响因子：
--
作者：
Emanuel Kieronski;Lidia Tendera
通讯作者：
Lidia Tendera
一些简单形式化理论的不可判定性
DOI：
--
发表时间：
1953
期刊：
影响因子：
--
作者：
A. Janiczak
通讯作者：
A. Janiczak