Non-returning deterministic and nondeterministic finite automata with translucent letters

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F23%3A10477032" target="_blank" >RIV/00216208:11320/23:10477032 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=s~8LVyCHmD" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=s~8LVyCHmD</a>

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

Non-returning deterministic and nondeterministic finite automata with translucent letters

Popis výsledku v původním jazyce

Here, we propose a variant of the nondeterministic finite automaton with translucent letters (NFAwtl), which, after reading and deleting a letter, does not return to the left end of its tape, but instead continues from the position of the letter just deleted. When the end-of-tape marker is reached, our automaton can decide whether to accept, reject, or continue, which means that it reads the remaining tape contents again from the beginning. This type of automaton, called a non-returning finite automaton with translucent letters or an nrNFAwtl, is strictly more expressive than the NFAwtl. We study the expressive capacity of this type of automaton and that of its deterministic variant, comparing them to various other types of finite automata that do not simply read their input from left to right. Also, we are interested in the closure properties of the resulting classes of languages and in the complexity of the fixed membership problem.

Název v anglickém jazyce

Non-returning deterministic and nondeterministic finite automata with translucent letters

Popis výsledku anglicky

Here, we propose a variant of the nondeterministic finite automaton with translucent letters (NFAwtl), which, after reading and deleting a letter, does not return to the left end of its tape, but instead continues from the position of the letter just deleted. When the end-of-tape marker is reached, our automaton can decide whether to accept, reject, or continue, which means that it reads the remaining tape contents again from the beginning. This type of automaton, called a non-returning finite automaton with translucent letters or an nrNFAwtl, is strictly more expressive than the NFAwtl. We study the expressive capacity of this type of automaton and that of its deterministic variant, comparing them to various other types of finite automata that do not simply read their input from left to right. Also, we are interested in the closure properties of the resulting classes of languages and in the complexity of the fixed membership problem.

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

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2023

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

2804-7346

Svazek periodika

57

Číslo periodika v rámci svazku

October

Stát vydavatele periodika

FR - Francouzská republika

Počet stran výsledku

35

Strana od-do

8

Kód UT WoS článku

001097977100002

EID výsledku v databázi Scopus

2-s2.0-85176091681