12
$\begingroup$

The Dyck language is defined as the language of balanced parenthesis expressions on the alphabet consisting of the symbols $($ and $)$. For example, $()$ and $()(()())$ are both elements of the Dyck language, but $())($ is not. There is an obvious generalisation of the Dyck language to include several different types of parentheses.

It seems to me that the first time the term "Dyck language" is used to describe this language (and its generalisation) is in [Chomsky, N.; Schützenberger, M. P. The algebraic theory of context-free languages. 1963 Computer programming and formal systems, pp. 118–161]. Furthermore, all sources online agree that the "Dyck" in question is Walther von Dyck, who introduced the notion of a group presentation in 1882.

However, in the above paper, I can only see a weak reason as to why this language is named after von Dyck. A paragraph directly following the definition reads: The Dyck Language $D_{2n}$ on the $2n$ letters $x_{\pm i} \: (1 \leq i \leq n)$ [...] is a very familiar mathematical object: if $\varphi$ is the homomorphism of the free monoid generated by $\{ x_{\pm i}\}$ onto the free group generated by the subset $\{ x_i \mid i > 0\}$ that satisfies identically $(\varphi x_i)^{-1} = \varphi x_{-i}$, then $D_{2n}$ is the kernel of $\varphi$.

This alternate characterisation is obviously related to presentations, and thus has some connection with von Dyck. However, I am uncertain whether this is the full reason as to why it is named after him. Perhaps there is an intermediate study of the Dyck language inbetween the work of von Dyck and Chomsky-Schützenberger which makes this connection stronger? Thus, my question:

Why is the "Dyck language" named after von Dyck?

Of course, the same question might as well be asked about "Dyck paths" in combinatorics, closely related to the Catalan numbers, but it seems to me quite clear that Dyck paths were named after the Dyck language.

Any thoughts would be appreciated!

$\endgroup$
6
  • 2
    $\begingroup$ I think this is a very reasonable question. $\endgroup$ Aug 25, 2020 at 16:36
  • 1
    $\begingroup$ I think because it is the word problem of the free group is often called the 2-sided Dyck language. Here you are balancing letters and inverse letters. Balancing parentheses is a 1-sided version and so sometimes called 1-suded Dyck words. $\endgroup$ Aug 25, 2020 at 17:26
  • $\begingroup$ The one-sided version with different parentheses, depending on your conventions gives the words representing 1 in the polycyclic inverse monoid. The standard 1 parentheses language is the words representing 1 in the bicyclic monoid $\endgroup$ Aug 25, 2020 at 17:30
  • $\begingroup$ @BenjaminSteinberg Yes, I agree that this what is captured by the kernel characterisation above (and of course the bicyclic connection is nice -- it was when looking at this that I stumbled across my question). But the word problem (especially as a language) is long after von Dyck; I wonder whether the only reason for naming the Dyck language/paths after him is only because he (proto)studied free groups. Or did he do any work in which he indicated that these paths are interesting to study? $\endgroup$ Aug 25, 2020 at 17:45
  • 1
    $\begingroup$ I think he is folklorically credited with solving the word problem for the free group and that is the origin of the terminology. $\endgroup$ Aug 25, 2020 at 18:04

1 Answer 1

9
$\begingroup$

Diekert and Lange, in Variationen über Walther von Dyck und Dyck-Sprachen, quote a personal communication from Chomsky that attributes the name Dyck language to Schützenberger's 1962 paper on Certain elementary families of automata, although there only the letter "D" is used.

They note the link between the parenthetical structure of Von Dyck's free groups and the push-down automata that were studied in the 1950's and formalized by Schützenberger in On context-free languages and push-down automata (1963, where the "D" is now written in full as Dyck).

$\endgroup$
1
  • $\begingroup$ Brilliant! Thank you Carlo, that's exactly the kind of thing I was looking for! $\endgroup$ Aug 25, 2020 at 22:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.