Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

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.