__Preprint:__

**
Sam Buss, Douglas Cenzer, Mia Minnes and Jeffrey B. Remmel
Injection Structures Specified by Finite State Transducers
In **

**
Download manuscript: PDF.
**

**Abstract:**
An injection structure *A = (A,f)* is a set *A*
together with a one-place
one-to-one function *f*. *A* is an FST injection structure if
*A* is a regular set,
that is, the set of words accepted by some finite automaton, and *f*
is realized by a finite-state transducer. We initiate the study of
FST injection structures. We show that the model checking
problem for FST injection structures is undecidable which
contrasts with the fact that the model checking problem for automatic
relational structures is decidable. We also explore which
isomorphisms types of injection structures can be realized by
FST injections. For example, we completely characterize the isomorphism
types that can be realized by FST injection structures over a unary alphabet.
We show that any FST injection structure is isomorphic to an FST injection
structure over a binary alphabet. We also prove a number of positive
and negative results about the possible isomorphism types
of FST injection structures over an arbitrary alphabet.