Home » forums » LtU Forum

A new look at multimaps

I've just finished a small article on multimaps which (among other things) defines an interesting recursive definition of numerals. Here is the abstract:

Ordinary maps must contain only single occurrences of their domain values, while multimaps may contain multiple occurrences of both domain and range values.
In this short article we relax the occurrence type to be of any type - if such type obeys some kind of number law. Because of this relaxation and because multimaps behave like numbers, multimaps can be the occurrence type of other multimaps.
We explore this idea with some sketchy code snippets and finish with a recursive multiple of nothing.

By Robbert van Dalen at 2012-11-18 23:03 | LtU Forum | previous forum topic | next forum topic | other blogs | 5072 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Why generalize multiplicity here?

Hmm. What's your goal with generalizing the multiplicity of a multimap entry? Your multimaps used to be sets of entries, and now they're not just generalized to multisets or weighted sets, but to sets whose weights can even be more multimaps. Where is this journey going?

In my own pursuits, I tend to reach for multisets for one of two reasons: Either I can't find a good notion of equality to use for sets, or I want the multiple occurrences to apply independently in some aggregate computation. You don't lack an equality operator; in fact, your approach presumably relies on equality in order to find matching occurrences and combine their multiplicity objects. So do you have some particular kind of weighted aggregation in mind instead?

By Ross Angle at Mon, 2012-11-19 05:41 | login or register to post comments

Abstract Chemical Machine

Indeed, I'm reaching for weighted aggregation with a hint towards biological computing. For instance, the abstract chemical machine (CHAM) relies on (non-deterministic) multiset rewriting, which can be easily extended to multimap rewriting.
I'm not sure where my journey will lead me to next, but I do like to think about this kind of generalisations. At least it has given me a nice notation for every conceivable type of container.

By Robbert van Dalen at Mon, 2012-11-19 08:18 | login or register to post comments

Look at hybrid sets too

They have a rather interesting mathematics; my colleagues and I have used them for symbolic domain decompositions.

By Jacques Carette at Tue, 2012-11-20 02:15 | login or register to post comments

binary relations?

I can follow your paper to some extend. There are claims that some operations are improved from exponential to linear complexity. Is that because of using hybrid sets, or are hybrid sets just a convenient abstraction?
Also, how easy is it to extend the definition of piecewise-defined functions to piecewise-defined binary relations?
[edit: added the last paragraph]

By Robbert van Dalen at Tue, 2012-11-20 16:20 | login or register to post comments

Relations

Regarding extending to relations, I have no idea, I never thought about it until now. I think the answer is 'it depends'; it would depend on what kind of operations you are doing to those relations. Note that the same was already true of functions: some operators (like +) work smoothly, while others (like *) required use to work considerably harder.

The exponential improvement is in terms of representation size: basically we can represent an exponential number of cases with a linear number of 'pieces'. To have this make sense, tracking multiplicity is crucial. I don't think that integers are necessarily the only way to track multiplicity, but they are definitely the most obvious way.

By Jacques Carette at Wed, 2012-11-21 01:57 | login or register to post comments

Wheels of multimaps

Regarding integers, I've just finished a post that introduces wheels as a multiplicity type. Wheels are like rational numbers but allow the denominator to be zero. This means that all multimap operations (including inverse) can be made total.

By Robbert van Dalen at Thu, 2012-11-22 16:35 | login or register to post comments

Meadows

I much prefer meadows as the closest equational theory to that of fields. These turn out to be the same as von Neumann regular rings.

By Jacques Carette at Fri, 2012-11-23 00:51 | login or register to post comments

Nice Read

But why not totalize with an extra element, as usual? This could be an interesting additional contrast given in a new paper.

By j4n bur53 at Tue, 2012-11-27 14:10 | login or register to post comments

Try it

and you'll see it does not work nearly as nicely. It gives a much nicer topology, but the arithmetic does not want to really 'work' that well, since it does not help you define 0/0, etc. So it really depends on whether you are trying to do algebra or topology, it seems that you can't get both at once.

By Jacques Carette at Thu, 2012-11-29 03:28 | login or register to post comments