TY - GEN

T1 - Real-time deques, multihead Turing machines, and purely functional programming

AU - Chuang, Tyng Ruey

AU - Goldberg, Benjamin

PY - 1993

Y1 - 1993

N2 - We answer the following question: Can a deque (double-ended queue) be implemented in a purely functional language such that each push or pop operation on either end of a queue is accomplished in O(1) time in the worst case? The answer is yes, thus solving a problem posted by Gajewska and Tarjan and by Ponder, McGeer, and Ng, and refining results of Sarnak and Hoogerwoord. We term such a deque real-time, since its constant worst-case behavior might be useful in real time programs (assuming real-time garbage collection, etc.) Furthermore, we show that no restriction of the functional language is necessary, and that push and pop operations on previous versions of a deque can also be achieved in constant time. We present a purely functional implementation of real-time deques and its complexity analysis. We then show that the implementation has some interesting implications, and can be used to give a real-time simulation of a multihead Turing machine in a purely functional language.

AB - We answer the following question: Can a deque (double-ended queue) be implemented in a purely functional language such that each push or pop operation on either end of a queue is accomplished in O(1) time in the worst case? The answer is yes, thus solving a problem posted by Gajewska and Tarjan and by Ponder, McGeer, and Ng, and refining results of Sarnak and Hoogerwoord. We term such a deque real-time, since its constant worst-case behavior might be useful in real time programs (assuming real-time garbage collection, etc.) Furthermore, we show that no restriction of the functional language is necessary, and that push and pop operations on previous versions of a deque can also be achieved in constant time. We present a purely functional implementation of real-time deques and its complexity analysis. We then show that the implementation has some interesting implications, and can be used to give a real-time simulation of a multihead Turing machine in a purely functional language.

UR - http://www.scopus.com/inward/record.url?scp=0027870617&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0027870617&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0027870617

SN - 089791595X

T3 - Proc 6 Int Conf Funct Program Lang Comput Archit

SP - 289

EP - 296

BT - Proc 6 Int Conf Funct Program Lang Comput Archit

A2 - Anon, null

PB - Publ by ACM

T2 - Proceedings of the 6th International Conference on Functional Programming Languages and Computer Architecture (FPCA '93)

Y2 - 9 June 1993 through 11 June 1993

ER -