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}$
- Word RAM : This a very well known model of computation.
- Read-only word RAM: Where input memory is assumed to be read-only.
- Permuted word RAM: Allow input memory to be permuted but not destroyed.
- 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?