Abstract:
A class of decision problems is Boolean if it is closed under the
set{theoretic operations of union, intersection and complementation.
The paper introduces new Boolean classes of decision problems based
on algebraic constraints imposed on transitions of nite automata. We
discuss issues related to speci cations of these classes from algebraic,
computational and proof{theoretic points of view.