Boundedness of Monadic FO over Acyclic Structures
Boundedness of Monadic FO over Acyclic Structures
复制标题
非循环结构上 Monadic FO 的有界性
DOI：
10.1007/978-3-540-73420-8_50
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
N. Schweikardt
中科院分区：
文献类型：
--
作者：
S. Kreutzer;M. Otto;N. Schweikardt
我们把一元最小不动点的有界性问题作为一个决策问题来研究。虽然已知这个问题在一般情况下是不可判定的，甚至对于语法上非常受限的潜在一阶公式类，我们在这里得到了限制于非循环结构的任意一阶公式上的一元不动点的有界性问题的可判定性结果。
We study the boundedness problem for monadic least fixed points as a decision problem. While this problem is known to be undecidable in general and even for syntactically very restricted classes of underlying first-order formulae, we here obtain a decidability result for the boundedness issue for monadic fixed points over arbitrary first-order formulae in restriction to acyclic structures.
登录
查看更多内容
DOI：
--
发表时间：
1998
期刊：
Proceedings. Thirteenth Annual IEEE Symposium on Logic in Computer Science (Cat. No.98CB36226)
影响因子：
--
作者：
Phokion G. Kolaitis;M. Otto
通讯作者：
M. Otto
DOI：
10.1109/lics.2006.13
发表时间：
2006
期刊：
21st Annual IEEE Symposium on Logic in Computer Science (LICS'06)
影响因子：
--
作者：
Anuj Dawar;Martin Grohe;Stephan Kreutzer;Nicole Schweikardt
通讯作者：
Nicole Schweikardt
数据库逻辑程序的不可判定优化问题
DOI：
10.1145/174130.174142
发表时间：
1993
期刊：
J. ACM
影响因子：
--
作者：
H. Gaifman;Harry G. Mairson;Y. Sagiv;Moshe Y. Vardi
通讯作者：
Moshe Y. Vardi
DOI：
--
发表时间：
1979
期刊：
影响因子：
--
作者：
J. Ferrante;C. Rackoff
通讯作者：
C. Rackoff
DOI：
--
发表时间：
2005
期刊：
Annual Conference for Computer Science Logic
影响因子：
--
作者：
Michael Benedikt;L. Segoufin
通讯作者：
L. Segoufin