Next: Permutation groups Up: Indexing and Functions Previous: Indexing and Ordering   Contents

## Functions and Index Flags

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

• Instead of using -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 pair, we allow several kinds of contractions'' (see map below):

• If different -s map to the same image, then instead of listing all these pairs we say . If the function has just one image we may say .

• Sometimes the user is not interested in the preimage of , but only in its cardinality, so we allow .

• Finally, we even allow leaving the preimage part of the pair blank, just giving the list of function values .

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 a design is -resolvable; for each value of , the answer may be true'', false'', or unknown''.

Next: Permutation groups Up: Indexing and Functions Previous: Indexing and Ordering   Contents
Peter Dobcsanyi 2003-12-15