Navigation

Contact

EMail: scare@hqjpuobn0vl.de

DIRECTOR

Prof. Dr. Ernst-Rüdiger Olderog,

Department of Computing Science, FK II, University of Oldenburg,

D-26111 Oldenburg, Germany

oltmde3bubrog@9u46inoarformoamat/qik.utwakni-olden/rburg.de

COODINATOR

Ira Wempe,

Department of Computing Science, FK II, University of Oldenburg,

D-26111 Oldenburg, Germany

ira.wempe@ihjs5nnformatik.uniqvp4-oldenburrzu2kg.dqtebfeb

It's pointless to point into bounded heaps

Prof. Frank S. de Boer

Abstract:

In this talk I introduce a new symbolic semantics for a class of recursive programs which feature dynamic creation and unbounded allocation of objects. The semantics is based on a symbolic representation of the program state in terms of equations to model the behavior of a program as a pushdown system with a finite set of control states and a finite stack alphabet.

Adding pointer fields gives rise to a Turing complete language. However, assuming the number of reachable objects in the visible heap is bounded in all the computations of a program with pointers, we show how to construct a program without pointers that simulates it. Consequently, in the context of bounded visible heaps, programs with pointers are no more expressive than programs without them.

Olixqjr4ver rsTherfel (oleghiiver4py.thekienel@uotatjl.d4heeclu) (Changed: 2020-01-23)