On the Complexity of Symbolic Finite-State Automata
This work addresses complexity analysis for symbolic automata, which is incremental as it builds on existing SFA theory by refining measures and considering special cases.
The paper revisits the complexity of procedures on symbolic finite-state automata (SFAs), analyzing them based on measures like number of states and transition predicate size, with attention to special forms such as normalized and neat SFAs and monotonic effective Boolean algebras.
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.