Conference paper

Editor list: Calude, CS; Claude, E; Dinneen, MJ

Publication year: 2004

Pages: 102-113

Journal: Lecture notes in computer science

Volume number: 3340

ISSN: 0302-9743

ISBN: 3-540-24014-4

eISSN: 1611-3349

Conference: 8th International Conference on Developments in Language Theory

Publisher: Springer

Title of series: Lecture Notes in Computer Science

Abstract: 
Input-reversal pushdown automata are pushdown automata with the additional power to reverse the unread part of the input. We show that these machines characterize the family of linear context-free indexed languages, and that k + 1 input reversals are better than k for both deterministic and nondeterministic input-reversal pushdown automata, i.e., there are languages which can be recognized by a deterministic input-reversal pushdown automaton with k + 1 input reversals but which cannot be recognized with k input reversals (deterministic or nondeterministic). In passing, input-reversal finite automata are investigated. Moreover, an inherent relation between input-reversal pushdown automata and controlled linear context-free languages are shown, leading to an alternative description of Khabbaz geometric hierarchy of languages by input-reversal iterated pushdown automata. Finally, some computational complexity problems for the investigated language families are considered.

Harvard Citation style: Bordihn, H., Holzer, M. and Kutrib, M. (2004) Input reversals and iterated pushdown automata: A new characterization of Khabbaz geometric hierarchy of languages, Lecture notes in computer science (Schriftenreihe), 3340, pp. 102-113

APA Citation style: Bordihn, H., Holzer, M., & Kutrib, M. (2004). Input reversals and iterated pushdown automata: A new characterization of Khabbaz geometric hierarchy of languages. Lecture notes in computer science (Schriftenreihe). 3340, 102-113.