Non-Returning 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%2F22%3A10456315" target="_blank" >RIV/00216208:11320/22:10456315 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.4204/EPTCS.367.10" target="_blank" >https://doi.org/10.4204/EPTCS.367.10</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4204/EPTCS.367.10" target="_blank" >10.4204/EPTCS.367.10</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Non-Returning 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 rather continues from the position of the letter just deleted. When the end-of-tape marker is reached, our automaton can decide whether to accept, to reject, or to continue, which means that it again reads the remaining tape contents 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. Also we are interested in closure properties of the resulting classes of languages and in decision problems.

Název v anglickém jazyce

Non-Returning 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 rather continues from the position of the letter just deleted. When the end-of-tape marker is reached, our automaton can decide whether to accept, to reject, or to continue, which means that it again reads the remaining tape contents 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. Also we are interested in closure properties of the resulting classes of languages and in decision problems.

Druh

D - Stať ve sborníku

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í

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 statě ve sborníku

Electronic Proceedings in Theoretical Computer Science, EPTCS

ISBN

—

ISSN

2075-2180

e-ISSN

—

Počet stran výsledku

17

Strana od-do

143-159

Název nakladatele

Open Publishing Association

Místo vydání

sydney

Místo konání akce

Debrecén

Datum konání akce

26. 8. 2022

Typ akce podle státní příslušnosti

EUR - Evropská akce

Kód UT WoS článku

—