Succinctness of Hierarchical State Diagrams in Absence ofMessage Passing

TR-2004-42, Author: Andrzej Wasowski

Andrzej Wąsowski

February, 2004

Abstract

We show a subexponential but superpolynomial lower bound for
flattening problem for statecharts. The result presented is resistant
to many variations in statecharts semantics.
The immediate consequence is that usage of common flattening
algorithms in the implementations of tools should be carefully
examined, taking into account presence of signal communication in the
target language. This specifically affects flattening-based
strategies for automatic model-based program synthesis.

---

Technical report [TR-2004-42] in IT University Technical Report Series, February, 2004.

Available as PDF.