State machine with knowledge of prior states? I'm attepting to model a process flow where the transition to the next state is occasionally based on not only the input to the current state, but a prior state as well.

Below is an example graph descibring the process. The essence is: If both State Q1 and State Q3 recieve an input of one, after State 3, transition to State Q4, otherwise transition to State Q5.



I understand that it would be possible to model this using a finite-state machine where we duplicate any states between those that we are interested in. The example below demonstrates this with States Q2a and Q2b corresponding to the differences in input at state Q1



However, as the number of conditions and the gaps between them grows (both of which are possible in the process I'm looking at), the number of states grows exponentially.

The question is, what other computational models could be used to describe a process where an arbitrary number of inputs could be used to control transition between states?
In digital design we would call the thing you are looking for an algorithmic state machine.  In compiler design we would call it a control flow graph.  The idea in either case is that you divide the state problem into two parts, one part represents the control state, the other part represents the data path.  You label the states with how you want the data path to be modified, and the data path has some boolean outputs that you use to determine which way the control state should change.

Formally, you are describing a Moore machine where each state describes a set of control signals that will be sent to tell the data path how to modify itself, and the data-path in turn has a small set of boolean outputs that are used as the input language to the control state machine.

Your original problem would then have a control state, Q, and two variables, v1 and v2 and the graph would look something like:

       q1: v1 &lt;- some_function(...)
                |
                v
       q2: something else happens
                |
                v
    q3: v3 &lt;- some_other_function(...)
        test (v1==1 &amp;&amp; v3==1)?
       /                 \
       | true             | false
       v                  v
q4: something    q5: something else
       \                  /
        \                /
         v              v
           q6: whatever