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

Tyng Ruey Chuang, Benjamin Goldberg

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationProc 6 Int Conf Funct Program Lang Comput Archit
Editors Anon
PublisherPubl by ACM
Pages289-296
Number of pages8
ISBN (Print)089791595X
StatePublished - 1993
EventProceedings of the 6th International Conference on Functional Programming Languages and Computer Architecture (FPCA '93) - Copenhagen, Den
Duration: Jun 9 1993Jun 11 1993

Publication series

NameProc 6 Int Conf Funct Program Lang Comput Archit

Other

OtherProceedings of the 6th International Conference on Functional Programming Languages and Computer Architecture (FPCA '93)
CityCopenhagen, Den
Period6/9/936/11/93

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'Real-time deques, multihead Turing machines, and purely functional programming'. Together they form a unique fingerprint.

Cite this