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

$\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
    Sep 26, 2010 at 16:54
  • $\begingroup$ Yes to all those. $\endgroup$
    – decomwe
    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
    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
    Sep 27, 2010 at 2:59
  • $\begingroup$ Oops. Getting myself muddled. Yes. Thankyou. $\endgroup$
    – decomwe
    Sep 27, 2010 at 8:48

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.