On the Complexity of Multi-entry DFAs

Abstract

Multi-entry finite automata (MDFAs) are a generalization of DFAs that allow for an arbitrary number of initial states. This paper extends existing research on MDFAs by studying their operational state complexity and the computational complexity of their associated decision problems. In particular, we analyze the cost on the number of states of the standard language-theoretic operations when performed on MDFAs and compare these results with the well known complexities for DFAs and NFAs. Additionally, we also analyze the complexity of deciding the membership, emptiness, universality and inclusion problems for MDFAs. Our findings contribute to a deeper understanding of the role that nondeterminism plays in the computational difficulty of certain problems. (c) IFIP International Federation for Information Processing 2027.