[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:
![\begin{displaymath}
\{[0,1],[3,4]\}
\end{displaymath}](img268.png){kind=small}
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(s1, s2, s) is true iff
s is equal to the (bit-wise) union of s1 and s2, and the
(bit-wise) intersection of s1 and s2 is null (ie. s1 and
s2 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.