As already 2-monotone -automata accept -complete languages,
we introduce a restricted variant of -monotonicity
for restarting automata, called .
For restarting automata without auxiliary symbols,
this restricted variant still yields infinite hierarchies.
However, for restarting automata with auxiliary symbols,
all degrees of sequential monotonicity collapse to the
first level, implying that -automata
that are sequentially monotone of degree for any
only accept context-free languages.
We consider systems consisting of finite automata communicating by exchanging messages and working on the same read-only data. We investigate the situation in which the automata work with constant but different speeds. We assume furthermore that the automata are not aware of the speeds and they cannot measure them directly. Nevertheless, the automata have to compute a correct output. We call this model multi-speed systems of finite automata. Complexity measure that we consider here is the number...
We consider systems consisting of finite automata communicating by exchanging messages
and working on the same read-only data.
We investigate the situation in which
the
automata work with constant
but different speeds. We assume furthermore that
the automata are not aware of the speeds and
they cannot measure them directly.
Nevertheless, the
automata have to compute a
correct output.
We call this model multi-speed systems of finite automata.
Complexity measure that we consider here is the...
Download Results (CSV)