Composition and problems with labels

[Martin Rubey]

Dear Ralf,

I continued to work on the multisort species, but now I have the following
design problem:

a crucial step in producing the isomorphism types for the composition FoG is to
produce a multiset of isomorphismtypes of G, each structure having the same
cardinality. For example, suppose we are given labels {1,2} and {3,4}, and G
is the species of graphs. We have two isomorphismtypes, namely the graph with
one edge and the graph without edges. We now want to obtain three different
sets, each containing two structures: (omitting many braces)

1 3 1 3 1 3
| | , | ,
2 4 2 4 2 4


Allowing repeated labels this is straightforward: I produce the
isomorphismtypes of G[1,1], and then produce a multiset-composition of the
result. If all labels have to be distinct, I would have to relabel the
structures, i.e., I would do it as follows:
1 1
isomorphismTypes([1,2])$G returns | and
2 2

multiset composition thereof returns

1 1 1 1 1 1
| | , | ,
2 2 2 2 2 2

relabel the structures to obtain

1 3 1 3 1 3
| | , | ,
2 4 2 4 2 4


Do we really want to do this?

Martin


-------------------------------------------------------------------------
This SF.net email is sponsored by DB2 Express
Download DB2 Express C - the FREE version of DB2 express and take
control of your XML. No limits. Just data. Click to get it now.
http://sourceforge.net/powerbar/db2/

[Ralf Hemmecke]

Post by Martin Rubey
Dear Ralf,
I continued to work on the multisort species, but now I have the following
a crucial step in producing the isomorphism types for the composition FoG is to
produce a multiset of isomorphismtypes of G, each structure having the same
cardinality.

I cannot quite follow. What is an "isomorphismtype" for you? Earlier and
also in your branch iso-experiments you do not use my view that
isomorphismtypes should be represented as representatives of eqivalence
classes. So not knowing which view you take I cannot say something precise.

Post by Martin Rubey
For example, suppose we are given labels {1,2} and {3,4},

Do you want to say {1,2} is *one* label?

Sorry, but I don't understand your mail. Maybe we should discuss this on
Wednesday.

Ralf

-------------------------------------------------------------------------
This SF.net email is sponsored by DB2 Express
Download DB2 Express C - the FREE version of DB2 express and take
control of your XML. No limits. Just data. Click to get it now.
http://sourceforge.net/powerbar/db2/

[Martin Rubey]

Post by Martin Rubey
Dear Ralf,
I continued to work on the multisort species, but now I have the following
a crucial step in producing the isomorphism types for the composition FoG is to
produce a multiset of isomorphismtypes of G, each structure having the same
cardinality.

I cannot quite follow. What is an "isomorphismtype" for you? Earlier and also
in your branch iso-experiments you do not use my view that isomorphismtypes
should be represented as representatives of eqivalence classes. So not knowing
which view you take I cannot say something precise.

Sorry. I tried to port my composition and multi partition algorithms to the
multisort context.

Post by Martin Rubey
For example, suppose we are given labels {1,2} and {3,4},

Do you want to say {1,2} is *one* label?

No, {1,2} should become the labels of the first isomorphism type and {3,4} the
labels of the second.

Sorry, but I don't understand your mail. Maybe we should discuss this on
Wednesday.

Yes, that's probably better. Only, I'm afraid we will run out of time...

Martin


-------------------------------------------------------------------------
This SF.net email is sponsored by DB2 Express
Download DB2 Express C - the FREE version of DB2 express and take
control of your XML. No limits. Just data. Click to get it now.
http://sourceforge.net/powerbar/db2/

[Ralf Hemmecke]

Post by Martin Rubey

Post by Ralf Hemmecke

Post by Martin Rubey
For example, suppose we are given labels {1,2} and {3,4},

Do you want to say {1,2} is *one* label?

No, {1,2} should become the labels of the first isomorphism type
and {3,4} the labels of the second.

After that I could approximate what you were trying to convey by your
first mail.

Post by Martin Rubey
Dear Ralf,
I continued to work on the multisort species, but now I have the following
a crucial step in producing the isomorphism types for the composition FoG is to
produce a multiset of isomorphismtypes of G, each structure having the same
cardinality. For example, suppose we are given labels {1,2} and {3,4}, and G
is the species of graphs. We have two isomorphismtypes, namely the graph with
one edge and the graph without edges. We now want to obtain three different
sets, each containing two structures: (omitting many braces)
1 3 1 3 1 3
| | , | ,
2 4 2 4 2 4
Allowing repeated labels this is straightforward: I produce the
isomorphismtypes of G[1,1], and then produce a multiset-composition of the
result. If all labels have to be distinct, I would have to relabel the
1 1
isomorphismTypes([1,2])$G returns | and
2 2
multiset composition thereof returns
1 1 1 1 1 1
| | , | ,
2 2 2 2 2 2
relabel the structures to obtain
1 3 1 3 1 3
| | , | ,
2 4 2 4 2 4
Do we really want to do this?

I don't want this. I don't think it is good or even necessary to return
something like

Post by Martin Rubey
multiset composition thereof returns
1 1 1 1 1 1
| | , | ,
2 2 2 2 2 2

MultisetComposition should return a *representative* of an isomorphism
type and therefore all labels would be different right away. There
should be no need to do relabelling (which would be impossible anyway
since you cannot distinguish the first 1 from the second 1).

Ralf

-------------------------------------------------------------------------
This SF.net email is sponsored by DB2 Express
Download DB2 Express C - the FREE version of DB2 express and take
control of your XML. No limits. Just data. Click to get it now.
http://sourceforge.net/powerbar/db2/