[om] Re: [CfD] Proposal for a Standard Change

[Michael Kohlhase]

Dear all,

on September 12, I made a proposal to change the standard to allow
structure sharing [http://www.openmath.org/archive/om/msg00537.html] that
contained concrete language for the standard change. 

Unfortunately, I forgot to add a text passage for page 23, where the OMR
element is explained. The material is not new, it comes from an e-mail
discussion [http://www.openmath.org/archive/om/msg00484.html], and has only
been re-arranged for the standard change proposal.

My proposal read 

> p.23 needs an  explanation of the 'OMR' element has to be given,
>      concretely we should a paragraph at the end stating (in LaTeX for
>      convenience):
>
>      OpenMath integers, floating point numbers, character strings,
>      byearrays, applications, binding, attribuitions can also be encoded
>      as an empty {\tt{OMR}} element with an {\tt{xlink:href}} attribute
>      whose value is the value of an id attribute of an OpenMath object of
>      that type. The OpenMath element represented by this {\tt{OMR}}
>      element is a copy of the OpenMath element pointed to in the
>      {\tt{xlink:xref}} attribute. Note that the representation of the
>      {\tt{OMR}} element is {\emph{structurally equal}}, but not identical
>      to the element it points to. 
>
>      For instance, the OpenMath object 
>      [... some examples ...]

This misses a discussion of the acyclicity constraint. So the text should
be (I have marked the new stuff)

*********** begin old stuff **************** 
      [OMR explanation; see above]   
    
      For instance, the OpenMath object 
      [... some examples ...]

*********** end old stuff, begin new stuff **************** 

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

The occurrences of the {\tt{OMR}} element must obey the following global
{\em{acyclicity constraint}}: An OpenMath element may not dominate itself.

Consider for instance the following (illegal) XML representation 

<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>

Here, the {\tt{OMA}} element with {\tt{id="foo"}} dominates its second
child, which dominates the {\tt{OMR}} element, which dominates its target:
the element with {\tt{id="foo"}}. So by transitivity, this element
dominates itself, and by the acylcicity constraint, it is not the XML
representation of an OpenMath element. Even though it could be given the
interpretation of the continued fraction 1/(1+1/(1+1/...)), this would
correspond to an infinite tree of applications, which is not admitted by
the structure of OpenMath objects described in section 3.

Note that the acyclicity constraints 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>

Here, the {\tt{OMA}} with {\tt{id="bar"}} dominates its second child, the
{\tt{OMR}} with {\tt{xref="baz"}}, which dominates its target {\tt{OMA}}
with {\tt{id="baz"}}, which in turn dominates its second child, the
{\tt{OMR}} with {\tt{xref="bar"}}, this finally dominates its target, the
original {\tt{OMA}} element with {\tt{id="bar"}}. So this pair of OM
objects violates the acyclicity constraint and is not the XML
representation of an OpenMath object.

*********** end new stuff ****************

--
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