4
$\begingroup$

I'm facing a mathematical structure that has everything of a Kleene algebra (S, +, ., 0, 1, *), except that the multiplication '.' is not right-distributive over the addition '+'.

http://en.wikipedia.org/wiki/Kleene_algebra

I reckon that it could be defined as a weakened version of Kleene algebra, where the semiring (S, +, ., 0, 1) is weakened to a (left) near-semiring, but I haven't found that description used anywhere until now.

http://en.wikipedia.org/wiki/Near-semiring

Is there a known name for such a structure, that could hint me to some literature ?

Thanks by advance,

Alex

$\endgroup$
  • $\begingroup$ I would call it something like 'left Kleene algebra'. But it doesn't really help in searching.. Can you share us some interesting features/properties/usage of these? $\endgroup$ – Berci Feb 19 '13 at 11:29
  • $\begingroup$ Well, I am formalizing a description language that mimics the structure of CFGs, but applied on an typed process space. My "alphabet" is a set of processes, the natural multiplication '.' is process composition, and the addition '+' is the parallelization of 2 processes. We also want to be able to "join" the results from two parallel processes if needed, and thus our processes are typed, and (a + b) is a process that outputs a Pair of results. Given a process 'c', we can maybe type (a + b).c or (a.c + b.c), but not both, which yields the contradiction to the right-distributive axiom. $\endgroup$ – Alex Repain Feb 19 '13 at 13:47
  • $\begingroup$ Also, I found mentions of "left-handed Kleene algebra", but the 'left-handed' part refers to the * axioms of the algebra, and not the distributivity in the semiring... As for the properties of the structure, if it already has been studied, that is what I am after ! $\endgroup$ – Alex Repain Feb 19 '13 at 13:50
3
$\begingroup$

Once I ran across Graphs, Dioids and and Semirings by Gondran and Minoux, and discovered it was a pretty well written book about such things.

I can't be positive it has exactly what you mention, but I remember it contained very detailed nomenclature for organizing generalizations of rings (for example: single-sided axioms, exactly as you are looking for). Since such generalizations have exploded in the past 40 years, and everybody chooses different names for stuff, the authors had a tough task of shoehorning everybody's terminology into a single comprehensible book. It is also pretty new, so I'd start there!

Another one I enjoyed was Golan's Semirings and their applications; however, it is much older, and I have even less confidence that it addresses exactly what you are interested in.

Good luck!

$\endgroup$
  • $\begingroup$ Thanks a lot for the pointers, Graphs, Dioids and and Semirings seems indeed to circumvent my field and explore it pretty extensively ; I'll have a peek at it! $\endgroup$ – Alex Repain Feb 20 '13 at 9:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.