The tag has no usage guidance.

learn more… | top users | synonyms

0
votes
0answers
19 views

Cache complexity of folds that have non-constant space

I'm looking for articles on the cache complexity of folds of non-constant space. My use case is Borwein's factorial algorithm. String concatenation would be a more extreme case. I'm aware of dynamic ...
7
votes
0answers
70 views

What is the optimal binary encoding of the elements of a monoid?

The Question Let $M$ be a finite monoid. Let $S$ be a generating set of $M$. Say we have a binary encoding of $S$ represented by $\phi:S \rightarrow A^*$ where $A = \{0, 1\}$. This encoding should ...
9
votes
2answers
683 views

Formal representation of an abstraction hierarchy

Introduction I'm writing my PhD thesis on Abstract Delta Modeling (ADM), an abstract algebraic description of modifications (known as deltas) able to act on products (as in 'software products'). This ...
6
votes
0answers
123 views

Complexity of Roman numeral evaluation

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