[Zurück]

B. Burgstaller, J. Blieberger, B. Scholz:
"On the Tree Width of Ada Programs";
Vortrag: Reliable Software Technologies - Ada-Europe, Palma de Mallorca, Spain; 14.06.2004 - 18.06.2004; in: "Lecture Notes in Computer Science - Ada-Europe", Springer-Verlag, 3063 (2004), ISBN: 3-540-22011-9; S. 78 - 90.

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.

http://dx.doi.org/10.1007/b97913

http://aleph.ub.tuwien.ac.at/F?base=tuw01&func=find-c&ccl_term=AC04968328