数据记录计算类？

Question

Datalog不是图灵完备的。

但它的计算类是什么？

它相当于有限状态机或下推机（即上下文无关）……还是介于两者之间？

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^nb^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^nb^nc^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^nb^nc^n 中
• 否则，如果 f(s, 0) 为 true，则字符串位于 a^nb^nc^n 中
• 如果 s 仅包含 n 个 'b' 实例，则 f(s, n) 为真
• 如果 s 以 a 开头，以 c 结尾，则 f(s, n) 为真，并且 f(s', n + 1) 对于中间的所有内容都为真

这应该可行，因为 f(s, n) 的每次递归调用都会从末尾去除一个 a 和一个 c 并记住它已经计数了多少。然后，一旦所有 a 和 c 都消失，它就会计算出 b 的多个实例。

基于此，我的感觉是我们也可以做一些或全部上下文相关语言。也许，缺乏无限制的执行正是线性有界自动机（短语结构语法中的产生式必须具有不长于左方的右侧）与一般无限制语法（其中间形式可以任意增长和收缩）的区别。