Controlled Finite Automata

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F14%3APU111904" target="_blank" >RIV/00216305:26230/14:PU111904 - isvavai.cz</a>

Výsledek na webu

<a href="http://link.springer.com/article/10.1007/s00236-014-0199-5" target="_blank" >http://link.springer.com/article/10.1007/s00236-014-0199-5</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s00236-014-0199-5" target="_blank" >10.1007/s00236-014-0199-5</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Controlled Finite Automata

Popis výsledku v původním jazyce

This paper discusses finite automata regulated by control languages over their states and transition rules. It proves that under both regulations, regular-controlled finite automata and context-free-controlled finite automata characterize the family of regular languages and the family of context-free languages, respectively. It also establishes conditions under which any state-controlled finite automaton can be turned into an equivalent transition-controlled finite automaton and vice versa. The paper also demonstrates a close relation between these automata and programmed grammars. Indeed, it proves that finite automata controlled by languages generated by propagating programmed grammars with appearance checking are computationally complete. In fact, it demonstrates that this computational completeness holds even in terms of these automata with a  reduced number of states.

Název v anglickém jazyce

Controlled Finite Automata

Popis výsledku anglicky

This paper discusses finite automata regulated by control languages over their states and transition rules. It proves that under both regulations, regular-controlled finite automata and context-free-controlled finite automata characterize the family of regular languages and the family of context-free languages, respectively. It also establishes conditions under which any state-controlled finite automaton can be turned into an equivalent transition-controlled finite automaton and vice versa. The paper also demonstrates a close relation between these automata and programmed grammars. Indeed, it proves that finite automata controlled by languages generated by propagating programmed grammars with appearance checking are computationally complete. In fact, it demonstrates that this computational completeness holds even in terms of these automata with a  reduced number of states.

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)

Rok uplatnění

2014

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

Acta Informatica

ISSN

0001-5903

e-ISSN

1432-0525

Svazek periodika

51

Číslo periodika v rámci svazku

5

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

11

Strana od-do

327-337

Kód UT WoS článku

000339103700003

EID výsledku v databázi Scopus

2-s2.0-84903900178