Subtype Covering

[User's Manual]
[Code]
As discussed in the user's guide, TRALE assumes that subtypes exhaustively cover their supertypes. To recapitulate, let us review the example provided in the user's guide.

Figure 3.19: A sample deranged type signature

In the hierarchy depicted in Figure 3.19, there are no t objects with identically typed F and G values as in the following feature structures:

TRALE does not accept such undefined combinations of feature values as valid. However, if TRALE detects that only one subtype's product of values is consistent with a feature structure's product of values, it will promote the product to that consistent subtype's product. Thus, in our example, a feature structure:

will be promoted automatically to the following. Note that the type itself will not be promoted to t$_1$.

This section shows how subtype covering is handled in TRALE. Types whose feature values are not exhaustively covered by their subtypes' feature values (such as t in the above example) are called deranged types.

At the highest level, TRALE performs the following steps during signature compilation in order to compute subtype covering.

1. Find all the subtypes Sub of supertype Super.
2. Create a base subsumption graph representation of the subtype relations found.
3. Topologically sort the graph and reverse the result so that more specific types come first (see section 3.3).
4. For each type t, find the number of maximal types that are subsumed by t.
5. For each type t, determine the status of every type for the purpose of classifying deranged types (to be discussed below).

These steps can be seen in the following code snippet:

compile_deranged_assert :-
  !,findall(Super-Sub,(non_a_type(Super),
                       imm_sub_type(Super,Sub)),SubGEdges),
  vertices_edges_to_ugraph([],SubGEdges,SubG),
  top_sort(SubG,RevSortedTypes),
  reverse(RevSortedTypes,SortedTypes),
  compute_maxcount(SortedTypes,SubG),
  compute_deranged(SortedTypes,SubG).

Here we focus on the last two steps, namely, compute_maxcount/2 and compute_deranged/2.

Computing $maxcount$ of each type

[User's Manual]
[Code--Compute Max-Count]
$Maxcount$ counts the number of maximal types subsumed by every type. The $maxcount$ of every maximal type as well as a_/1 atoms is 1. The $maxcount$ of a non-maximal type t is the cardinality of the union of the sets of maximal subtypes covered by the immediate subtypes of t, as given by the base subsumption graph. For example, in the type signature of Figure 3.20, the $maxcount$ of d, e, and f is 1 because they are maximal types. The $maxcount$ of b and c is 2 as they cover $\{$d, e$\}$, and $\{$e, f$\}$ respectively. The $maxcount$ of a, then, will be $\vert${d, e}$\cup${e, f}$\vert=\vert${d, e, f}$\vert=3$.

Figure 3.20: A sample type hierarchy with multiple inheritance

Classifying Deranged Types

[User's Manual]
[Code--MaxCount Map]
Types are classified in two categories: normal, and deranged. Normal types are non-deranged types that can be treated as maximal (even if they are not) when checking a potentially deranged supertype. All maximal types are normal. Atoms, because they are downward-closed, are not deranged. We do not add an entry for atoms (including a_ atoms) to the database.

As mentioned above, a deranged type is one whose map of appropriate value restrictions is not exhaustively covered by the maps of appropriate value restrictions of its maximally specific subtypes. When checking potentially deranged supertypes, these types must be replaced by a minimal covering of normal subtypes. The predicate deranged/2 indicates the status of every type for the purpose of classifying deranged types.

A map is a product of types, such as that found in a set of appropriate features. $maxcountMap$ counts the number of maximal maps subsumed by every map. A maximal map is one that has a maximal type in every dimension (i.e., feature). $MaxcountMap$ of a map is the product of the $maxcount$ of every dimension. For example, type t in Figure 3.19 will have a $maxcountMap$ of four corresponding its four possible subtypes, only two of which are present as designated subtypes of t.

[Code--MaxCountMap] Then we need to identify which one of the maps cover a_ atoms, and delete those from the root map. This is because the a_ atoms have infinite subtypes.

[Code--Atomic Prune] We then replace all deranged types with their non-deranged subtype covers with normalise_cover/2.