Hierarchical partitioning (really) helps - from flat structures to hierarchies.

Oliver Möller
Department of Computer Science
University of Aarhus

Complex systems are better understood, if they are organized according to some structure. Usually this is done in terms of a hierarchy that decomposes the system into successively smaller components.

In this seminar talk we address the problem of constructing a good hierarchy over some components, which are connected in a general way. We propose a (polynomial time) greedy-style algorithm that groups together according to some local heuristic function. Due to the high combinatorial and computational complexity, we have to sacrifice optimality here.

We report on application of this algorithm in the area of formal verification, where it serves as a preprocessor for a temporal scaling technique called `next' heuristic. The latter is included in a recent version of the Mocha model checking tool. We validate the adequacy of the computed hierarchies in terms of experimental run-time data.

Online References: Mocha:
my home page:

ASTEC seminar
October 17th September, 13:15

Place: Information technology, Uppsala University
Room: 1510
Time: 13.15

Room 1510 is in Building 1, Floor 5, room 10 (in the southern part of the building).

Help on how get here and MIC campus drawing.

There will be an extended period for discussions after the seminar.

Speakers are encouraged to give an short (5 min) introduction to the subject at the begining of the talk.
Listeners are excused if they have to leave after 1 hour.

Updated 05-Oct-2000 08:56 by Roland Grönroos
e-mail: info -at-    Location: