From Parikh's Theorem to Many-Sorted Spectra
Johann A. Makowsky · 2010
Abstract. We discuss a generalization of Parikh’s Theorem for contextfree languages to classes of many-sorted relational structures which are both definable in Monadic Second Order Logic and which are of bounded patch-width. Patch-width is a generalization of both tree-width and clique-width. This gives a powerful unifying tool to prove that certain classes of graphs are of unbounded width. For R. Parikh, at the occasion of his 70th birthday 1 Generalizing Parikh’s Theorem R. Parikh’s celebrated theorem, first proved in [Par66], counts the number of occurrences of letters in words of a context-free languages L over an alphabet of k letters. For a given word w, the numbers of these occurrences is denoted by a vector n(w) ∈ N k, and the theorem states Theorem 1 (Parikh 1966). For a context-free language L, the set Par(L) = {n(w) ∈ N k: w ∈ L} is semi-linear. A set X ⊆ Ns is linear in Ns iff there is vector ā ∈ Ns and a matrix M ∈ Ns×r such that X = Aā, M ¯ = { ¯b ∈ Ns: there is ū ∈ Nr with ¯b = ā + M · ū}. Singletons are linear sets with M = 0. If M ̸ = 0 the series is nontrivial. X ⊆ Ns is semi-linear in Ns iff X is a finite union of linear sets Ai ⊆ Ns. For s = 1 the semi-linear sets are exactly the ultimately periodic sets. The terminology is from [Par66], and has since become standard terminology in formal language theory. Several alternative proofs of Parikh’s Theorem have appeared since. D. Pilling [Pil73] put it into a more algebraic form, and more recently, L. Aceto, Z. Esik and A. Ingolfsdottir [AÉI02] showed that it depends only on a few equational properties of least pre-fixed points. B. Courcelle [Cou95]. has generalized Theorem 1 further to certain graph grammars, and relational structures which are