Strict local testability with consensus equals regularity, and other properties

A recent language definition device named consensual is based on agreement between similar words. Considering a language over a bipartite alphabet made by pairs of unmarked/marked letters, the match relation specifies when such words agree. Thus a set (the "base") over the bipartite alphabet consensually specifies another language that includes any terminal word such that a set of corresponding matching words is in the base. We show that all and only the regular languages are consensually generated by a strictly locally testable base; the result is based on a generalization of Medvedev's homomorphic characterization of regular languages. Consensually context-free languages strictly include the base family. The consensual and the base families collapse together if the base is context-sensitive. © 2013 World Scientific Publishing Company.