The Boolean Structure of Dot-Depth One
Christian Glaßer, Heinz Schmitz · Universitätsbibliothek Gießen · 2001
By definition, the class $B_1$ of dot-depth one languages is the Boolean closure of the class $B_{1/2}$ languages that can be written as finite unions of $u_0A^+u_1\ldots A^+u_n$, where $u_i\in A^*$. So dot-depth one languages can be described by Boolean combinations of patterns $(u_0,u_1,\ldots,u_n)$ in words which captures locally testable and piecewise testable properties. From a descriptional complexity point of view, the lengths of the $u_i$ reflect sequential aSpects, while the Boolean operations measure combinatorial complexity. We prove that the Boolean hierarchy over $B_{1/2}$ is decidable and strict, which has consequences in first-order logic and complexity theory. Moreover, we effectively characterize the fine structure of $B_1$ w.r.t. the mentioned sequential and combinatorial measures. This allows the exact location of a given language in this two-dimensional landscape in a computable way.