4
$\begingroup$

How many finite idempotent semirings (dioids) are there of order n?

And how many have an addition operation that coincides with a maximum operation for some ordering of the elements ?

Even if the exact numbers aren't known, what bounds are there?

As per Todd's comment: underlying additive structure is a commutative monoid, the underlying multiplicative structure is a monoid, and multiplication distributes over addition?

Idempotent means the addition satisfies a+a=a.

Multiplication is not necessarily commutative. (Correspondence principle for idempotent calculus and some computer applications. G. L. Litvinov and V. P. Maslov)

Also the statement a*0=0 has to be stated as it is independent of the others (M. A. Shubin (1992), "Algebraic remarks on idempotent semirings and the kernel theorem in spaces of bounded functions’" in books.google.com/books?&id=ZoxXoYoZuo0C&oi=fnd&pg=PA151)

Dioids are described as plentiful in "An Introduction to Idempotency" Jeremy Gunawardena

They are ennumerated for some special cases in J. H. Conway. Regular Algebra and Finite Machines. Chapman and Hall, 1971, Chapter 12

Improve this question
$\endgroup$
8
  • $\begingroup$ Do your semirings have a multiplicative identity? So in other words, do you mean the underlying additive structure is a commutative monoid, the underlying multiplicative structure is a monoid, and multiplication distributes over addition? $\endgroup$
    – Todd Trimble
    Commented Sep 26, 2010 at 16:54
  • $\begingroup$ Yes to all those. $\endgroup$
    – decomwe
    Commented Sep 26, 2010 at 20:41
  • $\begingroup$ These idempotent semirings without any further restrictions are described as a vast class by M. A. Shubin (1992), "Algebraic remarks on idempotent semirings and the kernel theorem in spaces of bounded functions’" in books.google.com/books?&id=ZoxXoYoZuo0C&oi=fnd&pg=PA151 $\endgroup$
    – decomwe
    Commented Sep 26, 2010 at 20:48
  • $\begingroup$ Regarding your second question: Do you mean to ask how many have an addition which doesn't come from a max operation? I ask because I am really only familiar with the semiring one gets by using "max" as the addition and "plus" as the multiplication on the reals. However, if this is your intended question, then the answer may be zero. Also, have you looked at any of Golan's texts on semirings? $\endgroup$
    – user4977
    Commented Sep 27, 2010 at 2:59
  • $\begingroup$ Oops. Getting myself muddled. Yes. Thankyou. $\endgroup$
    – decomwe
    Commented Sep 27, 2010 at 8:48

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .