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.