中央研究院 資訊科學研究所

活動訊息

友善列印

列印可使用瀏覽器提供的(Ctrl+P)功能

A Brouwerian Model of the Run-Time Memory

:::

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