[om] A Proposal for extending OpenMath with structure sharing

[Michael Kohlhase]

Dear all, 

just as the discussion about structure sharing in the OpenMath XML encoding
has petered out, Andreas Franke has noticed a complication. If we are not
careful with links, then it is simple to represent infinite data
structures. Consider for instance the continued fraction 1/(1+1/(1+1/...))

<OMOBJ>
  <OMA id="foo">
    <OMS cd="arith1" name="divide"/>
    <OMI>1</OMI>
    <OMA>
       <OMS cd="arith1" name="plus"/>
       <OMI>1</OMI>
       <OMR xref="foo"/>
    </OMA> 
  </OMA>
</OMOBJ>

While handy for this special case, this construction is highly
dangerous. Also, this is not restricted to such simple cases, as the
following example shows. 

<OMOBJ>
 <OMA id="bar">
  <OMS cd="arith1" name="plus"/>
  <OMI>1</OMI>
  <OMR xref="baz"/>
 </OMA>
</OMOBJ>

<OMOBJ>
 <OMA id="baz">
  <OMS cd="arith1" name="plus"/>
  <OMI>1</OMI>
  <OMR xref="bar"/>
 </OMA>
</OMOBJ>

I think that we should disallow such cyclic links. The constraint might go
something like this:

We say that an OM element dominates all its children and all elements they
dominate. An OMR element dominates its target, i.e. the element that
carries the id attribute pointed to by the xref attribute. 

An OM element is is illegal, if dominates itself. 

In our first example, the OMA id="foo" dominates its second child, which
dominates the OMR element, which dominates its target, the OMA id="foo" 
--> illegal

In the second example, the OMA id="bar" dominates its second child, the OMR
xref="baz", which dominates its target OMA id="baz", which dominates its
second child <OMR xref="bar"/>, which in turn dominates its target <OMA
id="bar">. ---> illegal as well. 

     Michael

--
om at openmath.org  -  general discussion on OpenMath
Post public announcements to om-announce at openmath.org
Automatic list maintenance software at majordomo at openmath.org
Mail om-owner at openmath.org for assistance with any problems