6
$\begingroup$

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

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Could you just describe your approach instead of linking to code? $\endgroup$
    – Kristoffer Arnsfelt Hansen
    Jan 18, 2013 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$
    – Chad Brewbaker
    Jan 18, 2013 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, 2016 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$
    – Chad Brewbaker
    Feb 11, 2016 at 18:29

0

Reset to default

Your Answer

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