Friday, October 4, 2013

Contextual grammars and term-labeled trees

I've recently discovered the work of Solomon Marcus, a brilliant mathematician who's been publishing in mathematical linguistics since the 1950s.  He worked to develop "contextual grammars," which derive from the American Structuralist ideas that the "set of contexts" determined by a word in a given language is an important characteristic of the word, perhaps the most important. In a survey paper that appeared in the Handbook of Formal Languages (Rozenberg and Salomaa 1997), Marcus explains how the sets of contexts determined by the words in a language and the sets of words appearing in the contexts are related by a Galois connection.  He cites Sestier (1960) for first showing this.

My problem with this whole framework is that the contexts are defined as string contexts only--the strings that occur before and after a word in a sentence form the context.  I have worked to get beyond this string-based model of language syntax.  In my own work I proposed term-labeled trees, which are sentences provided with an immediate constituent analysis (a bare tree) together with a semantic term label, usually a lambda term.  Then I proposed, ignorant of contextual grammars at the time, the notion of a term-labeled tree context.  This is the term-labeled sentence tree with two holes in it, corresponding to the locations of the meaning term and the linked syntactic item (possibly a word, maybe a subtree) that would fill the context. 

Drawing on the result of Sestier, it appears that in a term-labeled tree language the term-labeled tree contexts are still related to the words and other possible subtrees by a Galois connection.  I would have to take some more steps to prove it, but it seems right at a glance.  This is a nice mathematical connection, and it would be great if it continues to hold in what I regard as the improved variation on contextual grammars.


  1. I have a copy of the Sestier paper if you want (in French). It is seminal I think. I have been much inspired by Marcus and Sestier and Kulagina, who are now neglected.

    l think contextual grammars are the wrong direction though representationally.

  2. Yeah, I don't think I'm thrilled with contextual grammars, but it's the idea of the 'context' and the mathematical properties that I found useful and forward-thinking. I just basically adapted it to tree-structured sentences without knowing any of the provenance in mathematical linguistics. As far as neglect, I'm surprised that all the Lambek followers never saw fit to cite Marcus.

    I would appreciate seeing the Sestier paper, I can more or less read French with occasional help from Google Translate!

  3. In the mail: by the way I have written a paper on this Galois connection; which just came out in Journal of Logic and Computation "The syntactic concept lattice: Another algebraic theory of the context-free languages?".

    But I realize now that though I cited Sestier and Marcus and Kulagina in earlier conference papers I didn't in this one. Which now seems like a mistake. Oh well.