The Living Thing / Notebooks :

Grammatical inference

Mathematically speaking, inferring the “formal language” which can describe a set of expressions. In the slightly looser sense used by linguists studying natural human language, discovering the syntactic rules of a given language, which is kinda the same thing but with every term sloppier, and the subject matter itself messier.

This is already a crazy complex area, and being naturally perverse, I am interested in an especially esoteric corner of it, to whit, grammars of things that aren’t speech; inferring design grammars, say, could allow you to produce more things off the same “basic plan” from some examples of the thing; look at enough trees and you know how to build the rest of the forest, that kind of thing. I’m especially interested in things expressed not as a sequence of symbols from a finite alphabet - i.e. not over the free monoid, or over the free monoid but the symbol expression is hidden. This is a boutique interest. I also care about probabilistic ones, i.e. assigning measures to these things. That part is not at all boutique.

Normally design grammars deal with simple languages, such as, say “regular” languages. I’m interested in things a rung or two up the Chomsky hierarchy - Context-free grammars, maybe even context-sensitive ones.

See also design grammars, iterated function systems and my research proposal in this area.

Things to read