Proceedings of the IFSR Conversation 2010, Pernegg, Austria
Discussion Paper (Team 4): Classifying Problems according to their Design Complexity
Gerhard Chroust
M. Lehman proposed a hierarchical classification of software systems (Lehman, 1980, 1985) based on
the complexity of their design. It was later extended by Kopetz (1997) and Chroust (2008):
S-System (Specification system): S-type systems address problems that are formally defined and specified. A solution has to fulfil the specifications with no freedom. A typical example is the allocation of number plates to cars, where the rules are clearly stated (uniqueness, legal type and sequence of symbols, etc.)
P-System (Problem system): These systems should solve a problem that is not well-understood or precisely stated, and usually includes some heuristics. Any solution which solves (at least largely) the problem is acceptable. A typical example is the simulation of traffic. The system fulfils its purpose if the predicted traffic flow corresponds to reality.
E-System (Environment system): These systems which interact with the real world (e.g. industrial automation and control systems, embedded systems, etc.) and are strongly affected by the environment. A typical example is the control of traffic lights etc. according to the expected traffic forecasted by the simulation. Drivers very soon at least believe to be able to beat the system by choosing different routes or changing their behaviour, respectively.
W-Systems (Wicked systems): These systems have the properties of E-Systems with additional disturbing properties: they are large and complex, the problem cannot be expressed in a well-defined form, isolating the problem from the environment causes the problem to collapse or to disappear, no termination rule exists; one can always find a still better solution. Additionally the problem cannot be specified without some concept of its solution (Kopetz, 1997; Chroust-04). An example for a wicked system is the use of the outcome of the traffic simulation (a P-system) for suggesting (or enforcing) routing of cars in order to reduce both route length and fuel consumption.
Chroust, G. The empty chair – Uncertain Futures and Systemic Dichotomies, Systems Research and Behavioral Science, vol. 21 (2004), pp. 227–236.
Chroust, G., E. Schoitsch Choosing Basic Architectural Alternatives in: TIAKO, P. F., (ed.): Designing Software-Intensive Systems: Methods and Principles, pp. 161–221 Idea Group Inc., Hershey, USA 2008.
Kopetz, H. Real-time Systems – Design Principles for Distributed Embedded Applications Kluwer Academic Publishers, Boston/Dordrecht/London 1997.
Lehman, M.M. Programs, Life Cycles, and Laws of Software Evolution Proc. IEEE, 68:9:1060–1076.
Lehman, M.M. Belady L.A., (ed.) Program Evolution – Processes of Software Change APIC Studies in Data Proc. No. 27, Academic Press.
