Functions and Index Flags

A function $f$ with finite domain can be given by listing all $(x, f(x))$ pairs. Note that this list when spelled out in XML format can be a very large one, in particular, if the $x$-s are complex objects on their own. To help on this problem we can do several things:

• Instead of using $x$-s themself we use only indices referring to them. function_on_indices is defined to do this.

  The underlying principle is that if the external representation explicitly contains the related objects in a well defined (canonical) order then, in general, we use indexing as a way to refer to these objects. Nesting, in this sense, is not allowed.

• Frequently the domain of our functions is the set of k-subsets of some of our objects. function_on_ksubsets_of_indices is defined for this situation.

• Regarding the $(x, f(x))$ pair, we allow several kinds of ``contractions'' (see map below):
  • If different $x$-s map to the same image, then instead of listing all these pairs we say $(\{x, x_1, x_2, \ldots \}, f(x))$. If the function $f$ has just one image $f(x)$ we may say $(\mathrm{entire\_domain}, f(x))$.

  • Sometimes the user is not interested in the preimage $\{x, x_1, x_2, \ldots \}$ of $f(x)$, but only in its cardinality, so we allow $(\vert\{x, x_1, x_2, \ldots \}\vert, f(x) )$.

  • Finally, we even allow leaving the preimage part of the pair blank, just giving the list of function values $( , f(x))$.

In fact, the user may only be interested in the image cardinality, in which case the entire function body may be blank.

In more detail:

function_on_indices = element function_on_indices {
    attribute domain            { "points" | "blocks" } ,
    attribute n                 { xsd:nonNegativeInteger } ,
    attribute ordered           { "true" | "unknown" } ,
    attribute image_cardinality	{ xsd:positiveInteger } ? ,
    attribute precision         { xsd:positiveInteger } ? ,
    attribute title             { text } ? ,
    ( map + | blank )
}

This specifies a function on either points or blocks. n is the cardinality of the domain. ordered specifies whether the function entries are ordered (by preimages): if the function body is not blank and each preimage is given explicitly or (if there is just one function image) as the empty element entire_domain (i.e. neither as a preimage_cardinality nor blank), then the value of ordered must be ``true", otherwise it is ``unknown". precision is required if the function values are real numbers and specifies the precision to which they have been computed. A function is given by a sequence of map's, each of which is specified as follows:

map = element map {
    ( preimage | preimage_cardinality | blank )
    ,
    element image { z | d | q | not_applicable }
}

preimage = element preimage {
    z +
    |
    element ksubset { z+ } +
    |
    entire_domain
}

preimage_cardinality = element preimage_cardinality { z }

For an example of the use of function_on_indices, see section 7.5 on Resolutions.

The function_on_ksubsets_of_indices specification works in the same way when the domain consists of all sets of points or blocks of fixed size k:

function_on_ksubsets_of_indices = element function_on_ksubsets_of_indices {
    attribute domain_base       { "points" | "blocks" } ,
    attribute n                 { xsd:nonNegativeInteger } ,
    attribute k                 { xsd:nonNegativeInteger } ,
    attribute ordered           { "true" | "unknown" } ,
    attribute image_cardinality	{ xsd:positiveInteger } ? ,
    attribute precision         { xsd:positiveInteger } ? ,
    attribute title             { text } ? ,
    ( map + | blank )
}

For an example of its use, see the section 7.3.1 on Point concurrences.

We use the concept of index_flag to store an element in a list of ``fuzzy booleans'':

index_flag = element index_flag {
    attribute index { xsd:nonNegativeInteger },
    attribute flag  { "true" | "false" | "unknown" }
}

For example, we may want to record for which values of $\alpha$ a design is $\alpha$-resolvable; for each value of $\alpha$, the answer may be ``true'', ``false'', or ``unknown''.