[om] A Proposal for extending OpenMath with structure sharing

[jhd at cs.bath.ac.uk]

On Fri, 29 Mar 2002, Michael Kohlhase wrote:
> The core idea of structure sharing (DAG) representations is that the following two
> representations of terms are equivalent
> 
> 
>                   f                                f
>                  / \                              / \
>                 /   \                             \ /
>                /     \                             f
>               f       f                           / \
>              / \     / \                          \ /
>             f   f   f   f                          f
>            / \ / \ / \ / \                        / \
>            | | | | | | | |                        \ /
>            a a a a a a a a                         a
> 
This is an assumption. If 'f' is '-', and 'a' is '[-1,1]', then the
left-hand tree represents [-8,8], whereas the right-hand tree represents
0. There are some serious issues about OpenMath semantics here. This has
been debated before: Heidelberg said: 
  There was a discussion on sharing of
  sub-objects, and whether this should be part of the object layer. MG
  pointed out that the binary coding currently did support
  JHD pointed out that this could easily be handled by a system
  of labels (as in many LISP systems).  MG asked why {\tt LABEL} had to be
  special. SD subsequently pointed out that if {\tt LABEL} was instead an
  operator defined in a ``sharing'' CD, it would be possible for
  applications to state whether or not they supported sharing. JHD then 
  agreed. 
> ========================= THE PROPOSAL ===============================
> 
> To remedy this, I propose to add an optional attribute 'id' to the elements OMA,
> OMBIND, and OMATTR since they make up the term structure, and a new element 'OMR'
> with the xlink [1] attributes for simple links. Thus the object above would have
> the representation.
> 
> <OMOBJ>
>  <OMA>
>   <OMA name="t1">
I assume you mean 'id=' rather than 'name=' here.
>    <OMV name="f"/>
>    <OMA id="t11">
>     <OMV name="f"/>
>     <OMV name="a"/>
>     <OMV name="a"/>
>    </OMA>
>    <OMR xlink:href="t11"/>
>   </OMA>
>  <OMR xlink:href="t1"/>
> </OMOBJ>
> 
James Davenport
--
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