[Back]

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.