On the Complexity of Symbolic Finite-State Automata
  We revisit the complexity of procedures on SFAs (such as intersection,
emptiness, etc.) and analyze them according to the measures we find suitable
for symbolic automata: the number of states, the maximal number of transitions
exiting a state, and the size of the most complex transition predicate. We pay
attention to the special forms of SFAs: {normalized SFAs} and {neat SFAs}, as
well as to SFAs over a {monotonic} effective Boolean algebra.
