On the space complexity of DAG computations

In this thesis we have studied some issues related to the space complexity of Directed Acyclic Graphs (DAG) computations and in particular the possibility of obtaining a reduction of the amount of memory necessary to the evaluation of a DAG using computations with multiple assessments of the same vertex rather than strictly without recalculations. In the main result of the thesis, we introduce a method to obtain a significant upper bound for the space complexity of a DAG, based on the concept of DAG-vertex separator. By further developing this result according to the divide and conquer paradigm we obtain a decomposition of the DAG through which it is possible to observe a relationship between topological characteristics of the graph and its space complexity