<!-- $Id: p2gd.odd,v 1.11 1999/05/18 10:43:52 tei Exp $ -->
<!--*
    * $Log: p2gd.odd,v $
    * Revision 1.11  1999/05/18 10:43:52  tei
    * mixed content in gallachalzie eg
    *
    * Revision 1.10  1998/01/31 19:50:52  tei
    * Change system 'tei2.dtd' to public identifier
    * fix log keyword (if not already fixed)
    * normalize the sgml
    *
    * Revision 1.9  98/01/28  11:09:58  cmsmcq
    * LB changes of January 1998
    *
    * Revision 1.8  1994/04/08  18:54:36  msmcq
    * Last-second fixes for P3
    *
    * Revision 1.7  1994/03/27  16:30:14  lou
    * semifinal check
    *
    * Revision 1.5  1993/12/20  10:03:03  lou
    * fixed id
    *
    * Revision 1.4  1993/09/22  18:44:59  msmcq
    * Version as of publication of GD
    * -->
<!-- Revisions:                                               -->
<!-- 13 jan 98 : LB : fix typos in egs -->
<!-- 7 jan 98 : LB : VONT shd be VIENNENT -->
<!-- 94-04-07 : MSM : punctuation in head                     -->
<!-- 13 mar 94 : LB : applied mods from DTB/DD (twice) -->
<!-- 19 dec 93: LB : changed id on first dtd frag DAI->Dgd    -->
<!-- 93-09-17 : MSM : SGML fixes to exx                       -->
<!-- 93-09-17 : MSM : Expand discussion of Gallachalzie       -->
<!-- 93-09-17 : MSM : revise for publ                         -->
<!-- 93-09-16 : MSM : modify Argyll graph                     -->
<!-- 93-09-15 : MSM : quick revisions                         -->
<!-- 1 aug 93 : LB: various minor fixes to tagdocs            -->
<!--            changed title (was just 'Graphs')             -->
<!--            added DTD overall schema                      -->
<!-- 93-07-22 : DTL : add Sasine ex from DG                   -->
<!--                  minor revs based on new TAGDOCs         -->
<!-- 93-07-20 : DTL : add family tree, transducer exx         -->
<!--                  add definitions of path, connected      -->
<!-- 93-07-19 : DTL : change title to "Graphs"                -->
<!--                  make other changes suggested at Eynsham: -->
<!--                  single tagset for graphs, digraphs and  -->
<!--                   networks: GRAPH, NODE, ARC             -->
<!--                  replace specialized formatting          -->
<!--                   attributes by rend=                    -->
<!--                  eliminate LABEL tag, use attributes to  -->
<!--                   point to feature structures, etc.      -->
<!--                  use type= attribute to distinguish types -->
<!--                   of graphs                              -->
<!--                  change madeup exx to smthg realler      -->
<!--   8 Mar 93 : CMSMcQ : merge old 44.8 and 44.9, revise    -->
<!--                       intro, retitle as per chapter ST   -->
<!--                       ('nets')                           -->
<!--  29 Jul 92 :  DTL : Corrected ODD tagging, per LB.       -->
<!--  24 Jul 92 :  DTL : Renumber as p2.448.  Make other      -->
<!--                     minor changes.                       -->
<!--  21 Jul 92 :  DTL : Make minor corrections.              -->
<!--  14 Jul 92 :  DTL : Change ordering= to ord= on < tree > -->
<!--  Include attribute names (e.g. ord=) in example tags,    -->
<!-- even when they can be omitted.  Make minor               -->
<!-- corrections.  Change section numbers to p2.449, etc.     -->
<!-- Remove TAGDOC for  < label > , and add cross-reference   -->
<!-- to section on  < list > , in chapter 23, where           -->
<!--  < label >  is defined.                                  -->
<!--  10 Jul 92 :  DTL : Complete first draft, except for     -->
<!-- section on linguistic trees, based on AI1 working        -->
<!-- paper entitled "Encoding graphs, digraphs and trees",    -->
<!-- Nov. 1991, and suggestions from CMSMcQ on TEI-TECH in    -->
<!-- June 1992.                                               -->
<!--  Changes from ver. 1.14 of LING DTD:                     -->
<!--  Rename  < i.node >  as  < iNode > .                     -->
<!--  Rename adjac.to= as adjacTo=.                           -->
<!--  Rename adjac.from= as adjacFrom=.                       -->
<!--  Restore order= to ATTLIST of  < graph > ,  < digraph >  -->
<!--   and  < tree >.                                         -->
<!--  Restore size= to ATTLIST of < graph > and < digraph >.  -->
<!--  Restore degree= to ATTLIST of  < vertex >               -->
<!--  Restore inDegree= and outDegree= to ATTLIST of < node >. -->
<!--  Restore outDegree= to ATTLIST of < root > and < iNode >. -->
<!--  Add type= to ATTLIST of  < node >.                      -->
<!--  Add arity= to ATTLIST of  < tree > .                    -->
<!--  Add =partial as possible value for ordering= on < tree >. -->
<!--  Change content model of  < edge >  to permit at most    -->
<!--   one  < label >;                                        -->
<!--   add label= to ATTLIST of  < edge >;                    -->
<!--   change from= and to= to end1= and end2= in ATTLIST     -->
<!--    of  < edge >.                                 -->
<!--  Replace  < edge >  with  < arc >  as possible content   -->
<!--   of  < digraph >;                                       -->
<!--  ATTLIST of < arc > contains label=, from= and to=.      -->
<!--  Add attributes for drawing graphs, digraphs and trees   -->
<!--    as follows:                                           -->
<!--    vrtxFrame=, edgeSpec= to ATTLIST of  < graph >;       -->
<!--    nodeFrame=, arcSpec= to ATTLIST of  < digraph >       -->
<!--     and  < tree >;                                       -->
<!--    frame= to ATTLIST of < vertex >, < node >,            -->
<!--     < root >, < iNode > and < leaf >;                    -->
<!--    spec= to ATTLIST of  < edge >,  < arc >,  < root >    -->
<!--     and  < iNode >.                                      -->
<!-- P2.GD :  Networks, Graphs, Digraphs and Trees            -->

<!-- On title change, see next comment.            (DTL)      -->
<!-- < div1 id=GD n=23>                                       -->
<!-- < head>Networks, Graphs, Digraphs, and Trees< /head>     -->
<!-- EDITORS: How about changing id value to GR? (DTL)        -->
<!-- Taken already:  GR = grammar (msm)                       -->


<div1 id="GD" n="21"><head>Graphs, Networks, and Trees</head>

<!-- DTB writes: -->
<!--   This does not introduce the topic sufficiently well. These -->
<!-- Guidelines are not about encoding general data structures -->
<!-- primarily (?), they're about encoding (two words illegible) -->
<!-- text. So why do we have this stuff? We need to say it was -->
<!-- motivated by the linguistic stuff, I guess. -->

<p>Graphical representations are widely used for displaying relations
among informational units because they help readers to visualize those
relations and hence to understand them better.  Two general types of
graphical representations may be distinguished.

<!-- <note place=foot>The primary responsibility for this chapter -->
<!-- was borne by the working committee for analysis and -->
<!-- interpretation, whose members are listed in the front -->
<!-- matter.  It was drafted by D. Terence Langendoen with -->
<!-- assistance from Steven Zepp.  The Sasine text example and -->
<!-- suggested markup was provided by Daniel Greenstein.</note> -->

<list type="bullets">

<!-- I prefer to think of networks as special types of graphs -->
<!-- rather than the other way around.  (DTL)                 -->

<!-- Material deleted                                         -->
<!-- < item>Networks, that is < term>graphs< /term> and <     -->
<!-- term>digraphs< /term> (or < term>directed graphs<        -->
<!-- /term>) in the strictly mathematical sense, which        -->
<!-- consist of points, called < term>vertices< /term> or <   -->
<!-- term>nodes< /term>, and lines connecting them, called    -->
<!-- < term>edges < /term> or < term>arcs< /term>.            -->
<!-- End material deleted                                     -->

<item>Graphs, in the strictly mathematical sense, consist
of points, often called <term>nodes</term> or
<term>vertices</term>, and connections among them, called
<term>arcs</term>, or under certain conditions,
<term>edges</term>.  Among the various types of graphs are
<term>networks</term> and <term>trees</term>.  Graphs
generally and networks in particular are dealt with
directly below.  Trees are dealt with separately in
sections <ptr target="GDtr"> and <ptr target="GDat">.

<note place="foot">The treatment here is largely based on the
characterizations of graph types in <bibl><author>Gary Chartrand and
Linda Lesniak</author>, <title>Graphs and Digraphs</title>
(Menlo Park, CA: Wadsworth, 1986).</bibl></note></item>

