Polynomial complete problems in automata theory

Kozen (1977) proved that the emptiness problem for regular languages intersection is polynomial complete. In this paper we show that many other problems concerning deterministic finite state automata are polynomial complete and therefore intractable for solution. On the other hand, simplified versions of these problems can be solved in polynomial time by deterministic algorithms. This work is a part of the research on automata theory carried out at the Institute of Cybernetics headed by academician V.M. Glushkov.