Algebraic grammatical inference

A description is given of an approach to grammatical inference. Given both a positive and negative sample of the language to be learned, each string is mapped into a multi-variate polynomial expression. These expressions are each given values depending on their membership of the language. If we are inferring a non-stochastic grammar, then each expression derived from a positive string must equate to true, while each expression derived from a negative string must equate to false. Grammatical inference then reduces to an explicit constraint satisfaction process. In the non-stochastic case, this involves finding the least upper bound of the set of positive constraints that does not violate any negative constraint. Encouraging results are demonstrated on learning the parity and palindrome problems