Advertisement
Published in:
2011 | OriginalPaper | Chapter
Gaining Power by Input Operations: Finite Automata and Beyond
Authors : Markus Holzer, Martin Kutrib
Published in: Implementation and Application of Automata
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We summarize results on extended finite automata, which are basically finite state machines with the additional ability to manipulate the still unread part of the input. Well-known manipulation functions are reversal, left-revolving, right-revolving, and circular interchanging, or even biologically motivated functions as hairpin inversion. We mainly focus on the computational power of these machines and on the closure properties by standard formal language operations of the induced language families. Moreover, we also discuss several generalizations of this concept, the natural generalization to hybrid extended finite automata, which allows several input manipulation functions, and in particular, extended pushdown automata, which lead to an alternative characterization of Khabbaz hierarchy of languages. We do not prove these results but we merely draw attention to the big picture, some of the main ideas involved, and open problems for further research.