Over the past decade, it became apparent that the conceptual way of analyzing
problems through computer-science techniques can be considered as a general approach to
analysis, design, and problem solving, known as computational thinking [1]}, [2]}.
A key element of this approach is the taming of complexity by decomposing a complex problem
into simpler problems. Quoting Wing [1]}: “Computational thinking is using abstraction and
decomposition when attacking a large complex task or designing a large complex system.”
While abstraction helps to tame complexity by simplifying away irrelevant details of a complex
problem, decomposition helps to tame complexity by breaking down complex problems into simpler ones.
In fact, decomposition is a generic project-management technique: project managers quite often face
challenges that require decomposition – a large project that is divided among team members to make
the problem less daunting and easier to solve as a set of smaller tasks, where team members work on tasks
that are in their specific fields of expertise. As computer scientists and engineers, the concept
of decomposition is prevalent in the design of algorithms, in software construction, in hardware design,
and so on.
For example, a classical paper in software engineering studies criteria to be used in decomposing systems
into modules [4]}.
Yet, in spite of the centrality of the concept of decomposition in computational thinking,
it has yet to be studied formally in a general theoretical setting (see related work).
Such a study is the focus of this work.
