Affiliations: Jodrey School of Computer Science, Acadia University,
Wolfville, NS Canada B4P 2R6, Canada. E-mail: mike.domaratzki@acadiau.ca | Leiden Institute of Advanced Computer Science, LIACS,
University of Leiden, Niels Bohr Weg 1 2333 CA Leiden, The Netherlands.
E-mail: rozenber@liacs.nl | School of Computing, Queen's University,
Kingston, ON Canada K7L 3N6, Canada. E-mail: ksalomaa@cs.queensu.ca
Abstract: 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.
