3.3 Encoding Products of Finite Domains

Our simple example hardly touched on the power of the technique: it was not sufficiently ambiguous. In a real application, agreement involves several features and not just `number'. For example, German agreement involves 5 features:

gender -> masculine,feminine,neutral number -> singular,plural person -> 1,2,3 case -> nominative,accusative,dative,genitive quantifier -> definite,indefinite,none

However these features do not vary independently. For example the determiner ein is singular, but may be either masculine or neutral. If it is masculine, then it has nominative case. If it is neutral then it may have case nominative or accusative.

An elegant way to address the issue is, instead of insisting that the program preserve the distinction of features,¹ to merge them together into a compound `agreement' tuple that takes values in the cartesian product:

gender * number * person * case * quantifier

Next we notice that, since each dimension of the cartesian product can take only finitely many values, the cartesian product itself has finitely many values. This means that we can encode each tuple by a distinct integer and we can represent a disjunction of tuples by means of a finite domain.

3.3.1 Establishing a bijection between tuples and integers

3.3.2 Implementation