<item><term>Charts</term>, which typically plot data in two or more
dimensions, including plots with orthogonal or radial axes, bar charts,
pie charts, and the like.  These can be described using the elements
defined in the additional tag set for figures and graphics; see
chapter <ptr target="FT">.</item>

</list>
<!-- LB inserted following --></p>

<p>The following DTD fragment shows the overall organization of the
tag set discussed in the remainder of this chapter.

<eg id=dgd>
<![ CDATA [
<!-- 21:  Graphs, networks and trees                          -->
<!-- ... declarations from section 21.1                       -->
<!--     (Graphs)                                             -->
<!--     go here ...                                          -->
<!-- ... declarations from section 21.2                       -->
<!--     (Trees (basic method))                               -->
<!--     go here ...                                          -->
<!-- ... declarations from section 21.3                       -->
<!--     (Trees (alternate method))                           -->
<!--     go here ...                                          -->
]]>
</eg>
</p>

<p>This tag set is made available as described in <ptr target="STin">; in
a document which uses the markup described in this chapter, the document
type declaration should contain the following declaration for the entity
<ident type="pe">tei.nets</ident>:

<eg>
<![ CDATA [
<!ENTITY % tei.nets 'INCLUDE'>
]]>
</eg>

The entire document type declaration for a document using this
additional tag set together with the prose base might look like this:
<eg>
<![ CDATA [
 <!DOCTYPE TEI.2 PUBLIC "-//TEI P3//DTD Main Document Type//EN"
                        "tei2.dtd" [
    <!ENTITY % tei.prose 'INCLUDE' >
    <!ENTITY % tei.nets  'INCLUDE' >
 ]>
]]>
</eg>

<!-- end of LB insertion --></p>

<p>Among the types of qualitative relations often represented by graphs
are organizational hierarchies, flow charts, genealogies, semantic
networks, transition networks, grammatical relations, tournament
schedules, seating plans, and directions to people's houses.  In
developing recommendations for the encoding of graphs of various types,
we have relied on their formal mathematical definitions and on the most
common conventions for representing them visually.  However, it must be
emphasized that these recommendations do not provide for the full range
of possible graphical representations, and deal only partially with
questions of design, layout and placement.</p>

<div2 id="GDgr"><head>Graphs and Digraphs</head>

<p>Broadly speaking, graphs can be divided into two types:
<term>undirected</term> and <term>directed</term>.  An undirected graph
is a set of <term>nodes</term> (or <term>vertices</term>) together with
a set of pairs of those vertices, called <term>arcs</term> or
<term>edges</term>.  Each node in an arc of an undirected graph is said
to be <term>incident</term> with that arc, and the two vertices which
make up an arc are said to be <term>adjacent</term>.  An directed graph
is like an undirected graph except that the arcs are <term>ordered
pairs</term> of nodes.  In the case of directed graphs, the term
<term>edge</term> is not used; moreover, each arc in an directed graph
is said to be <term>adjacent from</term> the node from which the arc
emanates, and <term>adjacent to </term> the node to which the arc is
directed.  We use the element <gi>graph</gi> to encode graphs as a
whole, <gi>node</gi> to encode nodes or vertices, and <gi>arc</gi> to
encode arcs or edges; arcs can also be encoded by attributes on the
<gi>node</gi> element.  These elements have the following descriptions
and attributes:

<list type=gloss>
<label><gi>graph</gi></label>
<item>encodes a graph, which is a collection of nodes, and arcs 
which
connect the nodes.
Attributes include:
<list type=gloss>
<label><att>type</att></label>
<item>describes the type of graph.
Suggested values include:
<list type=gloss>
<label><term>transducer</term></label>
<item>a transition network with up to two labels on each arc</item>
<label><term>undirected</term></label>
<item>undirected graph</item>
<label><term>transition network</term></label>
<item>a directed graph with distinguished initial and final nodes</item>
<label><term>directed</term></label>
<item>directed graph</item>
</list></item>
<label><att>label</att></label>
<item>gives a label for a graph.</item>
<label><att>order</att></label>
<item>states the order of the graph, i.e., the number of its 
nodes.</item>
<label><att>size</att></label>
<item>states the size of the graph, i.e., the number of its arcs.</item>
</list>
</item>
<label><gi>node</gi></label>
<item>encodes a node, a possibly labeled point in a graph.
Attributes include:
<list type=gloss>
<label><att>label</att></label>
<item>gives a label for a node.</item>
<label><att>label2</att></label>
<item>gives a second label for a node.</item>
<label><att>value</att></label>
<item>provides the value of a node, which is a feature structure 
or other analytic element.</item>
<label><att>type</att></label>
<item>provides a type for a node.
Suggested values include:
<list type=gloss>
<label><term>final</term></label>
<item>final node in a transition network</item>
<label><term>initial</term></label>
<item>initial node in a transition network</item>
</list></item>
<label><att>adjFrom</att></label>
<item>gives the IDs of the nodes which are adjacent from the 
current node.</item>
<label><att>adjTo</att></label>
<item>gives the IDs of the nodes which are adjacent to the 
current node.</item>
<label><att>adj</att></label>
<item>gives the IDs of the nodes which are both adjacent to and 
adjacent from the current node.</item>
<label><att>inDegree</att></label>
<item>gives the in degree of the node, the number of nodes which 
are adjacent from the given node.</item>
<label><att>outDegree</att></label>
<item>gives the out degree of the node, the number of nodes which 
are adjacent to the given node.</item>
<label><att>degree</att></label>
<item>gives the degree of the node, the number of arcs with which 
the node is incident.</item>
</list>
</item>
<label><gi>arc</gi></label>
<item>encodes an arc, the connection from one node to another in 
a graph.
Attributes include:
<list type=gloss>
<label><att>label</att></label>
<item>gives a label for an arc.</item>
<label><att>label2</att></label>
<item>gives a second label for an arc.</item>
<label><att>from</att></label>
<item>gives the ID of the node which is adjacent from this arc.</item>
<label><att>to</att></label>
<item>gives the ID of the node which is adjacent to this arc.</item>
</list>
</item>
</list>
</p>

<p>Before proceeding, some additional terminology may be helpful.  We
define a <term>path</term> in a graph as a sequence of nodes n1, ..., nk
such that there is an arc from each ni to ni+1 in the sequence.  A
<term>cyclic path</term>, or <term>cycle</term> is a path leading from a
particular node back to itself.  A graph that contains at least one
cycle is said to be <term>cyclic</term>; otherwise it is
<term>acyclic</term>.  We say, finally, that a graph is
<term>connected</term> if there is a path from some node to every other
node in the graph; any graph that is not connected is said to be
<term>disconnected</term>.</p>

<p>Here is an example of an undirected, cyclic disconnected graph, in
which the nodes are annotated with three-letter codes for airports, and
the arcs connecting the nodes are represented by horizontal and vertical
lines, with 90 degree bends used simply to avoid having to draw diagonal
lines.

<!--      LAX: Los Angeles                                    -->
<!--      LVG: Las Vegas                                      -->
<!--      PHX: Phoenix                                        -->
<!--      TUS: Tucson                                         -->
<!--      CIB: Seven Cities of Cibola                         -->

<eg rend="skel">
<![ CDATA [
          .---LAX---.
          |         |
         LVG-------PHX---TUS    CIB

  Airline Connections in Southwestern USA
]]>
</eg></p>

<p>Next is a markup of the graph, using <gi>arc</gi> elements to encode
the arcs.

<eg>
<![ CDATA [
<graph type=undirected
       id=cug1
       label='Airline Connections in Southwestern USA'
       order=5
       size=4>
  <node label=LAX id=LAX degree=2>
  <node label=LVG id=LVG degree=2>
  <node label=PHX id=PHX degree=3>
  <node label=TUS id=TUS degree=1>
  <node label=CIB id=CIB degree=0>
  <arc  from=LAX to=LVG>
  <arc  from=LAX to=PHX>
  <arc  from=LVG to=PHX>
  <arc  from=PHX to=TUS>
  </graph>
]]>
</eg></p>

