J 2007

Self-Regulating Finite Automata

MEDUNA, Alexander a Tomáš MASOPUST

Základní údaje

Originální název

Self-Regulating Finite Automata

Autoři

MEDUNA, Alexander a Tomáš MASOPUST

Vydání

Acta Cybernetica, Szeged, University Szeged, 2007, 0324-721X

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Utajení

není předmětem státního či obchodního tajemství

Odkazy

Označené pro přenos do RIV

Ne

Organizační jednotka

Fakulta informatiky

Klíčová slova anglicky

regulated automata; self-regulation; infinite hierarchies of language families; parallel right linear grammars, right linear simple matrix grammars

Štítky

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 18. 12. 2008 22:12, doc. RNDr. Tomáš Masopust, Ph.D., DSc.

Anotace

ORIG CZ

V originále

This paper introduces and discusses {\em self-regulating finite automata}. In essence, these automata regulate the use of their rules by a sequence of rules applied during previous moves. A special attention is paid to {\em turns} defined as moves during which a self-regulating finite automaton starts a new self-regulating sequence of moves. Based on the number of turns, the present paper establishes two infinite hierarchies of language families resulting from two variants of these automata. In addition, it demonstrates that these hierarchies coincide with the hierarchies resulting from parallel right linear grammars and right linear simple matrix grammars, so the self-regulating finite automata can be viewed as the automaton counterparts to these grammars. Finally, this paper compares both infinite hierarchies. In addition, as an open problem area, it suggests the discussion of self-regulating pushdown automata and points out that they give rise to no infinite hierarchy analogical to the achieved hierarchies resulting from the self-regulating finite automata.

Česky

Zavedení a studium sebeřídících konečných automatů.