A Uniform Approach to the Complexity and Analysis of Succinct Systems

To my parents Gertrud and Michael vAbstract This thesis provides a unifying view on the succinctness of systems: the capability of a modeling formalism to describe the behavior of a system of exponential size using a polynomial syntax. The key theoretical contribution is the introduction of sequential circuit machines as a new universal computation model that focuses on succinctness as the central aspect. The thesis demonstrates that many well-known mod-eling formalisms such as communicating state machines, linear-time tem-poral logic, or timed automata exhibit an immediate connection to this machine model. Once a (syntactic) connection is established, many com-plexity bounds for structurally restricted sequential circuit machines can be transferred to a certain formalism in a uniform manner. As a consequence, besides a far-reaching unification of independent lines of research, we are also able to provide matching complexity bounds for various analysis prob