Hardest languages for conjunctive and Boolean grammars (Q1740643)

A language \(L_0\) is said to be the hardest language for a class of languages \(\mathscr{L}\) if \(L_0\) is in \(\mathscr{L}\) and all \(L\) in \(\mathscr{L}\) can be described as \(L = h_L^{-1}(L_0)\) or \(L = h_L^{-1}(L_0 \cup \{\varepsilon\})\) for some homomorphism \(h_L\). By a celebrated result of \textit{S. A. Greibach} [SIAM J. Comput. 2, No. 4, 304--310 (1973; Zbl 0278.68073)], there exists a hardest context-free language. However, not all classes of languages admit a language that is hardest in this sense, a prominent example being provided by the class of all rational languages [\textit{K. Čulík II} and \textit{H. A. Maurer}, RAIRO, Inf. Théor. 13, No. 3, 241--250 (1979; Zbl 0432.68052)]. The author proves existence of hardest languages for classes of languages generated by two types of generalised context-free grammars: by conjunctive grammars [\textit{A. Okhotin}, J. Autom. Lang. Comb. 6, No. 4, 519--535 (2001, Zbl 1004.68082)] and by Boolean grammars [\textit{A. Okhotin}, Inf. Comput. 194, No. 1, 19--48 (Zbl 1073.68037)]. On the other hand, he proves a negative result for subclasses of linear languages by which no class of linear languages containing all \(\mathrm{LL}(1)\)-linear languages admits a hardest language.