On the tree width of ada programs

Bernd Burgstaller; Johann Blieberger; Bernhard Scholz

doi:10.1007/978-3-540-24841-5_6

On the tree width of ada programs

Bernd Burgstaller, Johann Blieberger, Bernhard Scholz

College of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

12 Citations (Scopus)

Abstract

The tree width of a graph G measures how close G is to being a tree or a series-parallel graph. Many well-known problems that are otherwise NP-complete can be solved efficiently if the underlying graph structure is restricted to one of fixed tree width. In this paper we prove that the tree width of goto-free Ada programs without labeled loops is ≤ 6. In addition we show that both the use of gotos and the use of labeled loops can result in unbounded tree widths of Ada programs. The latter result suggested to study the tree width of actual Ada programs. We implemented a tool capable of calculating tight upper bounds of the tree width of a given Ada program efficiently. The results show that most existing Ada code has small tree width and thus allows efficient automatic static analysis for many well-known problems and – as a by-product – most Ada programs are very close to series-parallel programs.

Original language	English
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Editors	Alfred Strohmeier, Albert Llamosi
Publisher	Springer Verlag
Pages	78-90
Number of pages	13
ISBN (Print)	3540220119
DOIs	https://doi.org/10.1007/978-3-540-24841-5_6
Publication status	Published - 2004
Event	9th Ada-Europe International Conference on Reliable Software Technologies, Ada-Europe 2004 - Palma de Mallorca, Spain Duration: 2004 Jun 14 → 2004 Jun 18

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	3063
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	9th Ada-Europe International Conference on Reliable Software Technologies, Ada-Europe 2004
Country/Territory	Spain
City	Palma de Mallorca
Period	04/6/14 → 04/6/18

Bibliographical note

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2004.

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-540-24841-5_6

Cite this

Burgstaller, B., Blieberger, J., & Scholz, B. (2004). On the tree width of ada programs. In A. Strohmeier, & A. Llamosi (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 78-90). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3063). Springer Verlag. https://doi.org/10.1007/978-3-540-24841-5_6

Burgstaller, Bernd ; Blieberger, Johann ; Scholz, Bernhard. / On the tree width of ada programs. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). editor / Alfred Strohmeier ; Albert Llamosi. Springer Verlag, 2004. pp. 78-90 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{7035ee24891a4f7aa5fa916712f603fb,

title = "On the tree width of ada programs",

abstract = "The tree width of a graph G measures how close G is to being a tree or a series-parallel graph. Many well-known problems that are otherwise NP-complete can be solved efficiently if the underlying graph structure is restricted to one of fixed tree width. In this paper we prove that the tree width of goto-free Ada programs without labeled loops is ≤ 6. In addition we show that both the use of gotos and the use of labeled loops can result in unbounded tree widths of Ada programs. The latter result suggested to study the tree width of actual Ada programs. We implemented a tool capable of calculating tight upper bounds of the tree width of a given Ada program efficiently. The results show that most existing Ada code has small tree width and thus allows efficient automatic static analysis for many well-known problems and – as a by-product – most Ada programs are very close to series-parallel programs.",

author = "Bernd Burgstaller and Johann Blieberger and Bernhard Scholz",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2004.; 9th Ada-Europe International Conference on Reliable Software Technologies, Ada-Europe 2004 ; Conference date: 14-06-2004 Through 18-06-2004",

year = "2004",

doi = "10.1007/978-3-540-24841-5_6",

language = "English",

isbn = "3540220119",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "78--90",

editor = "Alfred Strohmeier and Albert Llamosi",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

address = "Germany",

}

Burgstaller, B, Blieberger, J & Scholz, B 2004, On the tree width of ada programs. in A Strohmeier & A Llamosi (eds), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3063, Springer Verlag, pp. 78-90, 9th Ada-Europe International Conference on Reliable Software Technologies, Ada-Europe 2004, Palma de Mallorca, Spain, 04/6/14. https://doi.org/10.1007/978-3-540-24841-5_6

On the tree width of ada programs. / Burgstaller, Bernd; Blieberger, Johann; Scholz, Bernhard.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). ed. / Alfred Strohmeier; Albert Llamosi. Springer Verlag, 2004. p. 78-90 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3063).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - On the tree width of ada programs

AU - Burgstaller, Bernd

AU - Blieberger, Johann

AU - Scholz, Bernhard

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 2004.

PY - 2004

Y1 - 2004

N2 - The tree width of a graph G measures how close G is to being a tree or a series-parallel graph. Many well-known problems that are otherwise NP-complete can be solved efficiently if the underlying graph structure is restricted to one of fixed tree width. In this paper we prove that the tree width of goto-free Ada programs without labeled loops is ≤ 6. In addition we show that both the use of gotos and the use of labeled loops can result in unbounded tree widths of Ada programs. The latter result suggested to study the tree width of actual Ada programs. We implemented a tool capable of calculating tight upper bounds of the tree width of a given Ada program efficiently. The results show that most existing Ada code has small tree width and thus allows efficient automatic static analysis for many well-known problems and – as a by-product – most Ada programs are very close to series-parallel programs.

AB - The tree width of a graph G measures how close G is to being a tree or a series-parallel graph. Many well-known problems that are otherwise NP-complete can be solved efficiently if the underlying graph structure is restricted to one of fixed tree width. In this paper we prove that the tree width of goto-free Ada programs without labeled loops is ≤ 6. In addition we show that both the use of gotos and the use of labeled loops can result in unbounded tree widths of Ada programs. The latter result suggested to study the tree width of actual Ada programs. We implemented a tool capable of calculating tight upper bounds of the tree width of a given Ada program efficiently. The results show that most existing Ada code has small tree width and thus allows efficient automatic static analysis for many well-known problems and – as a by-product – most Ada programs are very close to series-parallel programs.

UR - http://www.scopus.com/inward/record.url?scp=84958751679&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84958751679&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-24841-5_6

DO - 10.1007/978-3-540-24841-5_6

M3 - Conference contribution

AN - SCOPUS:84958751679

SN - 3540220119

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 78

EP - 90

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

A2 - Strohmeier, Alfred

A2 - Llamosi, Albert

PB - Springer Verlag

T2 - 9th Ada-Europe International Conference on Reliable Software Technologies, Ada-Europe 2004

Y2 - 14 June 2004 through 18 June 2004

ER -

Burgstaller B, Blieberger J, Scholz B. On the tree width of ada programs. In Strohmeier A, Llamosi A, editors, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Verlag. 2004. p. 78-90. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-24841-5_6

On the tree width of ada programs

Abstract

Publication series

Other

Bibliographical note

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this