Take the 2-minute tour ×
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.

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

https://gist.github.com/4542999

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|improve this question
1  
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
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

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.