Composing Constraint Automata, State-by-State

When composing Constraint Automata by means of the product, one can run into cases where the amount of resources necessary grows exponentially in the number of automata. If the Constraint Automaton being calculated requires an exponential number of states by its very nature, this is not surprising. However, there are cases where such growth is observed in intermediate products even though the final product requires a number of states that grows linearly in the number of automata. We employ a state-by-state approach to calculate the product and analyze the cases in which exponential growth of intermediary products is prevented, as opposed to the cases where it remains.

hosted by