Abstract.
An iterative array (IA) is a semi-infinite array (with left boundary) of cells, where the input string is given serially to the leftmost cell. This paper presents a quadratic speedup theorem for IAs by using alternations. It is shown that for any constructible functions s(n) and t(n) such that \(t(n)\geq s(n)\geq n\), every s(n)t(n)-time deterministic IA can be simulated by an O(s(n))-space O(t(n))-time alternating IA. Therefore, every \(t^2(n)\)-space \(t^2(n)\)-time deterministic IA can be simulated by an O(t(n))-time alternating IA. This leads to a separation result: There is a language which can be accepted by an alternating IA in O(t(n)) time but not by any deterministic IA in t(n) time.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Author information
Authors and Affiliations
Additional information
Received: 9 July 2001 / 20 August 2002
An extended summary of this paper appeared in the Proc. Machines, Computations and Universality (LNCS 2055), May 23–28, 2001, 240–251. This research was partially supported by the Telecommunications Advancement Foundation.
Rights and permissions
About this article
Cite this article
Iwamoto, C., Tateishi, K., Morita, K. et al. A quadratic speedup theorem for iterative arrays. Acta Informatica 38, 847–858 (2002). https://doi.org/10.1007/s002360200092
Issue Date:
DOI: https://doi.org/10.1007/s002360200092