recognizable_relation (731B)
1 # Recognizable relation 2 3 A [relation] over [words] (i.e., a subset of pairs of words -- potentially the first and second component are not over the same [alphabet]) is *recognizable* if it is a finite [union] of [Cartesian_products] of [regular_languages] (on each alphabet) 4 5 By [Mezei's_theorem] (cf [morvan2025homomorphism] Prop VII.1.1), they are exactly the relations that are [monoid_recognized] by finite [monoids] and [morphisms] 6 - This theorem generalizes to a correspondence between [monoid_varieties] and [language_varieties] 7 8 A recognizable relation must contain an infinite [clique] (cf [morvan2025homomorphism] Cor VII.1.3) 9 10 Generalizations: [automatic_relations] 11 12 Up: [word_relation] 13 14 Aliases: recognizable relations