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

<p><a href="https://gist.github.com/4542999">https://gist.github.com/4542999</a></p>

<p>1) Is this a known result?</p>

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

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

CC BY-SA 3.0
2013-01-18T14:39:20.757Z
Could you just describe your approach instead of linking to code?
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2013-01-18T22:08:06.147Z
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
CC BY-SA 3.0
2016-02-10T16:58:39.703Z
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
CC BY-SA 3.0
2016-02-11T18:29:23.807Z
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
<kolmogorov-complexity><parallel><monoid><ds.algorithms>
Complexity of Roman numeral evaluation
Chad Brewbaker
# Complexity of Roman numeral evaluation

(Asked by: username_0 on 2013-01-17)

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

**Tags:** kolmogorov-complexity, parallel, monoid, ds.algorithms

> **Comments:**
> **username_1**: Could you just describe your approach instead of linking to code?  
> **username_0**: 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 :)  
> **username_2**: 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?  
> **username_0**: 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.  

---

## 0 answers

