# Honest Representations

The cause of the problem we just saw with the “dishonest” representation is not the (mathematically well-defined) mapping itself but rather the lack of suitable context for it. In particular, the integer successor function, for instance, cannot be implemented by any computable function under the nefarious representation p of the previous section, though it is part and parcel of our normal view of the naturals. As we will see, we can allow an honest representation to be any arbitrary injective (multivalued) function as long as we also pay attention to the internal structure of the abstract domain.

Imagine that Abe, the person posing instances of a problem, thinks in terms of an abstract domain A, such as integers, graphs, or pictures. Abe must have some means of describing for himself each of the elements of A, most commonly by means of a finite set G of “generators” of A (cf. [4, 9, 22, 23]). These generators give structure to A and meaning to its elements as described by ground terms H over G. For generators to do their job, every element of A must be equal to the value of at least one term in H; so at least one generator must be a scalar constant (of arity 0).[1] Examples of generators for the natural numbers include:

(in unary “caveperson” style), as well as for the commonplace binary representation, and

for ternary. With the latter two, there are infinitely many representations of the number zero.

insisting that the generators form a free term algebra (a Herbrand universe): more than one term

may designate the same abstract element.

Fig. 6.2 An abstract undirected, unlabeled graph

For undirected, unlabeled graphs, G, with vertices V (G denotes the set of graphs whose vertices are taken from the set V of vertices), an example of a set of generators is

Over these generators, the graph depicted in Fig. 6.2 is the value of the ground term

wherein there is an edge between the “first” and “second” vertices. It is also the value of the term

wherein there is an edge between the “third” and “second” vertices. [In general, generators can be partial.]

Accordingly, we formalize the notion of (honest) representation as any injective multivalued function from an abstract domain that is structured by generators. Recall that a multivalued function p : A ^ C (or set-valued function p : A ^ P(C)) is injective if p(x) П p(y) = 0 for all distinct x, y e A.

Definition 6.2 (Representation)

• • An abstract domain is a set A of elements, including (always) Boolean values true and false, equipped with a finite set G of generators for the whole domain, which also includes the binary equality relation =. Every element of A must be equal to at least one ground term over G.
• • A representation of A in a “concrete” domain C is an injective multivalued function p : A ^ C. We will insist that p(true) is finite.

• The representation p((a1,...,a„>) of a tuple of abstract elements ai is the set рЩ) x p(a2) x ... x p(an), the set of all tuples (c1,..., cn>, such that d e p(ai).

The equality relation and Boolean constants are required for interpreting the output, as we will see. Having only finitely many representations of true will allow Abe to understand and compare results of Cay’s computations.

Having representations as multi-valued, rather than single-valued, functions gives the freedom to have many representations for the same abstract element, as is very commonly done in practice. For example, one may represent the rational number one-half by /2, 7/i4, etc., and the unordered set {7, 2, 3} by the sequences (2, 3, 7>, (7, 3, 2>, etc.

The choice of what is “abstract” and what is “concrete” is in “the eyes of the beholder”; it is in the final analysis an arbitrary formal choice. One may view a number as an abstract entity, represented by a concrete string over the symbols 0 and 1, while another views the symbol 1 as an abstract entity represented by some ink dots or electric pulse, etc. Likewise, the equality relation = depends on the choice of what an abstract entity is. For example, if the abstract domain is graphs, then the graph of Fig. 6.2 is a single entity and all of its different generating terms yield equal entities, while in the case that the abstract domain consists of graphs with numbered vertices, the different generating terms yield isomorphic, but unequal, entities.

An alternative to the proposed generator-based approach for describing abstract elements would be to define them by means of a set of relations. For graphs, this might be the relation telling whether an edge is present between two given vertices. It is well known that using such relations, rather than generating functions, increases the complexity of many procedures. (For example, exhaustively checking all vertex combinations for getting an adjacent vertex.) Furthermore, we argue in Sect. 6.9 that this alternative does not at all fit the bill. Intuitively, a set of functions allows one to also generate the representations, while a set of relations does not.

• [1] Unlike the development in [4], where effectiveness of an algorithm was at issue, here we are not