[38] discusses an extension of DCG in order to analyze the Australian free word-order language `Guugu Yimidhirr'. In ordinary DCG a category is associated with a pair indicating which location the constituent occupies. Johnson proposes that constituents in the extended version of DCG be associated with a set of such pairs. A constituent thus `occupies' a set of continuous locations. The following is a sentence of Guugu Yimidhirr:

In this sentence, the discontinuous constituent `Yarraga-aga-mu-n
...biiba-ngun' (boy's father) is associated with the set of
locations:

Johnson notices that such expressions can be represented with bit
vectors. In a grammar rule the sets of locations of the daughters of
the rule are `combined' to construct the set of locations associated
with the mother node. The predicate
*combines*(*s*_{1}, *s*_{2}, *s*) is true iff
*s* is equal to the (bit-wise) union of *s*_{1} and *s*_{2}, and the
(bit-wise) intersection of *s*_{1} and *s*_{2} is null (ie. *s*_{1} and
*s*_{2} must be non-overlapping locations). Grammars which exclusively
use this predicate, are permutation-closed. For Guugu Yimidhirr
Johnson also proposes a concatenative rule for possessive noun
constructions in which the possessive is identified by position rather
than by inflectional markings. Apart from these constructions Guugu
Yimidhirr is said to be permutation-closed (Johnson, quoting
[27]).
Earley deduction [66] is used as a general
proof procedure for such extended DCG grammars.

1998-09-30