...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>International journal of computer mathematics >Parameterized complexity of basic decision problems for tree automata
【24h】

Parameterized complexity of basic decision problems for tree automata

机译：树自动机基本决策问题的参数化复杂度

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

摘要

There are many decision problems in automata theory (including membership, emptiness, inclusion and universality problems) that are NP-hard for some classes of tree automata (TA). The study of their parameterized complexity allows us to find new bounds of their nonpolynomial time algorithmic behaviours. We present results of such a study for classical TA, rigid tree automata, TA with global equality and disequality and t-DAG automata. As parameters we consider the number of states, the cardinality of the signature, the size of the term or the t-dag and the size of the automaton.
机译：自动机理论中有许多决策问题（包括隶属度，空性，包含性和通用性问题），对于某些类别的树自动机（TA）来说都是NP难的。对它们的参数化复杂性的研究使我们能够找到其非多项式时间算法行为的新界限。我们介绍了经典TA，刚性树自动机，具有全局平等和不平等的TA和t-DAG自动机的研究结果。作为参数，我们考虑状态数，签名的基数，项或t-dag的大小以及自动机的大小。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号