On the descriptional and algorithmic complexity of regular languages

Hermann Gruber addresses basic questions in formal language theory, regarding the succinctness of description of languages by means of finite automata and regular expressions. These questions are studied from two different viewpoints. The first is descriptional complexity, which amounts to comparing the sizes of minimal descriptions. The second viewpoint is algorithmic complexity, which leads to efficiently finding such small descriptions. This monograph guidelines the reader through current research in the field and provides original solutions to several challenging research problems, including a classical open question dating back to the 1970s. The author uses a variety of proof methods, which are a blend of formal language theory, extremal combinatorics, communication complexity, circuit lower bounds, as well as the structure theory of graphs and digraphs. The book addresses researchers and professionals interested in discrete mathematics and theoretical computer science, especially automata theory.