Summary: The purpose of the paper is to give an introductory survey of the main aspects and results regarding the relative succinctness of different representations of languages, such as finite automata, regular expressions, pushdown automata and variants thereof, context-free grammars, and descroptional systems from a more abstract perspective. Basic properties of these descriptiomal systems and their size measures are addressed. The tradeoffs between different representations are either bounded by some recursive function, or reveal the phenomenon that the gain in economy of description can be arbitrary. In the latter case there is no recursive function serving as upper bound. We discuss developments relevant to the descriptional complexity of formal systems. The results presented are not proved but we merely draw attention to the big picture and some of the main ideas involved.
For the entire collection see [Zbl 1207.68011].