17
$\begingroup$

In the Sakarovitch's book on automata theory, it is written in the introduction to the section on rationals in the free group that the material presented therein lays "the foundation of a truly mathematical theory of context-free languages". Nevertheless, this is not made explicit, as context-free languages and pushdown automata are beyond the scope of the book.

I am aware of some connections of free groups (and especially of what Sakarovitch calls involutive monoids) to the theory of pushdown automata and context-free languages -- e.g., the Dyck language, the Shamir's theorem, etc. However, I have had a hard time finding a source in which the "truly mathematical theory of context-free languages", mentioned by Sakarovitch, is actually built up.

The closest thing I have found is the Berstel's book on transductions and context-free languages. However, at first sight it seems to me that pushdown automata are treated only marginally in this book, while the theory of rational subsets of a free group is not applied at all. Perhaps the material I am looking for has been intended for Eilenberg's Volume C, but I am not sure about that neither.

So I would like to ask for a pointer to a book, survey, or perhaps a set of papers, from which I could learn something about the Sakarovitch's "truly mathematical theory of context-free languages" and its relations to free groups and their rational subsets. Or perhaps I am looking for something that does not actually exist?

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
9
$\begingroup$

Sakarovitch's PhD thesis from 1976, titled Monoïdes syntactiques et languages algébriques (syntactic monoids and algebraic languages), revolves around this topic. At the time, this led to the definition of pointed monoids (see, e.g., his MFCS'75 paper). Around the 80's, the algebraic object of choice to study CFL's shifted to the Hotz group—Sakarovitch even has a paper on that topic in Acta. Inf. As far as I know, pointed monoids did not get the attention they deserved, although the same ideas can be found in Behle, Krebs, et al.; likewise, some recent approaches, based on more sophisticated tools, especially Stone duality, may provide a sound framework for such studies.

Another modern approach is that of Clark on the syntactic concept lattice, that I'm not familiar with.

As for the actual intentions of the author, one safe way is to ask him directly.

Improve this answer
$\endgroup$
5
$\begingroup$

In addition to the references given by Michaël Cadilhac, let me add this paper

Berstel, J.; Boasson, L. Towards an algebraic theory of context-free languages. Fund. Inform. 25 (1996), no. 3-4, 217--239.

Improve this answer
$\endgroup$

Your Answer

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

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