MEDUNA, Alexander and Tomáš MASOPUST. Self-Regulating Finite Automata. Acta Cybernetica. Szeged: University Szeged, 2007, vol. 18, No 1, p. 135-153. ISSN 0324-721X.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name Self-Regulating Finite Automata
Authors MEDUNA, Alexander and Tomáš MASOPUST.
Edition Acta Cybernetica, Szeged, University Szeged, 2007, 0324-721X.
Other information
Original language English
Type of outcome Article in a journal
Field of Study 10201 Computer sciences, information science, bioinformatics
Confidentiality degree is not subject to a state or trade secret
WWW URL
Organization unit Faculty of Informatics
Keywords in English regulated automata; self-regulation; infinite hierarchies of language families; parallel right linear grammars, right linear simple matrix grammars
Tags regulated automata, self-regulation
Tags International impact, Reviewed
Changed by Changed by: doc. RNDr. Tomáš Masopust, Ph.D., DSc., učo 4030. Changed: 18/12/2008 22:12.
Abstract
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.
Abstract (in Czech)
Zavedení a studium sebeřídících konečných automatů.
PrintDisplayed: 31/7/2024 11:12