12

I've been looking for the work on persistent real-time catenable deques. There are various approaches that have logarithmic complexities for concatenation of deques, and some that have amortized constant-time implementation, but much fewer real-time (non-amortized) deques with constant-time concatenation.

The well-known real-time catenable deque is the one described in the 1999 article by Haim Kaplan and Robert Tarjan, Purely Functional, Real-Time Deques with Catenation. However, both the wikipedia page on deques and this fantastic StackOverflow answer mention more recent work (apparently 2003) by Robert Tarjan and Radu Mihaescu, that is supposedly simpler.

Does anyone have a link to a publication by Robert Tarjan and Mihaescu on this work? The only thing I could find while browsing the web is a .doc document, apparently a part of some course notes, and that format is neither comfortable to read nor maybe reliable enough to base an implementation on.

Some web pages refer to the second author as "Mihaesau", which seems to be a mistake. I found a DBLP list of publications, more recent and not mentioning catenable queues, and a meager webpage, with no links to a publication section.

Community
  • 1
  • 1
gasche
  • 31,259
  • 3
  • 78
  • 100
  • 2
    Mihaescu is the proper spelling. I tracked him down through LinkedIn at one point. – Edward Kmett Feb 12 '15 at 00:29
  • Thanks for the clarification, I updated my question accordingly (and indeed that sounds like a more proper spelling, I don't know what I was thinking). – gasche Feb 14 '15 at 09:32
  • I can't seem to find a paper mentioned in the linked SO answer that matches the description in this question. Poking around, I came across the [Scandinavian Workshop on Algorithm Theory](http://www.csc.kth.se/tcs/SWAT98), sporting a contribution "Simple Confluently Persistent Catenable Lists." by Haim Kaplan, Chris Okasaki, Robert E. Tarjan. – greybeard Feb 14 '15 at 15:59
  • https://www.linkedin.com/pub/radu-mihaescu/7/119/97a – Edward Kmett Feb 15 '15 at 04:35
  • @gasche, what you were thinking is that the name is spelled two different ways in the paper in question, leading to confusion all around. – dfeuer Feb 25 '15 at 17:51
  • According to [this comment by ekmett](https://www.reddit.com/r/haskell/comments/a4wk1i/seminal_works_after_purely_functional_data/ebm30ra/), this is an implementation of Mihaescu-Tarjan deques: https://github.com/alang9/deque/blob/master/Data/Deque/Cat.hs – sjakobi Dec 13 '19 at 15:42

1 Answers1

6

A great answer on CStheory.SE links to that .doc and states that

So apparently there's no conference or journal description of the data structure and you've already got the definitive reference, until now at least. Note that the course is question is given by Tarjan. You could inquire by email about this data structure.

Community
  • 1
  • 1
Fred Foo
  • 355,277
  • 75
  • 744
  • 836
  • 2
    (For the record, I sent an email to Tarjan in 2013 about this, and never got an answer back.) – gasche Jun 15 '17 at 00:16