Interpreted Trajectories
Michael Domaratzki, Grzegorz Rozenberg, Kai Salomaa · Fundamenta Informaticae · 2006
We introduce generalized trajectories where the individual symbols are interpreted as operations performed on the operand words. The various previously considered trajectory-based operations can all be expressed in this formalism. It is shown that the generalized operations can simulate Turing machine computations. We consider the equivalence problem and a notion of unambiguity that is sufficient to make equivalence decidable for regular sets of trajectories under nonincreasing interpretations.