Veröffentlichung im Rahmen des 15. Kolloquium Programmiersprachen und Grundlagen der Programmierung (KPS'09) in Maria Taferl.

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

Download: kps09z.pdf