Konferenzpaper

Herausgeberliste: Ibarra, OH; Yen, HC

Jahr der Veröffentlichung: 2006

Seiten: 34-45

Zeitschrift: Lecture notes in computer science

Bandnummer: 4094

ISSN: 0302-9743

ISBN: 3-540-37213-X

Konferenz: 11th International Conference on Implementation and Application of Automata

Verlag: Springer

Serientitel: LECTURE NOTES IN COMPUTER SCIENCE

Abstract: 
Extended finite automata are finite state automata equipped with the additional ability to apply an operation on the currently remaining input word, depending on the current state. Hybrid extended finite automata can choose from a finite set of such operations. In this paper, five word operations are taken into consideration which always yield letter-equivalent results, namely reversal and shift operations. The computational power of those machines is investigated, locating the corresponding families of languages in the Chomsky hierarchy. Furthermore, different types of hybrid extended finite automata, defined by the set of operations they are allowed to apply, are compared with each other, demonstrating that there exist dependencies and independencies between the input manipulating operations.

Harvard-Zitierstil: Bordihn, H., Holzer, M. and Kutrib, M. (2006) Hybrid extended finite automata, Lecture notes in computer science (Schriftenreihe), 4094, pp. 34-45

APA-Zitierstil: Bordihn, H., Holzer, M., & Kutrib, M. (2006). Hybrid extended finite automata. Lecture notes in computer science (Schriftenreihe). 4094, 34-45.