Automata with Equational Constraints
Michael J. Dinneen, Bakh Khoussainov · 1999
We introduce the concept of finite automata with algebraic constraints. We show that the languages accepted by these automata are closed under the Boolean operations. We give e#cient polynomial-time algorithms for some decision problems related to these automata and their languages, including su#cient conditions for when we can determinize automata in polynomial time. 1 Introduction The study of complexity-theoretic, algebraic or computability-theoretic properties of a set of problems is usually motivated by the fact that the set is closed under certain natural operations. For example, the set may be Boolean, that is closed under the operations of union, intersection and complementation. For instance, the set of all Turing decidable problems is Boolean. Also the set of problems decidable in polynomial time (e.g. the class P) and set of regular languages are Boolean classes. An important non-Boolean class, which forms a lattice under the union and intersection operations, is the s...