|
Journal of Automata, Languages and Combinatorics
formerly:
Journal of Information Processing and Cybernetics /
Elektronische Informationsverarbeitung und Kybernetik
|
|
@article{jalc040302,
author = {Choffrut, Christian and Pelibossian, Hratchia
and Simonnet, Pierre},
title = {Decision Issues on Functions Realized by Finite Automata},
journal = jalc,
year = 1999,
volume = 4,
number = 3,
pages = {171--181},
keywords = {numeration systems, on-line functions of numbers,
synchronous automata, decision problems},
abstract = {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).\par
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).}
}