[om] A Proposal for extending OpenMath with structure sharing

[Richard Fateman]

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