×

Decision issues on functions realized by finite automata. (English) Zbl 0943.68106

Summary: 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).

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite