Re: Algebraic extensions of semirings
- From: markwh04@xxxxxxxxx
- Date: 3 Mar 2007 00:44:33 -0800
On Feb 26, 5:00 pm, "Jamie" <jamievic...@xxxxxxxxx> wrote:
I am interested in algebraic extensions of commutative semirings.
Can somebody tell me why the literature almost exclusively seems to
deal with algebraic extensions of fields? What's so special about
them? We can write down polynomials over loads of other structures.
That's probably why you do NOT see much in that context: there's
nothing special about them.
Therefore, the appropriate venue would be closer to Universal Algebra
or even Category Theory.
The notion of algebraic extension (by which, in your context, free
extension) is quite generic. Take the bare structure of any algebraic
theory. This is a magma. A magma A is defined by a set of O of
operators and an "arity" function n: O -> {0,1,2,...}. This gives you
the skeleton of an algebra.
The free magma <X> associated with (O,n), and generated by a set X, is
one and the same as a "term language" over the operator set. The
elements of X play the role of indeterminates. The structure is
defined inductively by:
* X is a subset of <X>
* if o is an operator, n(o) = N; and t1,...,tN are terms in <X>,
then o(t1,...,tN) is a term in <X>.
The free extension of <X> by a (disjoint) set Y is just <X union Y>.
So, what you have when dealing with an algebraic theory is a magma
(O,n) and a system r of relations. The theory is equational if r can
be derived from a finite set of equational identities (e.g. for all x:
x = x + x). It is implicational if it can be derived from a finite set
of equational and/or conditional identities. An example of an algebra
defined by conditional identities is:
Equational axioms:
(ab)c = a(bc); a1 = a; 1a = a;
a0 = 0; 0a = 0; a(b+c) = ab+ac; (a+b)c = ac+bc;
a+a = a; a+b = b+a; a+(b+c) = (a+b)+c; a+0 = a;
a* = 1 + a a*
Conditional axioms:
a = a + ab --> a = a + a b*
a = a + ca --> a = a + c* a
(A Kleene algebra). The underlying magma has operators 0, 1, product
(denoted by juxtaposition), star and +; of arities, respectively, 0,
0, 2, 1 and 2.
Conway proved in the 1970's that this algebra is not equational.
An algebra defined by relations r is a magma (O,n)/r such is (O,n)
subject to the equivalence relations produced by the relation set r.
So, the free (O,n,r)-algebra generated by a set X would be <X>/r, the
free magma, subject to the equivalence relations. Denoting this
algebra A = <X>/r, then the free extension A[Y] by a set, Y, of
indeterminates (disjoint from X) would just be A[Y] = <X union Y>/r.
Thus, for instance, the free Kleene algebra generated by a set X is
equivalently described as the algebra R_X of regular expressions over
an alphabet X. This is proven in my "Algebraic Approach" series, in a
quite direct fashion by actually constructing the homomorphism
involved in the corresponding universal property.
Reference:
The Algebraic Approach to Formal Languages
Part 2. Kleene Algebras and Regular Expressions
http://federation.g3z.com/CompSci/index.htm#Algebraic2
Another example: the free commutative dioid generated by a set X is
just the family F(X*) of finite subsets of the free monoid X* (a dioid
is a semiring where addition is idempotent: x = x + x).
.
- Prev by Date: GNS and adjoint functors
- Next by Date: Re: GNS and adjoint functors
- Previous by thread: GNS and adjoint functors
- Next by thread: min and max
- Index(es):
Relevant Pages
|
