[om] A Proposal for extending OpenMath with structure sharing

[Stephen Watt]

My first reaction would be to agree with you, Richard.

On Tue, Jun 25, 2002 at 09:34:14PM -0700, Richard Fateman wrote:
> What is the problem with cyclical data structures?  The reading
> and printing of such structures is defined in ANSI common lisp.
> Why not use the same kind of idea?
> RJF
> 
> 
> Michael Kohlhase wrote:
> 
> > 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
> > 
> 
> 
> --
> 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
--
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