An ever present, common sense idea in language modelling research is that, for a
word to be a valid phrase, it should comply with multiple constraints at
once. A new language definition model is studied, 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. The word problem can be solved in
NLOGSPACE, hence in P time.
The emptiness problem is undecidable.
Closure properties are
proved for intersection with regular sets and inverse alphabetical homomorphism.
Several conditions for a consensual definition to yield a regular language are
presented, and it is shown that the size of a consensual specification of
regular languages can be in a logarithmic ratio with respect to a DFA. The
family is incomparable with context-free and tree-adjoining grammar families.