I came up with a result the other day that arbitrary length Roman numeral evaluation can be modeled as a monoid:


1) Is this a known result?

2) If not, any suggestions of a niche journal that might be interested in such a submission?

3) Any known results on the space complexity of finite monoid elements? I have yet to come across a monoid representation with efficient parallel computation that took more than O(log N) space, with N being the number of elements being "added"/"multiplied". Useful monoid data structures seem to be a constant number of counters or a member of a transformation semigroup of constant size; i.e. a fixed length array of size K with elements in 0...(K-1).

  • 2
    $\begingroup$ Could you just describe your approach instead of linking to code? $\endgroup$ Jan 18 '13 at 14:39
  • $\begingroup$ By default treat all characters as additions. Bind the sign of a repeated character when enough information about it's suffix is known and subtract if needed. For more info see the code :) $\endgroup$ Jan 18 '13 at 22:08
  • 1
    $\begingroup$ A monoid is a set equipped with an associative operation and an identity. In your case, could you please explain formally what is the set, what is the associative operation and what is the identity, without referring to the code? $\endgroup$
    – J.-E. Pin
    Feb 10 '16 at 16:58
  • $\begingroup$ The monoid is a string of Roman numeral collapsed to a debit/credit value, plus some metadata about if all the characters are the same, and some info about what the first and last character are. Really do have to look at the code. Primally, a finite state plus a counter. There are rules on how two of theses objects are merged. I should formally write out the finite state transitions when I get time. $\endgroup$ Feb 11 '16 at 18:29

Your Answer

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

Browse other questions tagged or ask your own question.