University of Hertfordshire

By the same authors

On undecidability results of real programming languages

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


  • 905604

    Accepted author manuscript, 264 KB, PDF document

View graph of relations
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 → …


ConferenceKolloquium Programmiersprachen und Grundlagen der Programmierung
CountryUnited Kingdom
Period1/08/09 → …


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 article can be found at : Copyright Institut fur Technische Informatik

ID: 333110