The grand composition ofi¾źn automata may have a number of states/transitions exponential ini¾źn. When it does, it seems not unreasonable for the computation of that grand composition to require exponentially many resources time, space, or both. Conversely, if the grand composition ofi¾źn automata has a number of states/transitions only linear ini¾źn, we may reasonably expect the computation of that grand composition to also require only linearly many resources.#R##N##R##N#Recently and problematically, we saw cases of linearly-sized grand compositions whose computation required exponentially many resources. We encountered these cases in the context of Reo a graphical language for coordinating components in component-based software, constraint automata a general formalism for modeling systems' behavior, and our compiler for Reo based on constraint automata. Combined with earlier research on constraint automata verification, these ingredients facilitate a correctness-by-construction approach to component-based software engineering--one of the hallmarks in Sifakis' "rigorous system design". To achieve that ambitious goal, however, we need to solve the previously stated problem. In this paper we present such a solution.
['Sung-Shik T. Q. Jongmans', 'Tobias Kappé', 'Farhad Arbab']
Composing Constraint Automata, State-by-State