Chomsky–Schützenberger representation theorem in terms of groups

Question

There is the Chomsky–Schützenberger representation theorem on a decomposition of context-free languages: a language $L$ over the alphabet $\Sigma$ is context-free if and only if there exists

• a matched alphabet $T\cup \overline T$
• a regular language $R$ over $T\cup \overline T$
• a homomorphism $h:(T\cup \overline T)^{*}\to \Sigma ^{*}$

such that $L=h(D_{T}\cap R)$, where $D_{T}$ is a Dyck language. $D_{T}=\{\,w\in (T\cup \overline T)^{*}\mid w{\text{ is a correctly nested sequence of parentheses}}\,\} $. $T$ contains the opening parenthesis, $\overline T$ contains the closing parenthesis, $|T| = |\overline T|$.

On the other hand, there is a set of works which describes groups with a context-free word or co-word problem:

• Holt D. F. et al. Groups with context-free co-word problem
• Muller D. E., Schupp P. E. Groups, the theory of ends, and context-free languages

Finite groups are groups with regular word and co-word problem(Anisimov, "The group languages").

Is there exist variation of the Chomsky–Schützenberger representation theorem in terms of groups composition (or in terms of word or co-word problem)?

Answer 1

There has been quite some work on weighted formal languages over semirings. So this article gives a version of the Chomsky–Schützenberger representation theorem in this setting. It is not exactly what you have asked for, but might be interesting nonetheless, if you are looking for versons in more algebraic settings.

Answer 2

I think the Wikipedia article needs to be updated (but I'm not going to do so):

The version stated concerns the one-sided Dyck language, whose transductions correspond directly to push-down automata. If you look at the Chomsky–Schützenberger article (itself referring to source articles by Chomsky and Schützenberger that I haven't chased down), you'll see Prop. 2 stated for the 2-sided Dyck language, i.e., the word problem for the free group. I think this version is more properly called the Chomsky–Schützenberger theorem, as the construction required to simulate pushdown-automata using free group automata needs some cleverness. See Kambites for a nice proof.

1. Chomsky–Schützenberger, The algebraic theory of context-free languages, 118–161, In: Computer Programming & Formal Systems (Eds: P. And Hirschberg, D. Braffort), Studies in Logic and the Foundations of Mathematics 35, North-Holland, 1963
2. Kambites, Formal languages and groups as memory, Communications in Algebra, 37:1, 193–208, 2009, DOI:10.1080/00927870802243580, arXiv:math/0601061