2024/02/15 by Thomas Place, Place, Thomas, Marc Zeitoun +1 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #Cellular Automata and Applications #DNA and Biological Computing #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2402.10080
openalex publication_date 2024/02/15 · openalex created_date 2024/02/18 · openalex updated_date 2026/07/28
We study the class of star-free languages. A long-standing goal is to classify them by the complexity of their descriptions. The most influential research effort involves concatenation hierarchies, which measure alternations between ``complement'' and ``union plus concatenation''. We explore alternative hierarchies that also stratify star-free languages. They are built with an operator C↦ TL(C). From an input class C, it produces a larger one TL(C), consisting of all languages definable in a variant of unary temporal logic, where temporal modalities depend on C. Level n in the navigational hierarchy of basis C is constructed by applying this operator n times to C. As bases G, we focus on group languages and natural extensions thereof, denoted G+. We prove that the navigational hierarchies of bases G and G+ are strictly intertwined and conduct a thorough investigation of their relationships with concatenation hierarchies. We also look at two problems on classes of languages: membership (decide if a language is in the class) and separation (decide, for two languages L1,L2, if there is a language K in the class with L1⊆ K and L2∩ K=∅). We prove that if separation is decidable for G, then so is membership for level two in the navigational hierarchies of bases G and G+. We take a look at the trivial class ST=\∅,A^*\. For the bases ST and ST+, the levels one are standard variants of unary temporal logic. The levels two correspond to variants of two-variable logic, investigated recently by Krebs, Lodaya, Pandya and Straubing. We solve one of their conjectures. We also prove that for these two bases, level two has decidable separation. Combined with earlier results on the operator C↦ TL(C), this implies that level three has decidable membership.