Publication Details
Multi-Island Finite Automata and Their Even Computations
Meduna Alexandr, prof. RNDr., CSc. (DIFS)
Tomko Martin, Ing. (DIFS)
finite automata, graph-based decomposition, regulated computation, infinite
hierarchies of language families
This paper discusses n-island finite automata whose transition graphs can be
expressed as n-member sequences of islands i1, i2, ..., in, where there is
a bridge leaving ij and entering i(j+1) for each 1 <= j <= n - 1. It
concentrates its attention on even computation defined as any sequence of moves
during which these automata make the same number of moves in each of the islands.
Under the assumption that these automata work only in an evenly computational
way, the paper proves its main result stating that n-island finite automata and
Rosebrugh-Wood n-parallel right-linear grammars are equivalent. Then, making use
of this main result, it demonstrates that under this assumption, the language
family defined by n-island finite automata is properly contained in that defined
by (n+1)-island finite automata for all n >= 1. The paper also points out that
this infinite hierarchy occurs between the family of regular languages and that
of context-sensitive languages. Open questions are formulated in the conclusion.
@article{BUT168522,
author="Dušan {Kolář} and Alexandr {Meduna} and Martin {Tomko}",
title="Multi-Island Finite Automata and Their Even Computations",
journal="Kybernetika",
year="2022",
volume="57",
number="5",
pages="856--877",
doi="10.14736/kyb-2021-5-0856",
issn="0023-5954",
url="https://www.kybernetika.cz/content/2021/5/856"
}