Multi-Island Finite Automata and Their Even Computations

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Multi-Island Finite Automata and Their Even Computations

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Multi-Island Finite Automata and Their Even Computations

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2022

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Kybernetika

ISSN

0023-5954

e-ISSN

1805-949X

Svazek periodika

57

Číslo periodika v rámci svazku

5

Stát vydavatele periodika

CZ - Česká republika

Počet stran výsledku

22

Strana od-do

856-877

Kód UT WoS článku

000752440900008

EID výsledku v databázi Scopus

2-s2.0-85128282449