Sub-state machines have been around since at least 1970. They were used in NLP, where they were coined Augmented Transition Networks. Those were FSA with a stac

Sub-state machines have been around since at least 1970. They were used in NLP, where they were coined Augmented Transition Networks. Those were FSA with a stack (and variables), but when you don't do recursion, it's substituting an edge with another FSA. Bad Wiki entry (because ATMs are really bad at parsing natural language), but at least it contains a reference: https://en.wikipedia.org/wiki/Augmented_transition_network https://en.wikipedia.org/wiki/Augmented_transition_network