<p>
<!-- The <att>rend</att> attribute on the <gi>graph</gi> element may -->
<!-- be used  here to encode certain information about how the graph -->
<!-- is to be drawn. -->
The <att>label</att> attribute on the <gi>graph</gi> element records
a
label for the graph; similarly, the <att>label</att> attribute on
the <gi>node</gi> elements records the labels of those nodes.  The
<att>order</att> and <att>size</att> attributes on the <gi>graph</gi>
element record the number of nodes and number of arcs in the graph
respectively; these values are optional (since they can be computed from
the rest of the graph), but if they are supplied, they must be
consistent with the rest of the encoding.  They can thus be used to help
check that the graph has been encoded and transmitted correctly.  The
<att>degree</att> attribute on the <gi>node</gi> elements record the
number of arcs that are incident with that node.  It is optional
(because redundant), but can be used to help in validity checking:  if a
value is given, it must be consistent with the rest of the information
in the graph.  Finally, the <att>from</att> and <att>to</att> attributes
on the <gi>arc</gi> elements provide pointers to the nodes connected by
those arcs.  Since the graph is undirected, no directionality is implied
by the use of the <att>from</att> and <att>to</att> attributes; the
values of these attributes could be interchanged in each arc without
changing the graph.</p>

<p>The <att>adj</att>, <att>adjFrom</att>, and <att>adjTo</att>
attributes of the <gi>node</gi> element provide an alternative method of
representing unlabeled arcs, their values being pointers to the nodes
which are adjacent to or from that node.  The <att>adj</att> attribute
is to be used for undirected graphs, and the <att>adjFrom</att> and
<att>adjTo</att> attributes for directed graphs.  It is a semantic error
for the directed adjacency attributes to be used in an undirected graph,
and vice versa.  Here is a markup of the preceding graph, using the
<att>adj</att> attribute to represent the arcs.

<eg>
<![ CDATA [
<graph type=undirected
       id=cug2
       label='Airline Connections in Southwestern USA'
       order=5
       size=4>
  <node label=LAX id=LAX degree=2 adj='LVG PHX'>
  <node label=LVG id=LVG degree=2 adj='LAX PHX'>
  <node label=PHX id=PHX degree=3 adj='LAX LVG TUS'>
  <node label=TUS id=TUS degree=1 adj='PHX'>
  <node label=CIB id=CIB degree=0>
  </graph>
]]>
</eg></p>

<p>Note that each arc is represented twice in this encoding of the
graph.  For example, the existence of the arc from LAX to LVG can be
inferred from each of the first two <gi>node</gi> elements in the graph.
This redundancy, however, is not required:  it suffices to describe an
arc in any one of the three places it can be described (either adjacent
node, or in a separate <gi>arc</gi> element).  Here is a less redundant
representation of the same graph.

<eg>
<![ CDATA [
<graph type=undirected
       id=cug3
       label='Airline Connections in Southwestern USA'
       order=5
       size=4>
  <node label=LAX id=LAX degree=2 adj='LVG PHX'>
  <node label=LVG id=LVG degree=2 adj='PHX'>
  <node label=PHX id=PHX degree=3 adj='TUS'>
  <node label=TUS id=TUS degree=1>
  <node label=CIB id=CIB degree=0>
  </graph>
]]>
</eg></p>

<p>Although in many cases the <gi>arc</gi> element is redundant (since
arcs can be described using the adjacency attributes of their adjacent
nodes), it has nevertheless been included in the tag set, in order to
allow the convenient specification of identifiers, display or
rendition information, and labels for each arc (using the attributes
<att>id</att>, <att>rend</att>, and <att>label</att>).</p>

<p>Next, let us modify the preceding graph by adding directionality to
the arcs.  Specifically, we now think of the arcs as specifying selected
routes from one airport to another, as indicated by the direction of the
arrowheads in the following diagram.

<eg rend="fig">
<![ CDATA [
          +-<-LAX-<-+
          |         |
         LVG--->---PHX--->---TUS   CIB
                    |         |
                    +----<----+

  Selected Airline Routes in Southwestern USA
]]>
</eg></p>

<p>Here is an encoding of this graph, using the <gi>arc</gi> element to
designate the arcs.

<eg>
<![ CDATA [
<graph type=directed
       id=rdg1
       label='Selected Airline Routes in Southwestern USA'
       order=5
       size=5>
   <node label=LAX id=LAX inDegree=1 outDegree=1>
   <node label=LVG id=LVG inDegree=1 outDegree=1>
   <node label=PHX id=PHX inDegree=2 outDegree=2>
   <node label=TUS id=TUS inDegree=1 outDegree=1>
   <node label=CIB id=CIB inDegree=0 outDegree=0>
   <arc  from=LAX to=LVG>
   <arc  from=LVG to=PHX>
   <arc  from=PHX to=LAX>
   <arc  from=PHX to=TUS>
   <arc  from=TUS to=PHX>
   </graph>
]]>
</eg></p>

<p>Here is another encoding of the graph, using the <att>adjTo</att> and
<att>adjFrom</att> attributes on nodes to designate the arcs.

<eg>
<![ CDATA [
<graph type=directed
       id=rdg2
       label='Selected Airline Routes in Southwestern USA'
       order=5
       size=5>
   <node label=LAX id=LAX inDegree=1
         outDegree=1 adjTo=LVG adjFrom=PHX>
   <node label=LVG id=LVG inDegree=1
         outDegree=1 adjFrom=LAX adjTo=PHX>
   <node label=PHX id=PHX inDegree=2
         outDegree=2 adjTo='LAX TUS' adjFrom='LVG TUS'>
   <node label=TUS id=TUS inDegree=1
         outDegree=1 adjTo=PHX adjFrom=PHX>
   <node label=CIB id=CIB inDegree=0 outDegree=0>
   </graph>
]]>
</eg></p>

<p>If we wish to label the arcs, say with flight numbers, then
<gi>arc</gi> elements must be used to carry the <att>label</att>
attribute, as in the following example.

<eg>
<![ CDATA [
<graph type=directed
       id=rdg1
       label='Selected Airline Routes in Southwestern USA'
       order=5
       size=5>
   <node label=LAX id=LAX >
   <node label=LVG id=LVG >
   <node label=PHX id=PHX >
   <node label=TUS id=TUS >
   <node label=CIB id=CIB >
   <arc  from=LAX to=LVG label='SW117'>
   <arc  from=LVG to=PHX label='SW711'>
   <arc  from=PHX to=LAX label='AA218'>
   <arc  from=PHX to=TUS label='AW229'>
   <arc  from=TUS to=PHX label='AW225'>
   </graph>
]]>
</eg>
<!-- indegree/outdegree removed at DD's suggestion --></p>
<p>The formal declarations of the <gi>graph</gi>, <gi>node</gi> and
<gi>arc</gi> elements are as follows.

<eg id=dgdgr>
<![ CDATA [
<!-- 21.1:  Graphs                                            -->
<!ELEMENT graph         - -  ((node+, arc*) | (arc*, node+))    >
<!ATTLIST graph              %a.global;
          label              CDATA               #IMPLIED
          order              NUMBER              #IMPLIED
          size               NUMBER              #IMPLIED
          type               CDATA               #IMPLIED       >
<!ELEMENT node          - O  EMPTY                              >
<!ATTLIST node               %a.global;
          label              CDATA               #IMPLIED
          label2             CDATA               #IMPLIED
          value              IDREF               #IMPLIED
          outDegree          NUMBER              #IMPLIED
          adjTo              IDREFS              #IMPLIED
          adjFrom            IDREFS              #IMPLIED
          inDegree           NUMBER              #IMPLIED
          type               CDATA               #IMPLIED
          adj                IDREFS              #IMPLIED
          degree             NUMBER              #IMPLIED       >
<!ELEMENT arc           - O  EMPTY                              >
<!ATTLIST arc                %a.global;
          label              CDATA               #IMPLIED
          to                 IDREF               #REQUIRED
          label2             CDATA               #IMPLIED
          from               IDREF               #REQUIRED      >
<!-- This fragment is used in sec. 21                         -->
]]>
</eg>
</p>

<div3><head>Transition Networks</head>
<p>For encoding transition networks and other kinds of directed graphs
in which distinctions among types of nodes must be made, the
<att>type</att> attribute is provided for <gi>node</gi> elements.  In
the following example, the <term>initial</term> and <term>final</term>
nodes (or <term>states</term>) of the network are distinguished.  It can
be understood as accepting the set of strings obtained by traversing it
from its initial node to its final node, and concatenating the labels.

<!-- Noam Chomsky, Syntactic Structures, 1957, p19, ex8 -->
<eg rend="fig">
<![ CDATA [
             OLD      MAN      COMES
            +->-+   +-->----o---->---+
            |   |   |                |
            \   /   |                |
        THE  \ /    |                |
(8)   o-->----o-----+                o
                    |                |
                    |                |
                    |                |
                    +-->----o---->---+
                      MEN       COME

<graph type='transition network'
       id=ss8
       label='(8)'
       order=5
       size=6>
   <node id=q0 inDegree=0 outDegree=1 type=initial>
   <node id=q1 inDegree=2 outDegree=3>
   <node id=q2 inDegree=1 outDegree=1>
   <node id=q3 inDegree=1 outDegree=1>
   <node id=q4 inDegree=2 outDegree=0 type=final>
   <arc  from=q0 to=q1 label=THE>
   <arc  from=q1 to=q1 label=OLD>
   <arc  from=q1 to=q2 label=MAN>
   <arc  from=q1 to=q3 label=MEN>
   <arc  from=q2 to=q4 label=COMES>
   <arc  from=q3 to=q4 label=COME>
   </graph>
]]>
</eg></p>

<p>A finite state transducer has two labels on each arc, and can be
thought of as representing a mapping from one sequence of labels to
the other.  The following example represents a transducer for
translating the English strings accepted by the network in the
preceding example into French.  The nodes have been annotated with
numbers, for convenience.

<eg rend="fig">
<![ CDATA [

         THE         MAN      COMES
      +--->---1------->-----4--->---+
      |   L'  |     HOMME     VIENT |
      |       |                     |
      |    OLD|VIEIL                |
      |       |                     |
      | THE   |                     |
(8)   0-->----2                     6
      |  LE  / \                    |
      |     /   \                   |
      |    /     \                  |
      |    | OLD |                  |
      |    +-->--+                  |
      |     VIEIL                   |
      |  THE        MEN       COME  |
      +--->---3------>----5---->----+
         LES / \   HOMMES   VIENNENT
            /   \
           /     \
           | OLD |
           +-->--+
            VIEUX
]]></eg><eg><![ CDATA [
<graph type='transducer'
       order=7
       size=10>
   <node id=t0 label=0 inDegree=0 outDegree=3 type=initial>
   <node id=t1 label=1 inDegree=2 outDegree=1>
   <node id=t2 label=2 inDegree=2 outDegree=2>
   <node id=t3 label=3 inDegree=2 outDegree=2>
   <node id=t4 label=4 inDegree=1 outDegree=1>
   <node id=t5 label=5 inDegree=1 outDegree=1>
   <node id=t6 label=6 inDegree=2 outDegree=0 type=final>
   <arc  from=t0 to=t1 label=THE label2="L'">
   <arc  from=t0 to=t2 label=THE label2=LE>
   <arc  from=t0 to=t3 label=THE label2=LES>
   <arc  from=t1 to=t4 label=MAN label2=HOMME>
   <arc  from=t2 to=t1 label=OLD label2=VIEIL>
   <arc  from=t2 to=t2 label=OLD label2=VIEIL>
   <arc  from=t3 to=t3 label=OLD label2=VIEUX>
   <arc  from=t3 to=t5 label=MEN label2=HOMMES>
   <arc  from=t4 to=t6 label=COMES label2=VIENT>
   <arc  from=t5 to=t6 label=COME label2=VIENNENT>
   </graph>
]]>
</eg></p></div3>

<div3><head>Family Trees</head>

<p>The next example provides an encoding a portion of a
<socalled>family tree</socalled>, in which nodes are used to represent
individuals, and parents of individuals, and arcs are used to
represent common parentage and descent links.  Let us suppose,
further, that information about individuals is contained in feature
structures, which are contained in feature-structure libraries
elsewhere in the document (see <ptr target="FSfl">).  We can use the
<att>value</att> attribute on <gi>node</gi> elements to point to those
feature structures.  Assume that, in some particular representation of
the graph, nodes representing females are framed by circles, nodes
representing males are framed by boxes, and nodes representing parents
are framed by diamonds.

<eg rend="fig"><![ CDATA [
                            Mo     Fa
                  Katherine->--K+A--<-Amberley
                                |
                        So      |    Da
                   +----<-------+----->----+
                   |            | So       |
                Bertrand        +->-+    Rachel
                   |                |
                   |              Frank
         Mo     Fa | Fa     Mo
   Peter->--P+B--<-+->--D+B--<-Dora
             |           |
          So |        Da | So
         +-<-+     +--<--+-->--+
         |         |           |
       Conrad     Kate        John
]]></eg><eg><![ CDATA [
<graph type='family tree' order=13 size=12>
  <node id=KathR  label='Katherine'
        value=kr1 inDegree=0 outDegree=1>
  <node id=AmbeR  label='Amberley'
        value=ar1 inDegree=0 outDegree=1>
  <node id=KAR  label='K+A'
        inDegree=2 outDegree=3>
  <node id=BertR  label='Bertrand'
        value=br1 inDegree=1 outDegree=2>
  <node id=PeteR  label='Peter'
        value=pr1 inDegree=0 outDegree=1>
  <node id=DoraR  label='Dora'
        value=dr1 inDegree=0 outDegree=1>
  <node id=PBR  label='P+B'
        inDegree=2 outDegree=1>
  <node id=DBR  label='D+B'
        inDegree=2 outDegree=2>
  <node id=FranR  label='Frank'
        value=fr1 inDegree=1 outDegree=0>
  <node id=RachR  label='Rachel'
        value=rr1 inDegree=1 outDegree=0>
  <node id=ConrR  label='Conrad'
        value=cr1 inDegree=1 outDegree=0>
  <node id=KateR  label='Kate'
        value=kr2 inDegree=1 outDegree=0>
  <node id=JohnR  label='John'
        value=jr1 inDegree=1 outDegree=0>
  <arc label='Mo' from=KathR to=KAR>
  <arc label='Fa' from=AmbeR to=KAR>
  <arc label='So' from=KAR to=BertR>
  <arc label='So' from=KAR to=FranR>
  <arc label='Da' from=KAR to=RachR>
  <arc label='Mo' from=PeteR to=PBR>
  <arc label='Fa' from=BertR to=PBR>
  <arc label='So' from=PBR to=ConrR>
  <arc label='Mo' from=DoraR to=DBR>
  <arc label='Fa' from=BertR to=DBR>
  <arc label='Da' from=DBR to=KateR>
  <arc label='So' from=DBR to=JohnR>
  </graph>
]]>
</eg>
<!-- Partial family tree for Bertrand Russell, based on       -->
<!-- Pereira and Shieber, Prolog and Natural Language         -->
<!-- Analysis, 1987, p22                                      --></p></div3>

<div3><head>Historical Interpretation</head>

<p>For our final example, we represent graphically the relationships
among various geographic areas mentioned in a
seventeenth-century Scottish document.  The document itself is
a <socalled>sasine</socalled>, which records a grant of land
from the earl of Argyll to one Donald McNeill, and reads in part
as follows (abbreviations have been expanded silently,
and <q>[...]</q> marks illegible passages):

<!-- From Dan Greenstein; EDS: can you get more details? -->
<!-- I think the text is quoted in Dan's contribution to      -->
<!-- CHum special issue. (DTL)                                -->


<q rend="display"><p>
Item instrument of Sasine given the said Hector
Mcneil confirmed and dated 28 May 1632
[...] at Edinburgh upon the 15 June 1632
</p><p>
Item ane charter granted by Archibald late earl
of Argyle and Donald McNeill of Gallachalzie wh
makes mention that ...
the said late Earl yields and grants
to the said Donald MacNeill ...
</p><p>
All and hail the two merk land of old extent
of Gallachalzie with the pertinents by and in
the lordship of Knapdale within the sherrifdome
of Argyll
</p><p>
[description of other lands granted follows ...]
</p><p>
This Charter is dated at Inverary the 15th May 1669
</p></q></p>

<p>In this example, we are concerned with the land and pertinents (i.e.
accompanying sources of revenue) described as <q>the two merk land of
old extent of Gallachalzie with the pertinents by and in the lordship of
Knapdale within the sherrifdom of Argyll</q>.</p>

<p>The passage concerns the following pieces of land:
<list type="bullets">
<item>the Earl of Argyll's land (i.e. the lands granted by this clause
of the sasine)</item>
<item>two mark of land in Gallachalzie</item>
<item>the pertinents for this land</item>
<item>the Lordship of Knapdale</item>
<item>the sherrifdom of Argyll</item>
</list>
We will represent these geographic entities as nodes in a graph.
Arcs in the graph will represent the following relationships among
them:
<list type="bullets">
<item>containment (INCLUDE)</item>
<item>location within (IN)</item>
<item>contiguity (BY)</item>
<item>constituency (PART OF)</item>
</list>

Note that these relationships are logically related: <q>include</q>
and <q>in</q>, for example, are inverses of each other: the Earl of
Argyll's land includes the parcel in Gallachalzie, and the parcel is
therefore in the Earl of Argyll's land.  Given an explicit set of
inference rules, an appropriate application could use the graph we are
constructing to infer the logical consequences of the relationships we
identify.</p>

<p>Let us assume that feature-structure analyses are available which
describe Gallachalzie, Knapdale, and Argyll.  We will link to those
feature structures using the <att>value</att> attribute on the nodes
representing those places.  However, there may be some uncertainty as to
which noun phrase is modified by the phrase <q>within the sheriffdome of
Argyll</q>:  perhaps the entire lands (land and pertinents) are in
Argyll, perhaps just the pertinents are, or perhaps only Knapdale is
(together with the portion of the pertinents which is in Knapdale).  We
will represent all three of these interpretations in the graph; they
are, however, mutually exclusive, which we represent using the
<att>excl</att> attribute defined in
chapter <ptr target="AI">.<note place="foot">That is, the three syntactic
interpretations of the clause are mutually exclusive.  The notion that
the pertinents are in Argyll is clearly not inconsistent with the notion
that both the land in Gallachalzie and the pertinents are in Argyll.
The graph given here describes the possible interpretations of the
clause itself, not the sets of inferences derivable from each syntactic
interpretation, for which it would be convenient to use the facilities
described in chapter <ptr target="FS">.
</note></p>

<p>We represent the graph and its encoding as follows, where
the dotted lines in the graph indicate the mutually exclusive arcs; in
the encoding, we use the <att>exclude</att> attribute to indicate those
arcs.

<eg rend="skel"><![ CDATA [
              Earl of Argyll's land
            (land described in sasine)
                      | | |
      ,-<-INCLUDE--<--' + '->-INCLUDE---> Pertinents
      |                 :                  :  |   |
 Gallachalzie          IN  ...<..IN..<.....:  |   |
                        :  :                  |   |
                        :  :             INCLUDE INCLUDE
                        :  :              |           |
                        :  :   (part of pertinents)  (part)
                        :  :              |           |
                        :  :              BY         PART OF
                        :  :              |           |
                        :  :          Lordship of Knapdale
                        :  :                   :
                        :  :  ...<.IN..<.......:
                        :  :  :
                Sherrifdom of Argyll
]]>
</eg>

<!-- why are some lines dotted? and no rend even supplied here for -->
<!-- me to delete! -->

The graph formalizes the following relationships:
<list type="bullets">
<item>the Earl of Argyll's land <mentioned>includes</mentioned> (the parcel of
land in) Gallachalzie</item>
<item>the Earl of Argyll's land <mentioned>includes</mentioned> the pertinents of that parcel</item>
<item>the pertinents are (in part) <mentioned>by</mentioned> the Lordship of Knapdale</item>
<item>the pertinents are (in part) <mentioned>part of</mentioned> the Lordship of Knapdale</item>
<item>the Earl of Argyll's land, or the pertinents, or
the Lordship of Knapdale, is <mentioned>in</mentioned> the Sherrifdom of Argyll</item>
</list>
We encode the graph thus:
<eg>
<![ CDATA [
<graph type=directed order=7 size=9>
  <node id=earl label="Earl of Argyll's land">
  <node id=gall label="Gallachalzie" value=gallfs>
  <node id=pert label="Pertinents">
  <node id=per1 label="Pertinents part">
  <node id=per2 label="Pertinents part">
  <node id=knap label="Lordship of Knapdale" value=knapfs>
  <node id=argy label="Sherrifdome of Argyll" value=argyfs>
  <arc  id=earlgall label="INCLUDE" from=earl to=gall>
  <arc  id=earlargy label="IN" from=earl to=argy
        exclude="pertargy knapargy">
  <arc  id=earlpert label="INCLUDE" from=earl to=pert>
  <arc  id=pertper1 label="INCLUDE" from=pert to=per1>
  <arc  id=pertper2 label="INCLUDE" from=pert to=per2>
  <arc  id=pertargy label="IN" from=pert to=argy
        exclude="earlargy knapargy">
  <arc  id=per1knap label="BY" from=per1 to=knap>
  <arc  id=per2knap label="PART OF" from=per2 to=knap>
  <arc  id=knapargy label="IN" from=knap to=argy
        exclude="earlargy pertargy">
  </graph>
]]>
</eg>
</p>
</div3>
</div2>
<!-- $Id: p2gdtr.odd,v 1.7 1998/01/31 19:50:52 tei Exp $ -->
<!--*
    * $Log: p2gdtr.odd,v $
    * Revision 1.7  1998/01/31 19:50:52  tei
    * Change system 'tei2.dtd' to public identifier
    * fix log keyword (if not already fixed)
    * normalize the sgml
    *
    * Revision 1.6  94/03/27  16:30:20  lou
    * semifinal check
    *
    * Revision 1.3  1993/09/22  18:46:17  msmcq
    * Revision as of publication of GD
    * -->
<!-- Revisions:                                               -->
<!-- 93-09-17 : MSM : fix exx                                 -->
<!-- 93-09-17 : MSM : exx changes (quote LABEL values)        -->
<!-- 93-09-17 : MSM : outdegr[ee], cosmetic changes           -->
<!-- 93-09-15 : MSM : quick revisions                         -->
<!-- 93-07-20 : DTL : make changes consistent with GD         -->
<!--                  change first madeup ex to a realler one -->
<!--                  align attributes in examples            -->

<div2 id="GDtr" type="Terry"><head>Trees</head>

<p>A <term>tree</term> is a connected acyclic graph.  That is, it is
possible in a tree graph to follow a path from any vertex to any other
vertex, but there are no paths that lead from any vertex to itself.  A
rooted tree is a directed graph based on a tree; that is, the arcs in
the graph correspond to the arcs of a tree such that there is exactly
one node, called the <term>root</term>, for which there is a path from
that node to all other nodes in the graph.  For our purposes, we may
ignore all trees except for rooted trees, and hence we shall use the
<gi>tree</gi> element for rooted trees, and the <gi>root</gi> element
for its root.  The nodes adjacent to a given node are called its
<term>children</term>, and the node adjacent from a given node is called
its <term>parent</term>.  Nodes with both a parent and children are
called <term>internal nodes</term>, for which we use the <gi>iNode</gi>
element.  A node with no children is tagged as a <gi>leaf</gi>.  If the
children of a node are ordered from left to right, then we say that that
node is <term>ordered</term>.  If all the nodes of a tree are ordered,
then we say that the tree is an <term>ordered tree</term>.  If some of
the nodes of a tree are ordered and others are not, then the tree is a
<term>partially ordered tree</term>.  The ordering of nodes and trees
may be specified by an attribute; we take the default ordering for trees
to be ordered, that roots inherit their ordering from the trees in which
they occur, and internal nodes inherit their ordering from their
parents.  Finally, we permit a node to be specified as following other
nodes, which (when its parent is ordered) it would be assumed to
precede, giving rise to crossing arcs.
<!-- DD writes concerning above sentence:
"  Makes no sense! Is this just another way to specify order
 or does it convert ordered nodes to partially ordered nodes?"
 I dunno. So I'm leaving well alone. (LB) -->
The elements used for the
encoding of trees have the following descriptions and attributes.

<list type=gloss>
<label><gi>tree</gi></label>
<item>encodes a tree, which is made up of a root, internal nodes,
leaves, and arcs from root to leaves.
Attributes include:
<list type=gloss>
<label><att>arity</att></label>
<item>gives the maximum number of children of the root and 
internal nodes of the tree.</item>
<label><att>ord</att></label>
<item>indicates whether or not the tree is ordered, or if it is 
partially ordered.
Legal values are:
<list type=gloss>
<label><term>Y</term></label>
<item>indicates that all of the branching nodes of the tree are 
ordered.</item>
<label><term>N</term></label>
<item>indicates that all of the branching nodes of the tree are 
unordered.</item>
<label><term>partial</term></label>
<item>indicates that some of the branching nodes of the tree are 
ordered and some are unordered.</item>
</list></item>
<label><att>order</att></label>
<item>gives the order of the tree, i.e., the number of its nodes.</item>
</list>
</item>
<label><gi>root</gi></label>
<item>represents the root node of a tree.
Attributes include:
<list type=gloss>
<label><att>label</att></label>
<item>gives a label for a root node.</item>
<label><att>value</att></label>
<item>provides the value of the root, which is a feature 
structure or other analytic element.</item>
<label><att>children</att></label>
<item>provides a list of IDs of the elements which are the 
children of the root node.</item>
<label><att>ord</att></label>
<item>indicates whether or not the root is ordered.
Legal values are:
<list type=gloss>
<label><term>Y</term></label>
<item>indicates that the children of the root are ordered.</item>
<label><term>N</term></label>
<item>indicates that the children of the root are unordered.</item>
</list></item>
<label><att>outDegree</att></label>
<item>gives the out degree of the root, the number of its 
children.</item>
</list>
</item>
<label><gi>iNode</gi></label>
<item>represents an intermediate (or internal) node of a tree.
Attributes include:
<list type=gloss>
<label><att>label</att></label>
<item>gives a label for an intermediate node.</item>
<label><att>value</att></label>
<item>provides the value of an intermediate node, which is a 
feature structure or other analytic element.</item>
<label><att>children</att></label>
<item>provides a list of IDs of the elements which are the 
children of the intermediate node.</item>
<label><att>parent</att></label>
<item>provides the ID of the element which is the parent of this 
node.</item>
<label><att>ord</att></label>
<item>indicates whether or not the internal node is ordered.
Legal values are:
<list type=gloss>
<label><term>Y</term></label>
<item>indicates that the children of the intermediate node are 
ordered.</item>
<label><term>N</term></label>
<item>indicates that the children of the intermediate node are 
unordered.</item>
</list></item>
<label><att>follow</att></label>
<item>provides an ID of the element which this node follows.</item>
<label><att>outDegree</att></label>
<item>gives the out degree of an intermediate node, the number of 
its children.</item>
</list>
</item>
<label><gi>leaf</gi></label>
<item>encodes the leaves (terminal nodes) of a tree.
Attributes include:
<list type=gloss>
<label><att>label</att></label>
<item>gives a label for a leaf.</item>
<label><att>value</att></label>
<item>provides the value of a leaf, which is a feature structure 
or other analytic element.</item>
<label><att>parent</att></label>
<item>provides the ID of parent of a leaf.</item>
<label><att>follow</att></label>
<item>provides an ID of an element which this leaf follows.</item>
</list>
</item>
</list>
</p>

