首页    期刊浏览 2024年11月30日 星期六
登录注册

文章基本信息

  • 标题:The Complexity of Intersecting Finite Automata Having Few Final States
  • 本地全文:下载
  • 作者:Michael Blondin ; Andreas Krebs ; Pierre McKenzie
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2012
  • 卷号:2012
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    The problem of determining whether several finite automata accept a word in common is closely related to the well-studied membership problem in transformation monoids. We raise the issue of limiting the number of final states in the automata intersection problem. For automata with two final states, we show the problem to be ?L-complete or NP-complete according to whether a nontrivial monoid other than a direct product of cyclic groups of order 2 is allowed in the automata.We further consider idempotent commutative automata and (abelian, mainly) group automata with one, two or three final states over a singleton or larger alphabet, elucidating the complexity of the intersection nonemptiness and related problems in each case.

  • 关键词:finite automata; Intersection Problem; L complete; Monoids; NP-complete; Point Spread Problem
国家哲学社会科学文献中心版权所有