Grammar-Based Set-Theoretic Formalization of Emergence in Complex Systems

Abstract

As complex systems are becoming ubiquitous and are growing, especially in terms of size and interconnectivity, the study of emergence in such systems is increasingly important. Emergence can be regarded as system properties that arise from the interactions of system components, but that cannot be derived from the properties of the individual components. Despite a long history of research on complex systems, there is still a lack of consensus on the definition of emergence. A plethora of emergence definitions hinders the understanding and engineering of complex systems. This thesis proposes a grammar-based set-theoretic approach to formalize and verify the existence and extent of emergence without prior knowledge or definition of emergent properties. Our approach is based on weak emergence that is both generated and autonomous from the underlying components. In contrast to current work, our approach has two main advantages. First, in formalizing emergence, our grammar is designed to model components of diverse types, mobile components, and open systems. Second, by focusing only on system interactions of interest and feasible combinations of individual component behavior, and degree of interaction, state-space explosion is reduced. Theoretical and experimental studies using the Boids model and multi-threaded programs demonstrate the complexity of our formal approach. The Boids model has been validated up to 1,024 birds. We also present and discuss open issues in the study of emergence, and highlight potential research opportunities.