What sort of automaton does SCXML describe?

Question

Are the limitations of SCXML the same as a deterministic finite automaton/deterministic finite state machine, or is the power of SCXML better captured by other abstract machines/automata? For instance, could SCXML be consider powerful enough to describe a pushdown automaton or a Turing machine?

Answer 1

Without a datamodel, you can map every SCXML document onto an equivalent DFA. You would use a powerset construction not unlike when transforming NFAs to DFAs. But for every practical purpose jbeard4 is right, as soon as you have a turing-complete datamodel, SCXML is turing complete.

Update: I have to correct me on this one. SCXML, even without any datamodel, is already turing-complete! Using the internal queue as a FIFO, you can model a deterministic queue automaton (DQA) which is equivalent to a turing machine. Thus, SCXML is turing-complete.

Answer 2

In practice, SCXML is turing complete, because it can use script tags to execute arbitrary Turing-complete code.