A Brouwerian model of the run-time memory

Wuu Yang*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

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 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.

Original languageEnglish
Pages (from-to)2103-2124
Number of pages22
JournalJournal of Information Science and Engineering
Volume31
Issue number6
DOIs
StatePublished - 1 Nov 2015

Keywords

  • Brouwerian algebra
  • Closed cluster
  • Cyclic structure
  • Depth-first search
  • Garbage collection
  • Graph theory
  • Reference count
  • Run-time memory
  • Strongly connected component

Fingerprint Dive into the research topics of 'A Brouwerian model of the run-time memory'. Together they form a unique fingerprint.

Cite this