×

The Boolean structure of dot-depth one. (English) Zbl 1013.68112

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.

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite