Consensual Languages

Pierluigi San Pietro (Politecnico di Milano)

giovedì 15 dicembre 2011 - 16.00 Sala Seminari del DEI



An ever present, common sense idea in language modeling research is that, for a word  to be a valid phrase, it should comply with multiple constraints at once. The talk will describe a recent language definition model, based on agreement or consensus between similar strings. Considering a regular set of strings over a bipartite alphabet made by pairs of unmarked/marked symbols, a match relation is introduced, in order to specify when such strings agree.  Then  a regular set over the bipartite alphabet can be interpreted as specifying another language over the unmarked alphabet, called the consensual language. A word is in the consensual language if a set of corresponding matching strings is in the original language. The family thus defined includes the regular languages and also interesting non-semilinear ones.

Various classical problems have been studied, e.g. closure properties, decidability/complexity of membership and emptiness, descriptional complexity of regular consensual languages.