Decision Issues on Functions Realized by Finite Automata
Christian Choffrut, Hratchia Pélibossian, Pierre Simonnet · 1999
Consider a numeration system and a finite set of symbols. Each finite (resp. infinite) sequence on this set represents an integer (resp. a real). Synchronous two-tape automata are devices that define a sequence-to-sequence mapping and can thus be interpreted as performing a relation on integers (resp. reals). Given a numeration system belonging to some natural family defined in this paper and a synchronous two-tape automaton, we show that the following questions are decidable in polynomial time: whether the relation is a function and if this is the case whether it is monotone, injective, continuous (for the reals).