返回Google圖書搜尋

Unambiguous Simulations of Auxiliary Pushdown Automata and Circuits

出版	TUM, Institut für Informatik, 1990
URL	http://books.google.com.hk/books?id=UypKNAAACAAJ&hl=&source=gbs_api

註釋Abstract: "In this paper time-bounded auxiliary push-down automata (AuxPDA), i.e. time and space bounded Turing machines with additional push-down store, are considered. We investigate the power of unambiguous Aux-PDA, i.e., machines that have at most one accepting computation, and ambiguity bounded AuxPDA. Recently, it was shown by Buntrock, Hemachandra, and Siefkes that space bounded Turing machines, whose computation trees have moderate ambiguity, can be efficiently simulated by by unambiguous AuxPDA with same space bound. This paper shows that such an efficient simulation is also possible for AuxPDA. The simulation incorporates no space and time penalty, unless the ambiguity is very high