In the framework of the "Milan Seminar on Automata and Formal Languages" initiative, which provides monthly seminars at UniversitÓ di Milano, UniversitÓ di Milano-Bicocca and Politecnico di Milano, on Tuesday, December 15th, 2011 , in the Sala Seminari del DEI at Dipartimento di Elettronica e Informazione in via Ponzio 34/5, Milano, Pierluigi San Pietro (Politecnico di Milano) will speak about "Consensual Languages".
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.