There is a very natural model of finite-state reduction, namely the most general finite-state transducer -- one input tape, one output tape, non-deterministic, transitions can be labelled with arbitrary regular sets (with empty strings) on both the input and output side. This can be shown equivalent to Henning's single-symbol operations, but allows for much more intuitive reductions, still within the finite-state realm. The ambiguity Henning speaks of is just the non-determinism.
You can even allow such a transducer to have secondary storage (like a Turing Machine, pushdown automaton, etc) as long as there is a uniform constant bound on the size of the secondary storage.
Taking that a step further, you can use transformations that do arbitrary computations, but again show that the size of memory needed over all inputs is uniformly bounded, that is, there's a $k$ not depending on the input that limits the size of all memory used. Thus you can use pseudo-code, Java or whatever formalism you like, including forking, that is, non-determinism -- as long as you have:
- one input and one output tape/stream
- both streams processed in a single pass
- total memory is uniformly bounded across all forks/threads
In other words, you don't have to model finite-state transformations with transitions on a finite graph, which is a very brittle and finicky programming model. You can use any convenient programming formalism or model with any structuring of memory you like, as long as it satisfies those criteria.
In fact, I propose that as a sort of finite-state equivalent of the Turing-Church thesis. Not quite as crisp as the Turing-Church Thesis in the world of recursive functions, but very useful.