A Brouwerian Model of the Run-Time Memory

作者：Yang Wuu^*

来源：Journal of Information Science and Engineering, 2015, 31(6): 2103-2124.

• Brouwerian algebra
• closed cluster
• cyclic structure
• depth-first search
• graph theory
• garbage collection
• reference count
• run-time memory
• strongly connected component

The run-time memory of a program may be described with a directed graph in which nodes represent chunks of memory and edges represent references. We define a closed cluster induced by a node n, denoted as CC(n), as the largest set of nodes that are reachable from n but are unreachable from nodes outside the closed cluster. Based on closed clusters, there is a Brouwerian structure under the run-time memory. We present the Brouwerian model and discuss its properties, transformations, and applications. We also propose a two-counter algorithm for calculating CC(n). The two-counter algorithm is never slower than a traditional one-counter algorithm. Our study of the Brouwerian structure is motivated by work on garbage collection.

• 出版日期2015-11