Multi-Island Finite Automata and Their Even Computations
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F22%3APU138909" target="_blank" >RIV/00216305:26230/22:PU138909 - isvavai.cz</a>
Result on the web
<a href="https://www.kybernetika.cz/content/2021/5/856" target="_blank" >https://www.kybernetika.cz/content/2021/5/856</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.14736/kyb-2021-5-0856" target="_blank" >10.14736/kyb-2021-5-0856</a>
Alternative languages
Result language
angličtina
Original language name
Multi-Island Finite Automata and Their Even Computations
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
—
Continuities
S - Specificky vyzkum na vysokych skolach
Others
Publication year
2022
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Kybernetika
ISSN
0023-5954
e-ISSN
1805-949X
Volume of the periodical
57
Issue of the periodical within the volume
5
Country of publishing house
CZ - CZECH REPUBLIC
Number of pages
22
Pages from-to
856-877
UT code for WoS article
000752440900008
EID of the result in the Scopus database
2-s2.0-85128282449