How do I represent a strongly connected graph in XML grammar format?

• From: Dhruva Duncan <duncan@ISIP.MsState.EDU>
• Date: Fri, 10 Sep 2004 10:41:15 -0500 (CDT)
• To: www-voice@w3.org
• Message-Id: <200409101541.i8AFfFf02830@isip006.isip.msstate.edu>

I have a question regarding the use of the XML to
represent a directed graph according to the SRGS V1.0. 

If I have the graph 

  B--C--D
 /       \
A         H
 \       /
  E--F--G

this can be represented using the XML tags defined in the grammar
specification as shown below:

<grammar root="one">
  <rule id="one">
    <item> A </item>
    <one-of>
      <item>
        <item> B </item>
        <item> C </item>
        <item> D </item>
      </item>
      <item>
        <item> E </item>
        <item> F </item>
        <item> G </item>
      </item>
    </one-of>
    <item> H </item>
  </rule>
</grammar>

My question is, what happens if an arc is placed that connects the
two branches? For example, if we place an arc from B to F:

  B--C--D
 / \     \
A   \     H
 \   |   /
  E--F--G

The XML grammar would have to look like this:

<grammar root="one">
  <rule id="one">
    <item> A </item>
    <one-of>
      <item>
        <item> B </item>
        <one-of>
          <item>
            <item> F </item>
            <item> G </item>
          </item>
          <item>
            <item> C </item>
            <item> D </item>
          </item>
        </one-of>
      </item>
      <item>
        <item> E </item>
        <item> F </item>
        <item> G </item>
      </item>
    </one-of>
    <item> H </item>
  </rule>
</grammar>

Proper nesting of the XML tags does not allow the branches within any <one-of> 
statement to interact. So, to accomplish a graph equivalent to the one drawn
above, the path from B to the termination of B's branch had to be duplicated.
That by itself is fairly straight-forward, but note that there are now
multiple copies of F and G present.

If we go one step further, and add an arc from F to D, we get
the following graph:

  B--C--D
 / \   / \
A   \ /   H
 \   |   /
  E--F--G

The XML would look like:

<grammar root="one">
  <rule id="one">
    <item> A </item>
    <one-of>
      <item>
        <item> B </item>
        <one-of>
          <item>
            <item> F </item>
              <one-of>
                <item> G </item>
	        <item> D </item>    
              </one-of>
	    </item>
            <item>
              <item> C </item>
              <item> D </item>
            </item>
          </item>
        </one-of>
      </item>
      <item>
        <item> E </item>
        <item> F </item>
	<one-of>
          <item> G </item>
          <item> D </item>    
        </one-of>
      </item>
    </one-of>
    <item> H </item>
  </rule>
</grammar>

Again, the path from the source of the arc (F) to the point where the
branches recombine (H) had to be duplicated in each place where F was
present. If we continued in this fashion until we obtain the worst
case - a strongly connected graph - the resulting XML would be a tree
containing a large number of nodes.

I realize that by using ruleref tags I could possibly make this
grammar smaller, but that's not the problem I'm trying to address. Any
rule references created to reduce the size of groups of tags which
occur multiple times would still need to be invoked multiple times in
order to represent the XML you see above.

Is there a simpler way to represent this type of graph while following the 
XML SRGS V1.0? 

thanks very much,
Kyle Duncan

Received on Friday, 10 September 2004 16:06:37 UTC