<p>Here is an example of a tree.  It represents the order in which the
operators of addition (symbolized by <code>+</code>), exponentiation
(symbolized by <code>**</code>) and division (symbolized by <code>/</code>) are
applied in evaluating the arithmetic formula <code>
((a**2)+(b**2))/((a+b)**2) </code>.
In drawing the graph, the root is placed on the far right, and
directionality is presumed to be to the left.

<eg>
<![ CDATA [
a--,
   |-**-,
2--'    |
        |-+--,
b--,    |    |
   |-**-'    |
2--'         |
             |-/
a--,         |
   |-+--,    |
b--'    |    |
        |-**-'
        |
2-------'

<tree n='ex1' arity=2 order=12>
   <root  label='/'  id=div1               children='plu1 exp1'>
   <iNode label='+'  id=plu1   parent=div1 children='exp2 exp3'>
   <iNode label='**' id=exp1   parent=div1 children='plu2 num2.3'>
   <iNode label='**' id=exp2   parent=plu1 children='vara1 num2.1'>
   <iNode label='**' id=exp3   parent=plu1 children='varb1 num2.2'>
   <iNode label='+'  id=plu2   parent=exp1 children='vara2 varb2'>
   <leaf  label='a'  id=vara1  parent=exp2>
   <leaf  label='2'  id=num2.1 parent=exp2>
   <leaf  label='b'  id=varb1  parent=exp3>
   <leaf  label='2'  id=num2.2 parent=exp3>
   <leaf  label='a'  id=vara2  parent=plu2>
   <leaf  label='b'  id=varb2  parent=plu2>
   <leaf  label='2'  id=num2.3 parent=exp1>
   </tree>
]]>
</eg></p>

<p>In this encoding, the <att>arity</att> attribute represents the
<term>arity</term> of the tree, which is the greatest value of the
<att>outDegree</att> attribute for any of the nodes in the tree.  If, as
in this case, <att>arity=2</att>, we say that the tree is a
<term>binary</term> tree.</p>

<p>Since the left-to-right (or top-to-bottom!) order of the children of
the two <code>+</code> nodes does not affect the arithmetic result in this
case, we could represent in this tree all of the arithmetically
equivalent formulas involving its leaves, by specifying the attribute
<att>ord=N</att> on those two <gi>iNode</gi> elements, the attribute
<att>ord=Y</att> on the <gi>root</gi> and other <gi>iNode</gi>
elements, and the attribute <att>ord=partial</att> on the <gi>tree</gi>
element, as follows.

<eg><![ CDATA [
<tree n='ex2' ord=partial arity=2 order=13>
 <root  label='/'  id=div1   ord=Y             children='plu1 exp1'>
 <iNode label='+'  id=plu1   ord=N parent=div1 children='exp2 exp3'>
 <iNode label='**' id=exp1   ord=Y parent=div1 children='plu2 num2.3'>
 <iNode label='**' id=exp2   ord=Y parent=plu1 children='vara1 num2.1'>
 <iNode label='**' id=exp3   ord=Y parent=plu1 children='varb1 num2.2'>
 <iNode label='+'  id=plu2   ord=N parent=exp1 children='vara2 varb2'>
 <leaf  label='a'  id=vara1        parent=exp2>
 <leaf  label='2'  id=num2.1       parent=exp2>
 <leaf  label='b'  id=varb1        parent=exp3>
 <leaf  label='2'  id=num2.2       parent=exp3>
 <leaf  label='a'  id=vara2        parent=plu2>
 <leaf  label='b'  id=varb2        parent=plu2>
 <leaf  label='2'  id=num2.3       parent=exp1>
 </tree>
]]>
</eg></p>

<p>This encoding represents all of the following:

<list>
<item><code>((a**2)+(b**2))/((a+b)**2)</code></item>
<item><code>((b**2)+(a**2))/((a+b)**2)</code></item>
<item><code>((a**2)+(b**2))/((b+a)**2)</code></item>
<item><code>((b**2)+(a**2))/((a+b)**2)</code></item>
</list></p>

<p>Linguistic phrase structure is very commonly represented by trees.
Here is an example of phrase structure represented by an ordered tree
with its root at the top, and a possible encoding.

<eg><![ CDATA [
      ,---PP---,
      |        |
      P    ,--NP--,
      |    |      |
     with Art     N
           |      |
          the periscope

<tree n='ex3' arity=2 order=8>
   <root  id=PP1               children='P1 NP1'     label='PP'>
   <iNode id=P1    parent=PP1  children=with1        label='P'>
   <leaf  id=with1 parent=P1                         label='with'>
   <iNode id=NP1   parent=PP1  children='the1 peri1' label='NP'>
   <iNode id=Art1  parent=NP1  children=the1         label='Art'>
   <leaf  id=the1  parent=Art1                       label='the'>
   <iNode id=N1    parent=NP1  children=peri1        label='N'>
   <leaf  id=peri1 parent=N1                         label='periscope'>
   </tree>
]]>
</eg></p>

<p>Finally, here is an example of an ordered tree, in which a particular
node which ordinarily would precede another is specified as following
it.  In the drawing, the <code>xxx</code> symbol indicates that the arc from
VB to PT crosses the arc from VP to PN.

<eg>
<![ CDATA [
       ,--VP--,
       |      |
   ,--VB-----xxx--,
   |          |   |
   VB         PN  PT
   |          |   |
  look       them up

<tree n='ex4' arity=2 order=8>
   <leaf  label='look' id=look1 parent=VB2>
   <leaf  label='them' id=them1 parent=PN1>
   <leaf  label='up'   id=up1   parent=PT1>
   <iNode label='VB'   id=VB2   parent=VB1 children=look1>
   <iNode label='PN'   id=PN1   parent=VP1 children=them1 >
   <iNode label='PT'   id=PT1   parent=VB1 children=up1 follow=PN1>
   <iNode label='VB'   id=VB1   parent=VP1 children='VB2 PT1'>
   <root  label='VP'   id=VP1              children='VB1 PN1'>
   </tree>
]]>
</eg></p>

<p>The formal declarations of the <gi>tree</gi>, <gi>root</gi>,
<gi>iNode</gi> and <gi>leaf</gi> elements are as follows.

<eg id=dgdtr>
<![ CDATA [
<!-- 21.2:  Trees (basic method)                              -->
<!ELEMENT tree          - -  ((leaf | iNode)*, root, (leaf | 
                             iNode)*)                           >
<!ATTLIST tree               %a.global;
          label              CDATA               #IMPLIED
          order              NUMBER              #IMPLIED
          ord                (Y | N | partial)   Y
          arity              NUMBER              #IMPLIED       >
<!ELEMENT root          - O  EMPTY                              >
<!ATTLIST root               %a.global;
          label              CDATA               #IMPLIED
          value              IDREF               #IMPLIED
          children           IDREFS              #IMPLIED
          outDegree          NUMBER              #IMPLIED
          ord                (Y | N)             #IMPLIED       >
<!ELEMENT iNode         - O  EMPTY                              >
<!ATTLIST iNode              %a.global;
          parent             IDREF               #IMPLIED
          label              CDATA               #IMPLIED
          follow             IDREF               #IMPLIED
          value              IDREF               #IMPLIED
          children           IDREFS              #REQUIRED
          outDegree          NUMBER              #IMPLIED
          ord                (Y | N)             #IMPLIED       >
<!ELEMENT leaf          - O  EMPTY                              >
<!ATTLIST leaf               %a.global;
          parent             IDREF               #IMPLIED
          label              CDATA               #IMPLIED
          follow             IDREF               #IMPLIED
          value              IDREF               #IMPLIED       >
<!-- This fragment is used in sec. 21                         -->
]]>
</eg>


