Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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).

share|cite|improve this question
Could you just describe your approach instead of linking to code? – Kristoffer Arnsfelt Hansen Jan 18 '13 at 14:39
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 :) – Chad Brewbaker Jan 18 '13 at 22:08
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? – J.-E. Pin Feb 10 at 16:58
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. – Chad Brewbaker Feb 11 at 18:29

Your Answer


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

Browse other questions tagged or ask your own question.