trace vs. computation vs. run vs. execution vs. walk Many folks use the terms "trace", "execution", "computation", "run", "walk" ... interchangeably when they speak about state machines with labeled transitions.  Does any work distinguish between these concepts?  E.g., which work says that XXX is a sequence of states, YYY is a sequence of labels and ZZZ is a sequence of states and labels between them, for pairwise different XXX, YYY, ZZZ in {trace, execution, computation, run, walk, ...}?

Here, a state machine with labeled transitions is simply a rooted directed graph (where arbitrarily many roots are allowed, which are interpreted as initial states) with edges labeled by letters from a fixed alphabet.
There is no set terminology for this. Check the definition/use of the term where it appears.

Personally, I'd call it "computation", meaning the sequence of configurations the automaton goes through. And try to be consistent with this usage.