<!-- P2.449 : Another Tree Notation                           -->
<!-- Revisions                                                -->
<!-- 93-07-21 : DTL : replace < echo > by < eTree copyOf=xx > -->
<!--                  correct exs with missing < /eTree >     -->
<!-- 92-12-14 : MSM : correct forestgrp id value              -->
<!-- 24 Jul 92 : DTL  : Renumber section to p2.449.  Make     -->
<!--    other minor changes.                                  -->
<!-- 21 Jul 92 : DTL  : Make minor corrections.               -->
<!-- 19 Jul 92 : DTL  : Add ODD tagging and TAGDOCS.          -->
<!--    Complete draft.  Changes from ver 1.14 of A&I         -->
<!--    DTD: change < e.tree > and < e.leaf > to < eTree      -->
<!--    > and < eLeaf > respectively.  Remove name= from      -->
<!--    ATTLIST of < eTree > and < triangle > (the global     -->
<!--    n= attribute can be used).  Change content model      -->
<!--    of < forest > to include the possibility of           -->
<!--    < triangle >s.  Change content model of <             -->
<!--    forestGrp > to permit one or more < forest >s,        -->
<!--    instead of two or more.  Allow < echo > in            -->
<!--    content model of < forest > and < forestGrp >.        -->
<!-- 17 Jul 92 : SZ, DTL: Incorporate material from ALLC      -->
<!--    draft article.                                        --></p></div2>

<div2 id="GDat" type="Anthony"><head>Another Tree Notation</head>
<!-- DD writes: "shouldnt this be swapped with preceding section
    as this is the more natural tree representation? -->
<p>In this section, we present an alternative to the method of
representing the structure of ordered rooted trees that is given in
section <ptr target="GDtr" type="div3">, which is based on the observation
that any node of such a tree can be thought of as the root of the
subtree that it dominates.  Thus subtrees can be thought of as the same
type as the trees they are embedded in, hence the designation
<gi>eTree</gi>, for <term>embedding tree</term>.  Whereas in a
<gi>tree</gi>, the relationship among the parts is indicated by the
<att>children</att> attribute, and by the names of the elements
<gi>root</gi>, <gi>iNode</gi> and <gi>leaf</gi>, the relationship among
the parts of an <gi>eTree</gi> is indicated simply by the arrangement of
their content.  However, we have chosen to enable encoders to
distinguish the terminal elements of an <gi>eTree</gi> by means of the
empty <gi>eLeaf</gi> element, though its use is not required; the
<gi>eTree</gi> element can also be used to identify the terminal nodes
of <gi>eTree</gi> elements.  We also provide a <gi>triangle</gi>
element, which can be thought of as an <term>underspecified</term>
<gi>eTree</gi>, that is an <gi>eTree</gi> in which certain information
has been left out.  In addition, we provide a <gi>forest</gi> element,
which consists of one or more <gi>tree</gi>, <gi>eTree</gi> or
<gi>triangle</gi> elements, and a <gi>forestGrp</gi> element, which
consists of one or more <gi>forest</gi> elements.  The elements used for
the encoding of embedding trees and the units containing them have the
following descriptions and attributes.

<list type=gloss>
<label><gi>eTree</gi></label>
<item>provides an alternative to <gi>tree</gi> element for 
representing
ordered rooted tree structures.
Attributes include:
<list type=gloss>
<label><att>label</att></label>
<item>gives a label for an embedding tree.</item>
<label><att>value</att></label>
<item>provides the value of an embedding tree, which is a feature 
structure or other analytic element.</item>
</list>
</item>
<label><gi>triangle</gi></label>
<item>provides for an underspecified <gi>eTree</gi>, that is,
an 
<gi>eTree</gi> with information left out.
Attributes include:
<list type=gloss>
<label><att>label</att></label>
<item>gives a label for an underspecified embedding tree.</item>
<label><att>value</att></label>
<item>provides the value of a triangle, which is the SGML 
identifier of a feature structure or other analytic 
element.</item>
</list>
</item>
<label><gi>eLeaf</gi></label>
<item>provides explicitly for a leaf of an embedding tree, which 
may also
be encoded with the <gi>eTree</gi> element.
Attributes include:
<list type=gloss>
<label><att>label</att></label>
<item>gives a label for a leaf of an embedding tree.</item>
<label><att>value</att></label>
<item>provides the value of an embedding leaf, which is a feature 
structure or other analytic element.</item>
</list>
</item>
<label><gi>forest</gi></label>
<item>provides for groups of rooted trees.
Attributes include:
<list type=gloss>
<label><att>type</att></label>
<item>identifies the type of the forest.</item>
</list>
</item>
<label><gi>forestGrp</gi></label>
<item>provides for groups of forests.
Attributes include:
<list type=gloss>
<label><att>type</att></label>
<item>identifies the type of the forest group.</item>
</list>
</item>
</list>
</p>

<p>Like the <gi>root</gi>, <gi>iNode</gi> and <gi>leaf</gi> of a
<gi>tree</gi>, the <gi>eTree</gi>, <gi>triangle</gi> and
<gi>eLeaf</gi> elements may also have <att>label</att> and
<att>value</att> attributes.</p>

<p>To illustrate the use of the <gi>eTree</gi> and <gi>eLeaf</gi>
elements, here is an encoding of the second example in section <ptr
target="GDtr" type="div3">, repeated here for convenience.

<eg><![ CDATA [
      ,---PP---,
      |        |
      P    ,--NP--,
      |    |      |
     with Art     N
           |      |
          the periscope

<eTree n='ex1' label='PP'>
   <eTree label='P'><eLeaf label='with'></eTree>
   <eTree label='NP'>
      <eTree label='Art'><eLeaf label='the'></eTree>
      <eTree label='N'><eLeaf label='periscope'></eTree>
      </eTree>
   </eTree>
]]>
</eg></p>

<p>Next, we provide an encoding, using the <gi>triangle</gi> element, in
which the internal structure of the <gi>eTree</gi> labeled <code>NP</code> is
omitted.

<eg><![ CDATA [
      ,---PP----,
      |         |
      P        NP
      |       /  \
     with    /    \
            /______\
          the periscope

<eTree n='ex2' label='PP'>
   <eTree label='P'><eLeaf label='with'></eTree>
   <triangle label='NP'><eLeaf label='the periscope'></triangle>
   </eTree>
]]>
</eg></p>

<p>Ambiguity involving alternative tree structures associated with the
same terminal sequence can be encoded relatively conveniently using a
combination of the <att>exclude</att> and <att>copyOf</att> attributes
described in sections <ptr target="SAat"> and <ptr target="SAie">.  In
the simplest case, an <gi>eTree</gi> may be part of the content of
exactly one of two different <gi>eTree</gi> elements.  To mark it up,
the embedded <gi>eTree</gi> may be fully specified within one of the
embedding <gi>eTree</gi> elements to which it may belong, and a
virtual copy, specified by the <att>copyOf</att> attribute, may appear
on the other.  In addition, each of the embedded elements in question
is specified as excluding the other, using the <att>exclude</att>
attribute.  To illustrate, consider the English phrase <mentioned>see the
vessel with the periscope</mentioned>, which may be considered to be
structurally ambiguous, depending on whether the phrase <mentioned>with
the periscope</mentioned> is a modifier of the phrase <mentioned>the
vessel</mentioned> or a modifier of the phrase <mentioned>see the
vessel</mentioned>.  This ambiguity is indicated in the sketch of the
ambiguous tree by means of the dotted-line arcs.  The markup using the
<att>copyOf</att> and <att>exclude</att> attributes follows the
sketch.

