Re: CYK & Context-Free Expressions

On Apr 28, 12:58 pm, Tegiri Nenashi <TegiriNena...@xxxxxxxxx> wrote:
On Apr 28, 12:58 pm, Tegiri Nenashi <TegiriNena...@xxxxxxxxx> wrote:
BTW, speaking of trees, what is algebraic definition of tree
structure?

An element of a free magma.

A magma is an "algebra without axioms". That is, it's an algebra
comprising a signature plus no axioms. So the magma generated freely
from a set X is the same thing as the term language over the same
signature with members of X as its indeterminates.

The archetypical example of a magma is the one which has just one
operator -- a binary operator. The elements of this magma are then
binary trees.

Interesting cases arise if you start to consider magmas that are not
free; particularly those which admit solutions to fixed point
equations.

These constructs (forests,"node packing", etc) are too awkward to
genuinely believe for them to be the answer...

In large measure that's what motivated my movement a long time ago
away from tree/forest based formalisms in favor of a more algebraic
approach. You can clearly see the imprint of this, for instance, in
the REX regular expression utility (in comp.compilers), which
interestingly has had its underlying algebraic method translated in a
wide range of settings (perl, Prolog, XML-Schema).
.

Relevant Pages

  • The Magic Algebra -- The Algebraic Approach to Control Flow Analysis
    ... Control Flow by Infinitary Expressions ... Multiple Objects and the Extended Magic Algebra ... what's known as a MAGMA. ... For assignment statements involving simple variables, the context ...
    (comp.compilers)
  • Re: CYK & Context-Free Expressions
    ... A magma is an "algebra without axioms". ... comprising a signature plus no axioms. ... and binary trees as elements. ...
    (comp.theory)
  • Re: CYK & Context-Free Expressions
    ... going to Earley, however, let's stop at the CYK method for a moment. ... For each grammar a kind of universal CYK grammar formed along these ... A magma is an algebra consising of a signature subject to no axioms. ...
    (comp.theory)
  • Re: Algebraic extensions of semirings
    ... deal with algebraic extensions of fields? ... the appropriate venue would be closer to Universal Algebra ... This is a magma. ... subject to the equivalence relations produced by the relation set r. ...
    (sci.math.research)
  • Re: What is a Complete Algebra!?
    ... Does the rank of supporting algebraic structure help in this!? ... I mean is an algebra based on a magma less complete than an algebra defined on a ring!? ...
    (sci.math)