State machine with knowledge of prior 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