On Succinctness of Hierarchical State Diagrams in Absence of Message Passing

We show a subexponential but superpolynomial lower bound for flattening problem for statecharts. The result explains why common flattening algorithms explode, if the signal communication is excluded from the target language. This specifically a#ects flattening-based strategies for automatic model-based program synthesis