论文标题
二阶扩展逻辑的复杂性和表达能力
The Complexity and Expressive Power of Second-Order Extended Logic
论文作者
论文摘要
我们研究所有有限结构上的So-horn $^{*} $，So-horn $^{r} $的表达能力和So-horn $^{*r} $。我们表明，so-horn $^{r} $，so-horn $^{*r} $，fo（lfp）彼此重合，而so-horn $^{*} $是适当的so-horn $^{r} $的sublogic。为了证明此结果，我们介绍了datalog $^{*} $ program的概念，datalog $^{r} $程序及其分层版本，s-datalog $^{*} $ program和s-datalog $^{r} $ program。结果表明，在所有结构上，datalog $^{r} $和s-datalog $^{r} $是等价的，datalog $^{*} $是datalog $^{r} $的适当sublogic。 So-horn $^{*} $和SO-HORN $^{r} $可以分别为datalog $^{*} $和datalog $^{r} $的否定。我们还表明，So-Ehorn $^{r} $逻辑是So-Horn捕获所有有限结构的Co-NP的扩展版本。
We study the expressive powers of SO-HORN$^{*}$, SO-HORN$^{r}$ and SO-HORN$^{*r}$ on all finite structures. We show that SO-HORN$^{r}$, SO-HORN$^{*r}$, FO(LFP) coincide with each other and SO-HORN$^{*}$ is proper sublogic of SO-HORN$^{r}$. To prove this result, we introduce the notions of DATALOG$^{*}$ program, DATALOG$^{r}$ program and their stratified versions, S-DATALOG$^{*}$ program and S-DATALOG$^{r}$ program. It is shown that, on all structures, DATALOG$^{r}$ and S-DATALOG$^{r}$ are equivalent and DATALOG$^{*}$ is a proper sublogic of DATALOG$^{r}$. SO-HORN$^{*}$ and SO-HORN$^{r}$ can be treated as the negations of DATALOG$^{*}$ and DATALOG$^{r}$, respectively. We also show that SO-EHORN$^{r}$ logic which is an extended version of SO-HORN captures co-NP on all finite structures.
