Journal article

MEDUNA Alexander and ZEMEK Petr. Controlled Finite Automata. Acta Informatica. 2014, vol. 51, no. 5, pp. 327-337. ISSN 0001-5903. Available from: http://link.springer.com/article/10.1007/s00236-014-0199-5
Publication language:english
Original title:Controlled Finite Automata
Title (cs):Řízené konečné automaty
Pages:327-337
Place:DE
Year:2014
URL:http://link.springer.com/article/10.1007/s00236-014-0199-5
Journal:Acta Informatica, Vol. 51, No. 5, DE
ISSN:0001-5903
Keywords
finite automata, controlled accepting, control languages, accepting power, computational completeness, reduction
Annotation
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.
BibTeX:
@ARTICLE{
   author = {Alexander Meduna and Petr Zemek},
   title = {Controlled Finite Automata},
   pages = {327--337},
   journal = {Acta Informatica},
   volume = {51},
   number = {5},
   year = {2014},
   ISSN = {0001-5903},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php?id=9893}
}

Your IPv4 address: 54.158.55.5
Switch to IPv6 connection

DNSSEC [dnssec]