Characterization and complexity results on jumping finite automata

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F17%3A10366161" target="_blank" >RIV/00216208:11320/17:10366161 - isvavai.cz</a>

Výsledek na webu

<a href="https://www.sciencedirect.com/science/article/pii/S0304397516303206?via%3Dihub" target="_blank" >https://www.sciencedirect.com/science/article/pii/S0304397516303206?via%3Dihub</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.tcs.2016.07.006" target="_blank" >10.1016/j.tcs.2016.07.006</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Characterization and complexity results on jumping finite automata

Popis výsledku v původním jazyce

In a jumping finite automaton, the input head can jump to an arbitrary position within the remaining input after reading and consuming a symbol. We characterize the corresponding class of languages in terms of special shuffle expressions and survey other equivalent notions from the existing literature. Moreover, we present several results concerning computational hardness and algorithms for parsing and other basic tasks concerning jumping finite automata.

Název v anglickém jazyce

Characterization and complexity results on jumping finite automata

Popis výsledku anglicky

In a jumping finite automaton, the input head can jump to an arbitrary position within the remaining input after reading and consuming a symbol. We characterize the corresponding class of languages in terms of special shuffle expressions and survey other equivalent notions from the existing literature. Moreover, we present several results concerning computational hardness and algorithms for parsing and other basic tasks concerning jumping finite automata.

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

<a href="/cs/project/GA14-10799S" target="_blank" >GA14-10799S: Hyperkrychlové, grafové a hypergrafové struktury</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2017

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

Theoretical Computer Science

ISSN

0304-3975

e-ISSN

—

Svazek periodika

2017

Číslo periodika v rámci svazku

679

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

22

Strana od-do

31-52

Kód UT WoS článku

000403125700004

EID výsledku v databázi Scopus

2-s2.0-84994193589