Constructs a new state, given its predecessor state, the new marking, the
transition leading from the predecessor state to the new state, the cost
to go from the predecessor state to the new state, and the trace still
left to replay from the new state.