R. Kirner,W. Zimmermann, D. Richter:

"On Undecidability Results of Real Programming Languages";

Talk: 15. Kolloquium Programmiersprachen und Grundlagen der Programmierung (KPS 2009), Maria Taferl; 2009-10-12 - 2009-10-14; in: "15. Kolloquium Programmiersprachen und Grundlagen der Programmierung (KPS 2009)", J. Knoop, A. Prantl (ed.); Schriftenreihe des Instituts für Computersprachen, TU Wien, Bericht 2009-X-1 (2009), 141 - 154.

Often, it is argued that some problems in data-flow analysis

such as e.g. worst case execution time analysis are undecidable (because

the halting problem is) and therefore only a conservative approximation

of the desired information is possible. In this paper, we show that the

semantics for some important real programming languages - in particular

those used for programming embedded devices - can be modeled as

finite state systems or pushdown machines. This implies that the halting

problem becomes decidable and therefore invalidates popular arguments

for using conservative analysis.

Created from the Publication Database of the Vienna University of Technology.