Minimality.

A parser is called minimal iff it returns one solution for each possible derivation. As it stands the parser is not minimal in this sense. In fact, if the same word occurs more than once in the input string then we may find a solution several times. The problem comes about because a list is not an appropriate data structure for bags. For example, removing an element from a bag should not be non deterministic, but it is if we use lists (in Prolog this problem may be repaired using the cut). It is straightforward to encode bags with a more appropriate data structure such as the one found in some Prolog libraries, which we will adopt with slight modifications. ³

An empty bag is represented by the constant `bag'. A nonempty bag consists of three parts: an element, a (representation of a) number indicating how often this element occurs in the bag, and the rest of the bag. Furthermore the bag is ordered in such a way that an element precedes another element in the bag iff it precedes that element in some standard order. For example, in Prolog the bag {a, b, a, a, b, c} is represented as:

For clarity I sometimes write such a bag as:

$$\langle$$a/3, b/2, c/1$$\rangle$$

and use the usual list notation.

The parser is modified as follows. The predicate which calls the parser will contain an extra predicate, list_to_bag/2, which encodes a list as a bag. Furthermore this bag is given as the input argument to parse/3; the output argument is the empty bag, the constant bag.

The `subset' predicate is now defined for such bags, and for this reason it is called `subbag'.

This definition of the predicate `subbag' is deterministic given the first two arguments, and given the fact that the elements of the bag are always constants. The modified version of the parser is minimal.