# Logical Equivalents of Finite State Transducers

There's a notion of "regular" function on words in automata theory that corresponds nicely to functions in WS1S/Büchi Arithmetic/the logic of words with a prefix and equal-length relation. Specifically, a function $$f$$ is "regular" if the set of all $$(x_1,\ldots,x_n,y)$$ with $$y = f(x_1,\ldots,x_n)$$ is accepted by some DFA that reads in inputs in parallel. That is, it reads in all first characters, then all second characters, then all third characters, etc., reading in an "end of word" character for inputs shorter than the longest.

There's another notion of function in automata theory given by finite state transducers, but this is not the same. It's easy to construct a transducer that removes all $$a$$s from a word, but this function is not "regular" as above. Are there any interesting logical correlates of finite state transducers?

Anyway, the answer is yes, these function classes admit logical characterizations. Roughly, the idea is to use the model-theoretic notion of an interpretation. Given two signatures $$\Sigma$$ and $$\Gamma$$, an interpretation $$\Sigma \to \Gamma$$ is (roughly) a $$\Gamma$$-definition of each symbol in $$\Sigma$$. (This can be with respect to whatever base logic you choose.) An interpretation gives you a map between structures in the other direction, that is, from $$\Gamma$$-structures to $$\Sigma$$-structures. (Roughly: given a $$\Gamma$$-structure, the interpretation allows us to interpret the symbols in $$\Sigma$$.)
In finite model theory, strings over a fixed alphabet are identified with finite structures in a related signature. So a map from $$\Gamma$$-structures to $$\Sigma$$-structures becomes a function $$\Gamma^\star \to \Sigma^\star$$ (conflating alphabets and signatures).