<eg><![ CDATA [
      ,--------VP....................
      |        |                    :
      V   ,----NP.......         ,--PP--,
      |   |    |       :         |      |
     see Art   N    ,--PP--,     P    ,-NP-,
          |    |    |      |     |    |    |
         the vessel P    ,-NP-, with Art   N
                    |    |    |       |    |
                   with Art   N      the periscope
                         |    |
                        the periscope

<eTree n='ex3' label='VP'>
   <eTree label='V'><eLeaf label='see'></eTree>
   <eTree label='NP'>
      <eTree label='Art'><eLeaf label='the'></eTree>
      <eTree label='N'><eLeaf label='vessel'></eTree>
      <eTree id=ppa exclude=ppb label='PP'>
         <eTree label='P'><eLeaf label='with'></eTree>
         <eTree label='NP'>
            <eTree label='Art'><eLeaf label='the'></eTree>
            <eTree label='N'><eLeaf label='periscope'></eTree>
            </eTree>
         </eTree>
      </eTree>
   <eTree id=ppb copyOf=ppa exclude=ppa label='PP'></eTree>
   </eTree>
]]>
</eg></p>

<p>To indicate that one of the alternatives is selected, one may specify
the <att>select</att> attribute on the highest <gi>eTree</gi> as
either <att>select=ppa</att> or <att>select=ppb</att>; see section
<ptr target="SAat">.</p>

<p>Depending on the grammar one uses to associate structures with
examples like <mentioned>see the man with the periscope</mentioned>, the
representations may be more complicated than this.  For example,
adopting a version of the <term>X-bar</term> theory of phrase structure
originated by Jackendoff<note><bibl>R. Jackendoff,
<title>X-Bar Syntax</title>, 1977</bibl></note>, the
attachment of a modifier may require the creation of an intermediate
node which is not required when the attachment is not made, as shown in
the following diagram.  A possible encoding of this ambiguous structure
immediately follows the diagram.

<eg><![ CDATA [
    ..............VP......................
    :                                    :
 ,--V'--,                          ,-----V'------,
 |      |                          |             |
 V    ,-NP--,                   ,--V'--,      ,--PP--,
 |    |     |                   |      |      |      |
see  Spec ,-N'--,               V    ,-NP-,   P    ,-NP-,
      |   |     |               |    |    |   |    |    |
     the  N'  ,-PP---,         see  Spec  N' with Spec  N'
          |   |      |               |    |        |    |
          N   P    ,-NP-,           the   N       the   N
          |   |    |    |                 |             |
      vessel with Spec  N'             vessel        periscope
                   |    |
                  the   N
                        |
                     periscope

<eTree n='ex4' label="VP">
   <eTree id=vbara exclude=vbarb label="V'">
      <eTree id=va label="V"><eLeaf label="see"></eTree>
      <eTree label="NP">
         <eTree id=spec1a label="Spec"><eLeaf label="the"></eTree>
         <eTree label="N'">
            <eTree id=nbar2a label="N'">
               <eTree label="N"><eLeaf label="vessel"></eTree>
               </eTree>
            <eTree id=ppa label="PP">
               <eTree label="P"><eLeaf label="with"></eTree>
               <eTree label="NP">
                  <eTree label="Spec"><eLeaf label="the"></eTree>
                  <eTree label="N'">
                     <eTree label="N"><eLeaf label="periscope"></eTree>
                     </eTree>
                  </eTree>
               </eTree>
            </eTree>
         </eTree>
      </eTree>
   <eTree id=vbara exclude=vbarb label="V'">
      <eTree label="V'">
         <eTree id=vb copyOf=va label="V"></eTree>
         <eTree label="NP">
            <eTree id=spec1b copyOf=spec1a label="Spec"></eTree>
            <eTree id=nbar2b copyOf=nbar2a label="N'"></eTree>
            </eTree>
         </eTree>
      <eTree id=ppb copyOf=ppa label="PP"></eTree>
      </eTree>
   </eTree>
]]>
</eg></p>

<p>A <term>derivation</term> in a generative grammar is often thought
of as a set of trees.  To encode such a derivation, one may use the
<gi>forest</gi> element, in which the trees may be marked up using the
<gi>tree</gi>, the <gi>eTree</gi> or the <gi>triangle</gi> element.
The <att>type</att> attribute may be used to specify what kind of
derivation it is.  Here is an example of a two-tree forest, involving
application of the <socalled>wh-movement</socalled> transformation in
the derivation of <mentioned>what you do</mentioned> (as in <mentioned>this is
what you do</mentioned>) from the underlying <mentioned>you do what
</mentioned><note place="foot">The symbols <code>e</code> and <code>t</code> denote
special theoretical constructs (<term>empty category</term> and
<term>trace</term> respectively), which need not concern us here.</note>.

<eg><![ CDATA [
     ,--S'--,                 ,--S'--,
     |      |                 |      |
    COMP ,--S--,             COMP ,--S--,
     |   |     |              |   |     |
     e   NP  ,-VP-,           NP  NP  ,-VP-,
         |   |    |           |   |   |    |
        you  V    NP        what you  V    NP
             |    |                   |    |
            do   what                do    t

<forest n='ex5' type='syntactic derivation'>
   <eTree n='Stage 1' id=s1sbar label="S'">
      <eTree id=s1comp label="COMP"><eleaf id=s1e label="e"></eTree>
      <eTree id=s1s label="S">
         <eTree id=s1np1 label="NP"><eLeaf label="you"></eTree>
         <eTree id=s1vp label="VP">
            <eTree id=s1v label="V"><eLeaf label="do"></eTree>
            <eTree id=s1np2 label="NP">
               <eLeaf id=s1wh label="what">
               </eTree>
            </eTree>
         </eTree>
      </eTree>
   <eTree n='Stage 2' id=s2sbar corresp=s1sbar label="S'">
      <eTree id=s2comp corresp=s1comp label="COMP">
         <eTree copyOf=s1np2 corresp=s1e label="NP"></eTree>
         </eTree>
      <eTree id=s2s corresp=s1s label="S">
         <eTree id=s2np1 copyOf=s1np1 label="NP"></eTree>
         <eTree id=s2vp corresp=s1vp label="VP">
            <eTree id=s2v copyOf=s1v label="V"></eTree>
            <eTree id=s2np2 corresp=s1np2 label="NP">
              <eLeaf corresp=s1wh label="t">
              </eTree>
            </eTree>
         </eTree>
      </eTree>
   </forest>
]]>
</eg></p>

<p>In this markup, we have used <att>copyOf</att> attributes to provide
virtual copies of elements in the tree representing the second stage of
the derivation that also occur in the first stage, and the
<att>corresp</att> attribute (see section <ptr target="SAcs">) to link
those elements in the second stage with corresponding elements in the
first stage that are not copies of them.</p>

<p>If a group of forests (e.g. a full grammatical derivation including
syntactic, semantic and phonological subderivations) is to be
articulated, the grouping element <gi>forestGrp</gi> may be used.</p>

<p>The formal declarations of the <gi>eTree</gi>, <gi>triangle</gi>,
<gi>eLeaf</gi>, <gi>forest</gi> and <gi>forestGrp</gi> elements are as
follows.

<eg id=dgdal>
<![ CDATA [
<!-- 21.3:  Trees (alternate method)                          -->
<!ELEMENT eTree         - -  ((eTree | triangle | eLeaf )*)     >
<!ATTLIST eTree              %a.global;
          label              CDATA               #IMPLIED
          value              IDREF               #IMPLIED       >
<!ELEMENT triangle      - -  ((eTree | triangle | eLeaf)*)      >
<!ATTLIST triangle           %a.global;
          label              CDATA               #IMPLIED
          value              IDREF               #IMPLIED       >
<!ELEMENT eLeaf         - O  EMPTY                              >
<!ATTLIST eLeaf              %a.global;
          label              CDATA               #IMPLIED
          value              IDREF               #IMPLIED       >
<!ELEMENT forest        - -  ((tree | eTree | triangle)+)       >
<!ATTLIST forest             %a.global;
          type               CDATA               #IMPLIED       >
<!ELEMENT forestGrp     - -  ((forest)+)                        >
<!ATTLIST forestGrp          %a.global;
          type               CDATA               #IMPLIED       >
<!-- This fragment is used in sec. 21                         -->
]]>
</eg>

</p></div2>
<!-- Keep this comment at the end of the file
Local variables:
mode: sgml
sgml-default-dtd-file:"~/lib/psgml/p2odd.ced"
sgml-parent-document:("/home/tei/P3/Master/Odds/p2.odd" "TEI.1" "TEXT" "BODY" "DIV1")
sgml-omittag:t
sgml-shorttag:t
End:
-->

</div1>
<!-- Keep this comment at the end of the file
Local variables:
mode: sgml
sgml-default-dtd-file:"~/lib/psgml/p2odd.ced"
sgml-parent-document:("/home/tei/P3/Master/Odds/p2.odd" "TEI.1" "TEXT" "BODY" "DIV1")
sgml-omittag:t
sgml-shorttag:t
End:
-->
             <!-- 21 Graphs and Digraphs -->
