Glasser, Christian; Schmitz, Heinz The Boolean structure of dot-depth one. (English) Zbl 1013.68112 J. Autom. Lang. Comb. 6, No. 4, 437-452 (2001). Summary: By definition, the class \({\mathcal B}_1\) of dot-depth one languages is the Boolean closure of the class \({\mathcal B}_{1/2}\) of languages that can be written as finite unions of \(u_0A^+ u_1\cdots 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,\dots, 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 \({\mathcal 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 \({\mathcal 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. Cited in 8 Documents MSC: 68Q45 Formal languages and automata Keywords:dot-depth hierarchy; decidability; Boolean hierarchy PDFBibTeX XMLCite \textit{C. Glasser} and \textit{H. Schmitz}, J. Autom. Lang. Comb. 6, No. 4, 437--452 (2001; Zbl 1013.68112)