可确定的非文化敏感语言

Question

可以说，为描述日常问题而创建的大多数语言都是上下文敏感性。另一方面，可能会发现某些不递归甚至无法递归依赖的语言。

这两种类型之间是递归的非文化敏感语言。维基百科给出一个例子 这里:

一个非上下文敏感的递归语言的示例是任何递归语言，其决策是一个expass-hard问题，例如，一组等效的正则表达式和指数。

因此，问题：存在哪些其他问题可决定但不含义敏感的问题？这类问题与可决定的expspace-hard相同吗？

Answer 1

CSL与$ Mathsf {nspace}（n）$相同 （非确定性线性空间）。任何在$ mathsf {nspace}（n）$之外的语言不是CSL。

要了解情况，请记住，$ sat in mathsf {nspace}（n）$甚至TQBF。

存在哪些其他问题可决定但不敏感的问题？

有很多问题。对于大于$ mathsf {pspace} $大于$ mathsf {pspace} $的复杂性类别的任何问题，因为$ mathsf {nspace}（nspace}（n）$之类的问题是$ mathsf {pspace} $，因为（多项式时间）减少可以吹出多项式输入的大小）。给出一个示例将意味着证明包含问题的复杂性类别的较低障碍，这是非常艰巨的任务。到目前为止，我们知道的唯一主要方法是对角线化，这意味着较大的阶级应该能够模拟较小的类。

因此，$ mathsf {expspace text { - }硬} $似乎是一个自然的地方，可以开始寻找不是CSL的语言示例。

这类问题与可决定的expspace-hard相同吗？

否 空间层次定理, ，在$ mathsf {nspace}（n^2）$中有一些语言，这些语言不在$ mathsf {nspace}（n）$中。如果您要提出好的例子，那将很困难，因为该定理使用对角线化工作，因此所证明的能够满足这些条件的语言非常人为。

我建议您从$ Mathsf {nspace}（n）$向分离$ mathsf {nspace}（n^2）$分开的自然问题。

Answer 2

就像$ {a^nb^n：n geq 0 } $是不含上下文但不是常规的，语言$ l = {a^nb^nc^n：n geq 0 } $是决定性的。但不是无上下文。但是，可以使用对数空间来解决$ l $（您只需要为每个符号$ a $ a $，$ b $和$ c $的计数器），因此它不是expace-hard。

另外，语言$ {（r_1，r_2）：l（r_1）= l（r_2）} $，其中$ r_1 $和$ r_2 $是正则表达式，是pspace-comment。我几乎确定这不是上下文敏感的，但是我不记得证据，而且我正在用手机写作，因此寻找参考并不容易。