computation-theory - 数据记录计算类？

Question

Datalog 不是图灵完备的。

但它的计算类是什么？

是否相当于Finite state machine或 Pushdown machine (即上下文无关)......还是介于两者之间？

Answer 1

假设我们可以访问以下谓词，无论是内置的还是由我们在语言中定义的:

Head(x, y) iff y is a list and x is the first element in the list
Tail(x, y) iff x and y are lists and x is the same as y but is missing y's first element
Equal(x, y) iff x and y are the the same thing

首先，我认为很明显这种语言可以接受所有常规语言。根据 Myhill-Nerode 定理，正则语言的最小 DFA 中的所有状态都对应于不可区分关系下的唯一等价类。似乎我们可以为每个等价类/状态使用一个谓词来表示与输入字符串对应的列表是否属于该类，然后另一个谓词仅当与接受状态对应的谓词之一为真时才为真。因此，对于 {a, b} 上具有偶数 a 和奇数 b 的语言，最小 DFA 有四种状态:

 O
 |
 V
q0<---a--->q1
 ^          ^
 |          |
 b          b
 |          |
 V          V
q2<---a--->q3

这里，q2 是唯一的接受状态。我们的 DataLog 程序可能如下所示:

Q0(()).
Q0(x) :- Head(y, x), Equal(y, 'a'), Tail(z, x), Q1(z).
Q0(x) :- Head(y, x), Equal(y, 'b'), Tail(z, x), Q2(z).
Q1(x) :- Head(y, x), Equal(y, 'a'), Tail(z, x), Q0(z).
Q1(x) :- Head(y, x), Equal(y, 'b'), Tail(z, x), Q3(z).
Q2(x) :- Head(y, x), Equal(y, 'a'), Tail(z, x), Q3(z).
Q2(x) :- Head(y, x), Equal(y, 'b'), Tail(z, x), Q0(z).
Q3(x) :- Head(y, x), Equal(y, 'a'), Tail(z, x), Q2(z).
Q3(x) :- Head(y, x), Equal(y, 'b'), Tail(z, x), Q1(z).
EvenAOddB(x) :- Q2(x).

基于这个例子，我认为很明显我们总是可以以这种方式对转换进行编码，因此可以接受任何常规语言。因此，DataLog 至少与确定性有限自动机一样强大。

我们可以这样定义:

// Last(x, y) iff x is the last element of y
Last(x, y) :- Head(x, y), Tail(z, y), Equal(z, ()).

// AllButLast(x, y) iff x and y are the same list but x is missing the last element of y
AllButLast((), (x)).
AllButLast(x, y) :- Head(w, x), Head(z, y), Equal(w, z),
                    Tail(w', x), Tail(z', y), AllButLast(w', z').

现在我们可以识别与上下文无关语言 a^n b^n 中的字符串对应的列表:

// ANBN(x) iff x is a list beginning with n 'a's followed by n 'b's
ANBN(()).
ANBN(x) :- Head(y, x), Equal(y, 'a'), Tail(z, x),
           Last(w, z), Equal(w, 'b'), AllButLast(z', z),
           ANBN(z').

很容易调整谓词以找到偶数回文的语言，然后很容易调整以找到所有回文的语言。我相信我们也可以让它接受平衡括号等语言。基于这种经验，我猜我们可以接受所有上下文无关语言。

我们可以获得上下文相关的语言吗？让我们试试 a^n b^n c^n。如果我们假设 DataLog 对整数类型有这样的内置谓词:

Zero(x) iff x is equal to zero
Successor(x, y) iff x and y are integers and x = y + 1

那么我认为我们可以，如下:

ANBNCN(()).
ANBNCN(x) :- Zero(y), ANBNCNZ(x, y).

ANBNCNZ(x, y) :- BN(x, y).
ANBNCNZ(x, y) :- Head(w, x), Equal(w, 'a'),
                 Last(z, x), Equal(z, 'c'),
                 Tail(u, x), AllButLast(v, u),
                 Successor(r, y), ANBNCNZ(v, r).

BN(x, y) :- Head(w, x), Equal(w, 'b'),
            Successor(y, z), Tail(u, x),
            BN(u, z).

以上内容如下:

空字符串在 a^n b^n c^n

否则，如果 f(s, 0) 为真，则字符串在 a^n b^n c^n 中

如果 s 仅包含 'b' 的 n 个实例，则 f(s, n) 为真

如果 s 以 a 开头，以 c 结尾，并且 f(s', n + 1) 对中间的所有内容都为真，则 f(s, n) 为真

这应该可以工作，因为每次对 f(s, n) 的递归调用都会从末端剥离一个 a 和一个 c 并记住它已经计数了多少。一旦所有的 a 和 c 都消失了，它就会计算出 b 的许多实例。

基于此，我的感觉是，我们可能也可以使用部分或全部上下文相关语言。可能，缺乏无界执行正是线性有界自动机(短语结构文法中的产生式必须具有不长于 LHS 的 RHS)与一般无限制文法(其中间形式可以任意增长和收缩)的区别。