標題: A Brouwerian Model of the Run-Time Memory
作者: Yang, Wuu
資訊工程學系
Department of Computer Science
關鍵字: Brouwerian algebra;closed cluster;cyclic structure;depth-first search;graph theory;garbage collection;reference count;run-time memory;strongly connected component
公開日期: 1-Nov-2015
摘要: 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.
URI: http://hdl.handle.net/11536/129405
ISSN: 1016-2364
期刊: JOURNAL OF INFORMATION SCIENCE AND ENGINEERING
Volume: 31
起始頁: 2103
結束頁: 2124
Appears in Collections:Articles