A Brouwerian Model of the Run-Time Memory
- 講者楊武教授 教授 (國立交通大學 資訊工程學系)
邀請人:莊庭瑞 - 時間2013-08-15 (Thu.) 14:00 ~ 16:00
- 地點資訊所新館106演講廳
摘要
Abstract:
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, discuss its properties and applications, and propose a two-counter algorithm for calculating CC(n). Our study of the Brouwerian structure is motivated by work on garbage collection.
Key Words and Phrases:
Brouwerian algebra; closed cluster; cyclic structure; depth-first search; graph theory; garbage collection; reference count; run-time memory; strongly connected component