• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Annual ACM/IEEE Symposium on Logic in Computer Science >The complexity of regular abstractions of one-counter languages
【24h】

The complexity of regular abstractions of one-counter languages

机译：一站式语言的常规抽象的复杂性

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

摘要

We study the computational and descriptional complexity of the following transformation: Given a one-counter automaton (OCA) A, construct a nondeterministic finite automaton (NFA) 13 that recognizes an abstraction of the language G(A): its (1) downward closure, (2) upward closure, or (3) Parikh image. For the Parikh image over a fixed alphabet and for the upward and downward closures, we find polynomial-time algorithms that compute such an NFA. For the Parikh image with the alphabet as part of the input, we find a quasi-polynomial time algorithm and prove a completeness result: we construct a sequence of OCA that admits a polynomial-time algorithm iff there is one for all OCA. For all three abstractions, it was previously unknown whether appropriate NFA of sub-exponential size exist.
机译：我们研究以下转换的计算和描述复杂度：给定一个单计数器自动机（OCA）A，构造一个可识别语言G（A）的抽象的不确定性有限自动机（NFA）13：（1）向下闭合，（2）向上闭合或（3）Parikh图像。对于固定字母表上的Parikh图像以及向上和向下的闭合，我们发现了可计算此类NFA的多项式时间算法。对于以字母作为输入一部分的Parikh图像，我们找到了一个拟多项式时间算法并证明了完整性结果：如果所有OCA都有一个，则构造一个允许多项式时间算法的OCA序列。对于所有三个抽象，以前都不知道是否存在适当的亚指数大小的NFA。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号