• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Language and automata theory and applications >The Parameterized Complexity of Chosen Problems for Finite Automata on Trees
【24h】

The Parameterized Complexity of Chosen Problems for Finite Automata on Trees

机译：树上有限自动机选择问题的参数复杂度

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

There are many decision problems in automata theory (including membership, emptiness, emptiness of intersection, inclusion and universality problems) that for some classes of tree automata are NP-hard. The study of their parameterized complexity allows us to find new bounds of their non-polynomial time algorithmic behaviors. We present results of such a study for classical tree automata (TA), rigid tree automata (RTA), tree automata with global equality and disequal-ity (TAGED) and t-DAG automata.
机译：在自动机理论中有很多决策问题（包括隶属度，空度，交集的空度，包含和普遍性问题），对于某些类别的树自动机来说，它们是NP-难的。对它们的参数化复杂性的研究使我们能够找到其非多项式时间算法行为的新界限。我们介绍了对经典树自动机（TA），刚性树自动机（RTA），具有全局平等和不平等性的树自动机（TAGED）和t-DAG自动机的研究结果。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号