2 Wilhelm-Schickard-Institut für Informatik,

Abstract. The problem of determining whether several finite automata accept a word in common is closely related to the well-studied member-ship problem in transformation monoids. We raise the issue of limiting the number of final states in the automata intersection problem. For au-tomata 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 sin-gleton or larger alphabet, elucidating the complexity of the intersection nonemptiness and related problems in each case.