Graph Theory - Computational Linguistics and Talking Robots - page 171

A NAG may be based on an SRG, a signature, or a set of proplets (e.g., 7.4.2).
The following constraints on NAGs apply only to intra- and extrapropositional
functor-argument and intrapropositional coordination. Extrapropositional co-
ordination requires a separate treatment, as shown in the following Sect. 9.2.
In order to be wellformed, a NAG must satisfy the following conditions:

9.1.4 G RAPH - THEORETICAL CONSTRAINTS ON WELLFORMED NAG S

1. The signature must be simple , i.e., there must be no loops or multiple lines.
2. The NAG must be symmetric , i.e., for every arc connecting some nodes A
and B, 2 there must be an arc from B to A.
3. The traversal of arcs must be continuous , i.e., combining the traversal of
arc x from A to B and of arc y from C to D is permitted only if B = C.
4. The numbering of arcs must be exhaustive , i.e., there must exist a naviga-
tion which traverses each arc.
Because of conditions 1 (simple) and 2 (symmetric), the signature and the
associated NAG are graph-theoretically equivalent .
However, because the numbering of the arcs induces a restriction on the
traversal order of a NAG, the equivalence exists strictly speaking between the
signature and the set containing all NAGs for the content in question. 3 As
an example, consider the set of all possible NAGs corresponding to the n=3
(three-node) semantic relations graph of 9.1.3:

9.1.5 P OSSIBLE NAG S FOR AN N =3 SEMANTIC RELATIONS GRAPH

NAG 1 NAG 2

NAG 3 NAG 4

0
1

0

find find

find find

3

2

4

4

41 2

3 1

2 3

2 3 4

1

0

0

dog bone dog bone

dog bone dog bone

Graph-theoretically, the above graphs are all equally wellformed: excluding
the start line, the arcs are symmetric, the numbering is continuous, and the
traversal is exhaustive. Determining the possible NAGs for a given signature
and the numbering of the arcs may be left to a simple algorithm.
For linguistic purposes not all four graphs in 9.1.5 are equally suitable, how-
ever. In addition to graph-theoretical well-formedness (9.1.4), a NAG must
also satisfy the following linguistic constraints:

2 By requiring two nodes, a special exclusion of start lines is unnecessary.
3 Alternatively, the equivalence exists between a signature and the one associated un numbered arcs
graph. Or, if the traversal does not have to start at arc 1, the equivalence exists between a signature
and each of its associated NAGs.