Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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? –  Todd Trimble Sep 26 '10 at 16:54
    
Yes to all those. –  decomwe Sep 26 '10 at 20:41
    
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 –  decomwe Sep 26 '10 at 20:48
    
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? –  user4977 Sep 27 '10 at 2:59
    
Oops. Getting myself muddled. Yes. Thankyou. –  decomwe Sep 27 '10 at 8:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.