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

<p>Berstel, J.; Boasson, L. <a href="http://www-igm.univ-mlv.fr/~berstel/Articles/1996AlgebraicTheory.pdf" rel="noreferrer">Towards an algebraic theory of context-free languages</a>. <em>Fund. Inform.</em> <strong>25</strong> (1996), no. 3-4, 217--239. </p>

CC BY-SA 3.0
2016-11-28T13:33:38.447Z
2016-11-28T13:33:38.447Z
J.-E. Pin
<p>Sakarovitch's PhD thesis from 1976, titled <em>Monoïdes syntactiques et languages algébriques</em> (syntactic monoids and algebraic languages), revolves around this topic.  At the time, this led to the definition of <em>pointed monoids</em> (see, e.g., his <a href="http://link.springer.com/chapter/10.1007%2F3-540-07854-1_222" rel="noreferrer" title="MFCS paper">MFCS'75 paper</a>).  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 <a href="http://link.springer.com/article/10.1007%2FBF00625283" rel="noreferrer">in Acta. Inf.</a>  As far as I know, pointed monoids did not get the attention they deserved, although the same ideas can be found in <a href="http://eccc.hpi-web.de/report/2011/035/download/" rel="noreferrer">Behle, Krebs, et al.</a>; likewise, some recent approaches, based on more sophisticated tools, especially Stone duality, may provide a sound framework for such studies.  </p>

<p>Another modern approach is that of Clark on <a href="https://pdfs.semanticscholar.org/5895/38e11d95398174f8014a9f566a46f3c49692.pdf" rel="noreferrer">the syntactic concept lattice</a>, that I'm not familiar with.</p>

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

CC BY-SA 3.0
2016-11-19T00:33:32.273Z
2016-11-19T00:33:32.273Z
Michaël Cadilhac
<p>In the <a href="http://www.cambridge.org/de/academic/subjects/mathematics/logic-categories-and-sets/elements-automata-theory?format=HB&amp;isbn=9780521844253" rel="noreferrer">Sakarovitch's book</a> on automata theory, it is written in the introduction to the section on <em>rationals in the free group</em> 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.</p>

<p>I am aware of some connections of free groups (and especially of what Sakarovitch calls <em>involutive monoids</em>) 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. </p>

<p>The closest thing I have found is the <a href="http://www-igm.univ-mlv.fr/~berstel/LivreTransductions/LivreTransductions.html" rel="noreferrer">Berstel's book</a> 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.</p>

<p>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?</p>

<context-free><automata-theory><reference-request>
A reference for a "more algebraic" approach to pushdown automata and CFLs?
Jára Cimrman
# A reference for a "more algebraic" approach to pushdown automata and CFLs?

(Asked by: username_0 on 2016-11-10)

In the [Sakarovitch's book](http://www.cambridge.org/de/academic/subjects/mathematics/logic-categories-and-sets/elements-automata-theory?format=HB&isbn=9780521844253) 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](http://www-igm.univ-mlv.fr/~berstel/LivreTransductions/LivreTransductions.html) 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?

**Tags:** context-free, automata-theory, reference-request

---

## 2 answers

### Answer by username_2 on 2016-11-19. Score: 9 | Accepted answer

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](http://link.springer.com/chapter/10.1007%2F3-540-07854-1_222 "MFCS 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.](http://link.springer.com/article/10.1007%2FBF00625283) 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.](http://eccc.hpi-web.de/report/2011/035/download/); 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](https://pdfs.semanticscholar.org/5895/38e11d95398174f8014a9f566a46f3c49692.pdf), that I'm not familiar with.

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


---

### Answer by username_1 on 2016-11-28. Score: 5

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](http://www-igm.univ-mlv.fr/~berstel/Articles/1996AlgebraicTheory.pdf). *Fund. Inform.* **25** (1996), no. 3-4, 217--239.


---

