Detail publikace

Multi-Island Finite Automata and Their Even Computations

KOLÁŘ, D. MEDUNA, A. TOMKO, M.

Originální název

Multi-Island Finite Automata and Their Even Computations

Typ

článek v časopise ve Web of Science, Jimp

Jazyk

angličtina

Originální abstrakt

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.

Klíčová slova

finite automata, graph-based decomposition, regulated computation, infinite hierarchies of language families

Autoři

KOLÁŘ, D.; MEDUNA, A.; TOMKO, M.

Vydáno

3. 1. 2022

ISSN

0023-5954

Periodikum

Kybernetika

Ročník

57

Číslo

5

Stát

Česká republika

Strany od

856

Strany do

877

Strany počet

22

URL

https://www.kybernetika.cz/content/2021/5/856

BibTex

@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"
}