Conference paper

Editor list: Ibarra, OH; Yen, HC

Publication year: 2006

Pages: 34-45

Journal: Lecture notes in computer science

Volume number: 4094

ISSN: 0302-9743

ISBN: 3-540-37213-X

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

Publisher: Springer

Title of series: 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 Citation style: Bordihn, H., Holzer, M. and Kutrib, M. (2006) Hybrid extended finite automata, Lecture notes in computer science (Schriftenreihe), 4094, pp. 34-45

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