By
Paolo Baldan University of Padova
Roberto Bruni Universtity of Pisa
A new social network has become extremely popular. It is called Feetbook. Users share stories, anecdotes and pictures about their feet. What is (especially) peculiar is that posts can be tagged to explain whether they refer to the left or right foot or both. This allows a user to follow a specific foot of another user, e.g., user A can follow the right foot of B but not the left one.
In order to organise a massive advertising campaign to influence the shoe market, a major shoe company appoints a consultant firm Oxford Synthetica (OS), in order to suitably profile Feetbook users. What OS is providing is a database including a set of users, the follower relation and an indication of which users have an analogous behaviour. The precise guarantee on the database is that it is the largest collection such that the following property holds:
| Say that A′ emulates A if whenever A follows the right (resp. left) foot of some user B then also A′ follows the right (resp. left) foot of some other user B′ such that B′ emulates B. Then one says that A and A′ have an analogous behaviour whenever each emulates the other. |
An expert of Oxford Synthetica thinks that the above description is complex and clumsy, and there is a much simpler equivalent one. He says that A doubly emulates A′ whenever if A follows the right (resp. left) foot of some user B then also A′ follows the right (resp. left) foot of some other user B′ such that B doubly emulates B′, and the same holds with the role of A and A′ exchanged. Then he claims that the concepts of having analogous behaviour and of doubly emulation are the same.
QUESTION: Are these notions really equivalent?
SOLUTION: No, in general they are not.
We can use a labelled graph to represent users habits. Nodes correspond to users and and there is an arrow from user A to user B labelled by a left (resp. right ) foot when A follows the left (resp. right) foot of B.
Then consider the following graph of user habits.
It is evident that user Mike emulates Joe. In fact, Joe only follows the left foot of Amy and Mike is also doing this (and clearly Amy emulates herself, as any user does). Moreover, also the converse holds, i.e., Joe emulates Mike and thus they have an analogous behaviour. In order to see this, first note that Sue emulates Pat since they both do not follow anyone. Then Amy emulates Tom, since the latter just follows the right foot of Pat and the former emulates this by following the right foot of Sue. We can conclude that Joe emulates Mike since the fact that Mike follows the left foot of Tom is emulated by Joe following the left foot of Amy.
However it is not the case that Joe doubly emulates Mike. To see this, first note that Tom do not doubly emulate Amy (in fact, Amy follows the left foot of Alex, while Tom only follows the right foot of Pat). Then, while Mike follows the left foot of Tom, note that Joe does not follow the left foot of any user that doubly emulates Tom.
FINAL REMARKS
In the area of concurrency theory, the above is a well-known difference between simulation relation (what we have called emulation here) and bisimulation relation (what we have called double emulation).
A brief survey on Logic Programming Encodings of Bisimulation can be found in:
Agostino Dovier: Logic Programming and Bisimulation. ICLP 2015 (technical communication)