• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International conference on implementation and application of automata >Some Decision Problems Concerning NPDAs, Palindromes, and Dyck Languages
【24h】

Some Decision Problems Concerning NPDAs, Palindromes, and Dyck Languages

机译：有关NPDA，回文和戴克语言的一些决策问题

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We address several types of decision questions related to context-free languages when an NPDA is given as input. First we consider the question of whether the NPDA makes a bounded number of stack reversals (over all accepting inputs) and show that this problem is undecidable even when the NPDA is only 2-ambiguous. We consider the same problem for counter machines (i.e., whether the counter makes a bounded number of reversals) and show that it is also undecidable. On the other hand, we show that the problem is decidable for unambiguous NPDAs even when augmented with reversal-bounded counters. Next, we look at problems of equivalence, containment and disjointness with fixed languages. With the fixed language Lo being one of the following: P = {x#x~r | x ∈ (0 + 1)*}, P_u = {xx~r | x ∈ (0 + 1)*}, D_k = Dyck language with fc-type of parentheses, or S_k = two-sided Dyck language with k types of parentheses, we consider problems such as: 'Is L(M)(⊂)L_0 = Ø?', 'Is L(M) ⊂ L_0?', or 'Is L(M) = L_0?, where M is an input NPDA (or a restricted form of it). For example, we show that the problem, 'Is L(M) (⊂) P?', is undecidable when M is a deterministic one-counter acceptor, while the problem 'Is L(M)⊂ P?' is decidable even for NPDAs augmented with reversal-bounded counters. Another result is that the problem 'Is L(M) ⊂ P_u?' is decidable in polynomial time for M an NPDA. We also show several other related decidability and undecidability results.
机译：当输入NPDA作为输入时，我们将解决与上下文无关语言有关的几种决策问题。首先，我们考虑NPDA是否进行一定数量的堆栈反转（在所有接受的输入上）的问题，并表明即使NPDA只有2个模棱两可的情况，这个问题也无法确定。对于计数器机器，我们考虑了相同的问题（即，计数器是否进行有限数量的冲销），并表明它也是不确定的。另一方面，我们表明，即使使用反转边界计数器增加了明确的NPDA，该问题也是可以确定的。接下来，我们研究固定语言的等价性，包容性和不相交性的问题。固定语言Lo为以下之一：P = {x＃x〜r | x∈（0 + 1）*}，P_u = {xx〜r | x∈（0 + 1）*}，D_k =带fc型括号的戴克语言，或者S_k =带k型括号的双面戴克语言，我们考虑这样的问题：'是L（M）（⊂） L_0 =Ø？，“ L（M）⊂L_0？”或“ L（M）= L_0？”，其中M是输入NPDA（或其限制形式）。例如，我们证明当M是确定性单柜台受体时，问题“ L（M）（））P？”是不确定的，而问题“ L（M）⊂P？”是不确定的。即使对于带有反转界计数器的NPDA而言，它也是可以确定的。另一个结果是问题“是L（M）⊂P_u吗？”对于一个NPDA，在多项式时间中是可确定的。我们还显示了其他一些相关的可判定性和不可判定性结果。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号