On undecidability results of real programming languages

Raimund Kirner, W. Zimmermann, D. Richter

Research output: Chapter in Book/Report/Conference proceedingConference contribution

79 Downloads (Pure)

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.
Original languageEnglish
Title of host publicationIn: Procs of Kolloquium Programmiersprachen und Grundlagen der Programmierung
Number of pages14
Publication statusPublished - 2009
EventKolloquium Programmiersprachen und Grundlagen der Programmierung - Vienna, United Kingdom
Duration: 1 Aug 2009 → …

Conference

ConferenceKolloquium Programmiersprachen und Grundlagen der Programmierung
Country/TerritoryUnited Kingdom
CityVienna
Period1/08/09 → …

Fingerprint

Dive into the research topics of 'On undecidability results of real programming languages'. Together they form a unique fingerprint.

Cite this