The memory that stores the input is called the input memory. The memory that an algorithm additionally occupies during the computation is called the working memory.

$\textit{Model of Computations}$

  1. Word RAM : This a very well known model of computation.
  2. Read-only word RAM: Where input memory is assumed to be read-only.
  3. Permuted word RAM: Allow input memory to be permuted but not destroyed.
  4. Restore model: This is a variant of permuted word RAM model, where the input memory is allowed to be modified during the process of answering a query, but it has to be restored to its original state afterward.

I know that why word RAM is the interesting model of computation in many cases but I don't have any idea what is the motivation behind studying problems in 3 and 4. Let us take the example of DFS(Depth-first Search). I know that the problem has been studied in word RAM and I also know about the space complexity of it in that model. I recently come across one paper in which DFS (see this) has been studied in 4th model of computation. The result is that DFS and BFS in place memory in linear time.

Question: What is the motivation behind restore model of computation?


The restore model is semantically identical to the read-only model. Both models are natural since you expect operations on objects to not alter them. For example, imagine running a query on a database. You don't want the query to modify the database, but you might not mind if the database is temporarily changed while running the query, as long as it is restored to its original state in the end.

(In fact, in this particular you might care, for many reasons: perhaps several processes access the database in parallel; or perhaps you are worried that a failure will stop the process in the model, thus leaving the database in a modified state. These are reasons why you'd sometimes prefer the read-only model.)

The restore model is more powerful than the read-only model, in the sense that it potentially requires less auxiliary memory. In recent times, this model is known as catalytic computation. See for example Koucký's expository article, which provides further motivations for this model.

  • $\begingroup$ That’s a different question. $\endgroup$ – Yuval Filmus Jan 29 at 8:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.