2012 | OriginalPaper | Chapter
The Complexity of Intersecting Finite Automata Having Few Final States
Authors : Michael Blondin, Pierre McKenzie
Published in: Computer Science – Theory and Applications
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The problem of determining whether several finite automata accept a common word is closely related to the well-studied membership problem in transformation monoids. We review the complexity of the intersection problem and raise the issue of limiting the number of final states in the automata involved. In particular, we consider commutative automata with at most two final states and we partially elucidate the complexity of their intersection nonemptiness and related problems.