On Double-Jumping Finite Automata and Their Closure Properties

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F19%3APU131285" target="_blank" >RIV/00216305:26230/19:PU131285 - isvavai.cz</a>

Výsledek na webu

<a href="https://www.rairo-ita.org/articles/ita/abs/2018/02/ita180059/ita180059.html" target="_blank" >https://www.rairo-ita.org/articles/ita/abs/2018/02/ita180059/ita180059.html</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1051/ita/2018013" target="_blank" >10.1051/ita/2018013</a>

Jazyk výsledku

angličtina

Název v původním jazyce

On Double-Jumping Finite Automata and Their Closure Properties

Popis výsledku v původním jazyce

The present paper modifies and studies jumping finite automata so they always perform two simultaneous jumps according to the same rule. For either of the two simultaneous jumps, it considers three natural directions---(1) to the left, (2) to the right, and (3) in either direction. According to this jumping-direction three-part classification, the paper investigates the mutual relation between the language families resulting from jumping finite automata performing the jumps in these ways and the families of regular, linear, context-free, and context-sensitive languages. It demonstrates that most of these language families are pairwise incomparable. In addition, many closure and non-closure properties of the resulting language families are established.

Název v anglickém jazyce

On Double-Jumping Finite Automata and Their Closure Properties

Popis výsledku anglicky

The present paper modifies and studies jumping finite automata so they always perform two simultaneous jumps according to the same rule. For either of the two simultaneous jumps, it considers three natural directions---(1) to the left, (2) to the right, and (3) in either direction. According to this jumping-direction three-part classification, the paper investigates the mutual relation between the language families resulting from jumping finite automata performing the jumps in these ways and the families of regular, linear, context-free, and context-sensitive languages. It demonstrates that most of these language families are pairwise incomparable. In addition, many closure and non-closure properties of the resulting language families are established.

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

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2018

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

RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS

ISSN

0988-3754

e-ISSN

1290-385X

Svazek periodika

52

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

FR - Francouzská republika

Počet stran výsledku

15

Strana od-do

185-199

Kód UT WoS článku

000459294200007

EID výsledku v databázi Scopus

2-s2.0-85062218999