Computational Complexity, volume 25, issue 4, pages 775-814

The complexity of intersecting finite automata having few final states

Publication typeJournal Article
Publication date2014-09-06
scimago Q2
SJR0.453
CiteScore1.5
Impact factor0.7
ISSN10163328, 14208954
General Mathematics
Computational Mathematics
Computational Theory and Mathematics
Theoretical Computer Science
Abstract
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 $${\oplus}$$ 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 (under the usual hypotheses on complexity classes) the complexity of the intersection nonemptiness and related problems in each case.
Found 

Top-30

Journals

1
2
3
1
2
3

Publishers

1
2
3
1
2
3
  • We do not take into account publications without a DOI.
  • Statistics recalculated only for publications connected to researchers, organizations and labs registered on the platform.
  • Statistics recalculated weekly.

Are you a researcher?

Create a profile to get free access to personal recommendations for colleagues and new articles.
Share
Cite this
GOST | RIS | BibTex | MLA
Found error?