Register transducers can be
parameterized by the set of data values from which the \(\omega \) -data words are built,
along with the set of predicates which can be used to test those
values. We distinguish a large class of data sets for which we obtain
decidability results for the later problem, namely the class of
oligomorphic data sets [1]}. Briefly, oligomorphic data sets are
countable sets \(D\)  equipped with a finite set of predicates which satisfies
that for all \(n\) , \(D^n\)  can be partitioned into finitely many equivalence classes
by identifying tuples which are equal up to automorphisms
(predicate-preserving bijections). For example, any set equipped with
equality is oligomorphic, such as \((\mathbb {N}, \lbrace =\rbrace )\) ,
\((\mathbb {Q}, \lbrace <\rbrace )\)  is oligomorphic
while \((\mathbb {N}, \lbrace <\rbrace )\)  is not.
However \((\mathbb {N}, \lbrace <\rbrace )\)  is an
interesting data set in and of itself. We also investigate NRT over such data set, using the fact that it is a substructure of \((\mathbb {Q}, \lbrace <\rbrace )\)  which is oligormorphic.
Our detailed contributions are the following:
