Catherine Quiminal

Work Package 3 Migrants and Borders -Guideline

Keywords: Migrations, Europe, representations, methodology, interviews guideline Migrations, Europe, représentations, méthodologie, guide d'entretien Cover: African migrations toward Europe

This paper presents the methodological guidelines of the interviews performed in the framework of the EuroBroadMap project. Three types of migrants were targeted by the different surveys: future migrants, 'transit' migrants, and migrants already living in Europe. Among the topics investigated, two were of particular interest in this program: representations of Europe and/or of European Union, and the way it evolves as the migration project is realised.

Common methodology

The methodology is based on a qualitative socio-anthropological approach of the representation of Europe and of the World of potential migrants, 'en route' migrants, successful and unsuccessful migrants toward Europe.

The team involved in this Work Package has a great experience in the field of socio-anthropological approach related to migrants mainly between Africa and France, Argentine and France, and are very familiar of the analyse of migratory journey.

In the framework of a research effort that focuses on the representations that migrants have constructed and will further diffuse about Europe, researchers will rely on informal discussions, non-directive talk, and the compilation of narratives about migrant trajectories, linked with the objectives in which migrants are engaged. The research teams will also take the benefit of in situ observation of places and networks of sociability, and the exchange of information about migratory spaces. The data collected will make possible an evaluation of the changing representations of Europe as a territory of destination, circulation, installation and/or expulsion, for the different situations of origin, transit and destination. The protocol of the survey has been established in order to capture these different representations according to social characteristic, cultural background, age or gender. For this reason, the panel will be carefully established with equal proportions, when it is possible, according to gender, age and social groups. To fulfil these objectives and obtain a sufficiently diversified and representative sample, the teams responsible for the surveys will rely on existing contact with migrants, NGOs, associations and with the actors from the 'sociability' places (cultural centres, meeting places churches, 'confreries', internet cafes, squats, etc.).

In each case, the rules of deontology will be strictly followed: non-implication and scientific distance, anonymity of the survey for both peoples and places, non-divulge of information that could provoke prejudice against the people investigated.

Main research questions

Three situations/moments of the migratory process will be taken into consideration in order to understand how migrants and potential migrants' visions of Europe change along the temporality of their trajectories. Such situations/moments are potential migration, transit migration and settlement in Europe.

Our hypothesis is that the collected visions of Europe will necessarily be ambiguous and ambivalent. Both the image of the European Union as an Eldorado and the image of the EU as a place of suffering and exclusion will probably coexist within peoples' narratives. Such contradictory visions are coherent with what anthropologist Marc Augé calls 'the condition of supermodernity' of the contemporary world1 . Different difficulties may arise through the research process. The first one regards the ordinary confusion between Europe as a geographical space with its more ore less blurred borders, and the European Union as a political space in construction with its evolving borders. In each interview we will have to understand how this twofold vision is constructed and how to interpret it in relation to each person's trajectory.

Another difficulty is that one should not take for granted that the EU is necessarily a meaningful concept for immigrants. Most probably, their vision and knowledge are limited to a country or a city. This question is particularly relevant for non-EU citizens as the EU is not yet a free settlement space for them (but only, within the Schengen borders at least, a free movement area).

It is also important to take into account the long history of relations between sending and settling countries (slave trade, colonization, world wars, colonial wars, Russian domination. . . ). Such a long history, together with contemporary international relations, has produced in people's imagination a memory of Europe and Europeans as well as a memory of European languages. The analysis of such a memory is particularly heuristic for approaching immigrant's visions of Europe and the Europeans as well as their visions of Europe's cultural productions.

Vernacular categories that have been used in the past to qualify Europeans and their countries, the Europeanized autochthons ('evolved', 'civilized', 'assimilated') as well as different categories of immigrants and their descendants in Europe (students, workers, different kinds of elites: political, intellectual, sport, technical, artistic. . . ) will be analysed. Such evolving categories, because they reveal the evolutions and changes that occurred in the relationships between sending countries and Europe/the European countries, are useful for a better understanding of the origins and the vehicles of visions of Europe. The analysis of such categories indeed contributes to highlight evolving forms of circulation between spaces, the nature of groups and individuals, as well as the kind of projects that contribute to the framing of people's movements. Such categories, by showing the evolutions and changes within mentalities, contribute also to reveal and construct a living history of Europe and the Europeans. They contribute to highlight collective memories or sporadic memories, representations of Europe, of Europeans and European countries. They introduce us to the 'contemporaneity' and intimacy of everyday experiences of both the working classes and the elites.

Europe and Europeans are also defined through a 'cultural baggage' made of languages, religions, ways of living. . . The attitude of immigrants, of immigrants returning home for holidays, and of potential immigrants towards such a 'cultural baggage', may reveal many aspects of their vision of Europe.

Our investigation will cover three main directions: the vehicles of the representation of Europe, Europe as a political space, Europe as a socioeconomic space. Three main directions concerning four situations. We have elaborated three guidelines corresponding at those situations (see Appendix) These guidelines are more than we said in French 'pense bête' than a list of obligatory questions.

Research topics

What follow are not properly guidelines for the interviews, but rather a selection of indicators that can be useful in order to understand immigrants' representations, knowledge and practices of Europe and the EU.

Europe (and the EU) will be considered as a political space, as a working space, as a transit space, as a settlement space. . . Topics such as social networks, the knowledge and the use of borders, the given and the circulating images of Europe will be further elaborated.

We organize our investigation from three major clusters congruent with our objective: the vectors of representations, the Europe as a political space, Europe as a socio-economic space.

Vectors of representations

What is the image and the information that is given about Europe in the home country / transit country / settlement country? By whom: the media / the institutions (embassies, universities, cultural centres, etc.) / eximmigrants / migrants returning for holiday / deported people / dismissed asylum seekers, etc.?

Europe as a political space

Europe as a political space: the European migration policy /policies (how is it/they are perceived, constructed, looked at). What is the knowledge of the European migration policy and what are the strategies of immigrants regarding specific features such as visas, the entrance policy, the police, the European social policy for immigrants, contracts (seasonal or others), political opportunities, the idea of Europe as a fortress, asylum and humanitarian aspects, family reunion opportunities, EU third country migration policies, residence permit and possible circulation within the EU space of democracy?

Europe as a social and economic space

Europe as a social and economic space: social rights, employment opportunities, internal and international mobility opportunities, host country policies, living conditions, knowledge of Europe as a working and a living space, racism, ethnic relations, women status. The issue of borders and detention camps (which knowledge and which experience) will also be tackled.

Some methodological precisions

During the survey, particularly during the interviews, the relevance of Europe as a category will be questioned and confronted to other categories such as Occident, nation, city, working places, economic areas, etc. Interviewees will be chosen in order to diversify destination and settlement countries in Europe. Interviewers will have to collect an as much as possible diverse sample of interviewees regarding their age, sex and education level.

At the beginning of the interviews, the concept of Europe will not be mentioned (neither notions referring to specific countries such as France, Italy and so on) in order to understand whether it is a meaningful / operational category for the interviewees. The interviews will try to grasp what is the reality of Europe and the EU within migration strategies as well as when and under which conditions it is evoked. Then, in a second part of the interviewing process, questions will be more specifically focused on Europe (knowledge, perception, practices, etc.).

The following questions will be addressed: how does Europe become a destination choice for future immigrants? How do immigrants perceive migration constraints and opportunities? How do contradictory and ambiguous imaginaries merge within the decision to engage in a migration path towards Europe? As regards migrants staying in the transit areas, we will try to understand whether the interruption of their migratory journey, as well as their detention condition, have changed their visions of Europe. For immigrants who already settled in Europe, we will try to understand the meaning of Europe and the European Union from the perspective of their integration or exclusion situation.

How is Europe divided by immigrants between transit / circulation / installation / residence spaces and into specific economic spaces in order to answer to their specific strategies?

Which knowledge of European languages? Europe as compared to other places (possible competitors of similar places): USA, Canada, etc.

Which knowledge of the European geography? Europe seen as a freedom space, as an entertainment space?

The perception of Europe as a space of racism

The perception of Europe's inhabitants, of Europeans, of Europe's national / ethnic / regional groups. . .

Categories and notions that are used to refer to Europe, Europeans, immigrants working in Europe, returnees.

Memory of a common history with Europe: slavery, colonization, wars, Russian domination. . .

Agenda

Analysis of Europe as a category that evolves along the migration trajectory (places, projects, networks, social profile of immigrants. . . ). The research will focus on the specific places in which migrants trajectories take place (home country, transit country, borders, settlement places, etc.). This will allow possible comparisons between the different fields.

Four types of populations will be investigated:

•

Appendices

Transit situations

Guidelines for the interviews

Please note that this is a draft. It has to be discussed with the IRMCo team, and it has to be tested. The researcher introduces him/herself and makes a brief presentation of the research project without referring directly to Europe. For example, s/he can say that s/he is interested in people's migratory projects and trajectories. The researcher makes clear to the interviewee that what s/he will say will be strictly confidential and that his/her anonymity will be preserved. If necessary, the name of places will also be changed.

General information about the interviewee's origins and family

Before asking you about your migratory path, we would like to know more about your life in you country of origin, your family of origin, and your own family.

Family of origin

Could you describe me your family of origin: how many members? Do you have brothers and sisters? Are you the younger / the older one / in between? What kind of job do they do? How would you define the economic and social situation of your family of origin (in comparison to the average situation in your country of origin)? Did your parents ever change their home or their job? Which language did you speak at home? (If the parents are still alive) Where do they live: in your country? abroad? where? What kind of education did they receive? What kind of education did your brothers and sisters receive (level, religious / not religious, specialization, private / public. . . )? What kind of job do they do now? The mobility path of the parents / brothers and sisters: did they ever move to another country / to another place in the country? If yes, where to? Does anybody have a foreign citizenship in your family of origin? In case someone has a foreign citizenship, what kind of use do they make of their citizenship (vote, travel. . . )?

Family

Are you single / married / else? Do you have children? How many members are there in your family? How would you describe your socio-economic situation in your country of origin (in comparison to the average situation)? Did you rent / own an apartment / house? Did you have a car? Did you have television? Telephone? Internet? Who was managing the family budget? Which language did you speak at home? Children: if you have children, where do they live now? Who takes care of them? Does anybody have a foreign citizenship in your family? In case someone has a foreign citizenship, what kind of use do their do of their citizenship (vote, travel. . . )?

Life in the home country

The building of the migratory project in the country of origin

Now I will ask you a few questions about the reasons why you decided to leave your country.

The decision

For which reason did you decide to leave your country (find job opportunities, political reasons, holiday, study, love. . . )? How long did you prepare your journey? With whom (people that are involved in the journey or in the project, people that helped to organize the journey)? How did you get the information to prepare your journey? When did you eventually decide to leave?

Socialization to Europe and socialization to migration

Did you ever go abroad before this journey? Where? For which purpose? Did anybody from your family moved abroad before you? If yes, who? Where? Why? What did they tell you about the place? What did they tell you about the country? What did they tell you about Europe (if the place is in Europe)? Did anybody from your friends moved abroad before you? Who / where / why? What did they tell you about the place / country / Europe (if in Europe)? Did you tell anybody about your project? How did your family react to your project? How did you friends react to your project? When you planned to go abroad, where did you want to go (country, region, city. . . )? Why? How and where (cultural centres, embassies, media, associations. . . ) did you get information about this place? How did you think you would reach this place (perceptions of borders)? Do you know anybody in this place? What do you expect from this place? How do you imagine people in this place? More broadly, what do you expect from Europe? From Europeans? What are the image and the information that are given about Europe in your home country? By whom (cultural centres, embassies, media, associations. . . )? Did you consider going to other places (North America for instance) than Europe? Why? Why didn't you choose this place?

Malta

If the place you planned to reach is not Malta: did you plan to go through Malta during your journey? If not, how did you happen in Malta? Did you have any contact here? Did anybody wait for you here? Did you ever hear about Malta before coming here? How did you figure out life here? What did you know about migration regulation and immigrants' situation here?

The migratory path

Now I will ask you about your journey from your homeland to Malta.

Could you please describe your journey, from your homeland to Malta? Was it dangerous? Did you move alone or with other persons? Which borders did you cross? What kind of papers did you have when you left your home country? Did you have to pay someone to get some papers / to pass the borders / to cross a country? How much money did you need for your trip? Did anybody help you to get this money (friends, intermediaries, family. . . )? During the journey did you have to change your itinerary? Did you have to change your plans about the destination place? Why? Who helped you to reach Malta? During your migratory path, did you change your mind about your projects? When? How did you feel about it? How many languages do you know (read/talk/write)? How many of them did you know before leaving your country? Do you think this knowledge has been helpful / unhelpful during your migratory path? Do you think it will be helpful in the future? How?

Life in Malta

Now let me ask you a few questions about your current situation in Malta. Tienen familia en los paises dont vient ta famille ? Avez-vous déjà fait des voyages là-bas ? Accueillez-vous ou votre famille des "parents" ou amis de ce pays en Argentine ? Avez-vous des liens autres avec ce pays (pratiques sportives, actualité, littérature, cinéma, amitiés virtuelles, projets. . . )?

Your current situation and everyday life

Pratiques socioculturelles / mémoire migratoire familiale (enfance -adolescence)

Langues parlées à la maison ? Pratiques socioculturelles familiales : on mange quoi chez vous ? On fête quoi ? Comment ? Scolarisation : école bilingue ? école communautaire ? Tes parents (grands-parents / oncles, tantes) ont-ils des amis originaires du même pays ? D'autres lieux migratoires ? Que font-ils ? Comment était ta vie là-bas ?

Vers la migration

Que connaissais-tu de l'Europe là-bas ? Comment (quel biais) ? Par rapport aux États-Unis ? Que connaissais-tu de la législation européenne par rapport à l'immigration ? Et que connaissais-tu des migrants en Europe ? Avais-tu des amis, de la famille en Europe ou qui ont déjà été en Europe ? Si oui, où ?

On the road

Projet migratoire

Pourquoi es-tu parti ? Quand as-tu songé à partir la première fois ? Comment as-tu préparé le voyage ? Quelles infos ? Quelle aide ? Quelle a été la réaction des parents et de la famille ? Réactions des amis ? Quelles étaient tes attentes de ce voyage ? Pensais-tu qu'il te serait plus facile de travailler ? Mieux gagner ta vie ? Meilleures études ? Rencontrer plus facilement des femmes / hommes ? Pouvoir être plus libre ? etc.

Réalité migratoire

Comment ça s'est passé depuis ton arrivée ? As-tu eu des difficultés, des problèmes, des moments durs durant cette migration ?

  Migration candidates in the home country: Cameroon (J.-Y. Blum Le Coat with A. Bopta and M. Tchindjang, January 2010), Mali (C. Quiminal, September 2009), Argentina (P. Gonzalez, F. Jedlicki) and India (M. Thapan). • Deported migrants: Congo-Brazzaville (J.-Y. Blum Le Coat, February 2010). • Transit migrants: Morocco (A. Pian, September 2009), Senegal (M. Timera), Malta (IRMCo team and C. Schmoll, October 2009), and Romania (Tigris team). • Migrants in Europe : Italy, Malta (C. Quiminal, M. Timera, C. Schmoll, and M. Thapan, 2010).

  What is your current legal situation? Do you expect and how to you expect it to change? How would you describe your everyday life in Malta? Do you have any friends? Do you have any family here? Do you have any connections with co-ethnics? Do you have any connection with your homeland (TV, mail, internet, telephone, send / receive money. . . )? Do you have any connection with your place of destination (TV, mail, internet, telephone, send / receive money. . . )? During your free time: Do you see friends / family? Do you read? What do you read? Do you watch TV? What do you watch on TV? Are you involved in associations or NGO activities? Do you participate to collective religious activities? Do you pray? Malta and the Maltese Do you know some people from Malta? Do you have friends here? How would you describe Maltese people? Would you describe Malta as a welcoming / non welcoming place? Why? What do you like/unlike here? Do you consider Malta as a European country? Could you compare Malta to other places you know / to the place you planned to go (if not Malta)? Could you compare Malta to Europe as a whole: would you say the situation in Malta reflects the situation of Europe or not, why? Do you know / have you heard of any similar place as Malta in Europe or elsewhere? Could you compare Malta to other places in Europe? Do you think it makes a difference to be in Malta or to be in another place in Europe (as regards job opportunities, migration regulation, people's behaviour towards immigrants. . . )? What do you think about immigration policy (do not specify Malta or Europe)? If the person is in a detention centre How long have you been staying here? How long do you think you will stay? Do you have connections with outside? Did you have any other experience in detention camps? What is your position towards detention camps? Who do you think is to be blamed about the situation in detention camps? Do you think that the situation of immigrants here in Malta reflects their situation in Europe? Why? Could you compare Europe to other possible destination countries (USA, Canada)? Do you think of Europe as a place where people can be freer than elsewhere? Do you think of Europe as a place where people can have more opportunities? Do you think of Europe as a place of racism? Why? Do you think racism and xenophobia are everywhere the same in Europe? Did you ever think about returning to your homeland? What do you think of people that decided to return? Relation avec le lieu d'origine migratoire familial, ou des lieux d'origine migratoire

	Argentina situation
	Guidelines for the interviews (exists in French, Spanish and
	Italian)
	Questions d'État civil
	Sexe, date de naissance, lieu de naissance
	Nationalité
	Situation familiale
	Niveau d'études
	Expériences professionnelles
	Résidence (domicile personnel, familial, autres)
	Veux-tu que nous parlions d'abord de la migration ou de l'Argentine, avant
	le départ ?
	En Argentine
	Origines familiales
	Généalogie et mémoire familiale : dresser un arbre généalogique familial
	(nationalité, âge approximatif, ville / pays de résidence, qualification, métier)
	le nom de leurs parents, grands-parents jusqu'au primo arrivant dans la
	République Argentine.
	D'où (comment? quand?) sont venus les migrants en Argentine de la
	famille ? Autres mobilités inter-Argentine ?
	Nationalité
	Nationalité des parents / grands-parents (quel est le premier à être devenu
	argentin, comment ?)
	Usages de la nationalité : vote ? Recours à des services sociaux ? À des
	programmes pour les émigrants ?

'Supermodernity' -he writes -'is driven by a process of acceleration of history, a contraction of space and an individualization of people's references', M. Augé, 1994, p.157.

If the person is working in Malta

Could you describe your job here? How did you find it? Who are you working for? Who is working with you? Do you think that there is a fair balance between you qualification and your job? What are your professional projects?

Current Migratory Project

Now that you are in Malta, did your migratory project change compared to what was planned in your homeland? Where do you not want to go? Why? Where do you want to go (place, region, city)? Why?

If the place is different from the one described in 3 (migratory project) How did you get information about this place? Do you know anybody there? What do you expect from this place? How do you imagine people in this place? How do you think you will reach this place (perceptions of borders, perception of the implementation of migration policies. . . )? How did you change your mind about your destination place?

If the place is the same than the one described in 3 Did you get new information about this place during your journey? Did you get new information about this place here in Malta? Do you think there are good opportunities for regularization in this place? Do you think there are good working opportunities? Do you think there would be opportunities for your family to join you? Do you think there are good opportunities for finding friends / finding a partner? What kind of professional project do you have in this place? Do you think your life there will be much more different from you life here? If yes, how? Do you think about other places where there could be good opportunities? Where? Why? What kind of opportunities? What do you think about European policy on immigration? Do you think it may impede you to realize your migratory project?

Visions of Europe

This is the last part of the interview. Let me ask you a bit more about your projects and your vision of Europe.

Could you compare the place you want to go to other places in Europe? Do you think there are important differences between those places (as regards job opportunities, migration policy and policy implementation, people's behaviour towards immigrants. . . )? Would you describe Europe as a welcoming place? Why? What are, according to you, the good and the bad sides of Europe as a destination?


C S Haar

Christian Kern

Stefan Schwoon

Stefan Haar

Computing the Reveals Relation in Occurrence Nets

Keywords: Structure and behaviour of Petri Nets, partial-order theory of concurrency, automatic analysis

Petri net unfoldings are a useful tool to tackle state-space explosion in verification and related tasks. Moreover, their structure allows to access directly the relations of causal precedence, concurrency, and conflict between events. Here, we explore the data structure further, to determine the following relation: event a is said to reveal event b iff the occurrence of a implies that b inevitably occurs, too, be it before, after, or concurrently with a. Knowledge of reveals facilitates in particular the analysis of partially observable systems, in the context of diagnosis, testing, or verification; it can also be used to generate more concise representations of behaviours via abstractions. The reveals relation was previously introduced in the context of fault diagnosis, where it was shown that the reveals relation was decidable: for a given pair a, b in the unfolding U of a safe Petri net N, a finite prefix P of U is sufficient to decide whether or not a reveals b. In this paper, we first considerably improve the bound on |P|. We then show that there exists an efficient algorithm for computing the relation on a given prefix. We have implemented the algorithm and report on experiments.

Introduction

Petri nets (see e.g. [START_REF] James | Petri Net Theory and the Modeling of Systems[END_REF][START_REF] Murata | Petri nets: Properties, analysis and applications[END_REF]) and their partial-order unfoldings [START_REF] Kenneth | Using Unfoldings to Avoid the State Explosion Problem in the Verification of Asynchronous Circuits[END_REF][START_REF] Esparza | An Improvement of McMillan's Unfolding Algorithm[END_REF][START_REF] Khomenko | Canonical Prefixes of Petri Net Unfoldings[END_REF] have long been used in model checking. Their crucial feature is the partial-order representation of concurrency, allowing to escape from the state-space-explosion problem that is brought about by the use of interleaving semantics [START_REF] Fabre | Partial Order Techniques for Distributed Discrete Event Systems: Why You Cannot Avoid Using Them[END_REF].

In this paper, we will focus on the problem of determining the following relation: an event a is said to reveal another event b iff, whenever a occurs, the occurrence of b is inevitable. This does not imply that a and b are causally related (though they may be); in fact, b may have occurred before a, lie in the future of a, or even be concurrent to a. To some degree, this relation is complementary to the well-known conflict relation: a and b are in conflict if the occurrence of a implies that the occurrence of b is impossible. Notice however that the conflict relation is symmetric while reveals is not.

We further emphasize that the reveals relation is essentially a non-temporal relation, as opposed to temporal properties or the synchronic distance of e.g. [START_REF] Goltz | Synchronic distance[END_REF][START_REF] Reisig | Petri Nets: An Introduction[END_REF][START_REF] Zhao | Synchronic Distance Based Workflow Logic Specification[END_REF]. The latter measures the quantitative degree of independency in the repeated occurrences of two net transitions, whereas a ⊲ b holds if and only if event a implies event b.

The reveals relation was first introduced in [START_REF] Haar | Unfold and cover: Qualitative Diagnosability for Petri Nets[END_REF]; more properties and discussions of its applications are given in [START_REF] Haar | Types of Asynchronous Diagnosability and the Reveals-Relation in Occurrence Nets[END_REF]. An important motivation for studying reveals lies in the partial observability of many systems in applications such as those related to fault diagnosis. The idea is that a⊲b implies that it suffices to observe a to infer occurrence of b; conversely, b does not have to be observable itself, provided a or any other event that reveals b is observable.

This binary relation is the topic of the present article. Recently, [START_REF] Balaguer | Building Tight Occurrence Nets from Reveals Relations[END_REF] gave generalizations that include a reveals relation connecting pairs of sets of events; however, even in this general setting the binary relation turns out to play a central role. Its exploration and effective computation remains therefore an important task, not only for the structural theory. In fact, ⊲ is relevant in general for opacity-related properties and tasks concerning concurrent systems; potential and actual applications include verification diagnosability (see [START_REF] Haar | Types of Asynchronous Diagnosability and the Reveals-Relation in Occurrence Nets[END_REF][START_REF] Haar | Qualitative Diagnosability of labeled Petri nets revisited[END_REF]) and other properties, conformance testing, synthesis of controllers and adaptors.

Concerning the task at hand, note that it was shown in [START_REF] Haar | Types of Asynchronous Diagnosability and the Reveals-Relation in Occurrence Nets[END_REF] that the reveals relation can be effectively computed for unfoldings of safe nets. For each pair of events (a, b), a suitable finite prefix whose height exceeds that of a and b by at most a uniform bound, is sufficient to verify if a reveals b. Here, we make the following contributions:

• We considerably improve the bound on the size of the finite prefix needed to decide whether a reveals b. While the previous bound seemed to make this decision impracticable, the new bound gives much more hope to determine the relation in practice.

• Motivated by this, we discuss an efficient algorithm that computes the entire reveals relation within a given prefix. The algorithm can be implemented completely with bitset operations.

• We have implemented the algorithm and report on experiments, notably on the following questions: how big is the prefix necessary to determine the reveals relation, and how much time does it take to compute said relation on a given prefix? Concerning the second question, the algorithm turns out to be suitably fast; it works on prefixes with tens of thousands of events in a few seconds, and usually takes less time than the actual construction of the prefix.

We proceed as follows: Section 2 introduces Petri nets, their unfoldings, the reveals relation, and some of its salient properties. Section 3 gives the new bound on the size of the prefix. Section 4 presents an algorithm for computing reveals on a given prefix, and Section 5 presents the experiments. We conclude in Section 6.

Definitions

This section introduces central definitions and facts about Petri nets, their unfoldings, and the reveals relation. While most definitions and some results would be valid in the case of Petri nets that are bounded, but not 1-bounded, our main interest is in 1-bounded (aka safe) nets. Moreover, lifting to non-safe nets brings little additional insight but makes arguments much more technical and cumbersome; we therefore chose to focus on safe nets.

Petri nets

A Petri net is a triple N = (P, T, F, M 0 ), where P and T are disjoint sets of places and transitions, respectively, and F ⊆ (P × T ) ∪ (T × P) is the flow relation. Any function M: P → IN is called a marking, and M 0 is the initial marking. By node, we shall mean an element from the set P ∪ T .

In figures (e.g., the left-hand side of Figure 1), circles represent places, rectangular boxes represent transitions, and directed edges represent F. A marking M is represented by black tokens.

For a node x, call

• x := { x ′ | (x ′ , x) ∈ F } the preset, and x • := { x ′ | (x, x ′ ) ∈ F } the postset of x.
Moreover, for any set X ⊆ P ∪ T , set

• X := x∈X • x and X • := x∈X x • .
Transitions induce a firing relation among markings, as follows: Let M, M ′ be markings and t a transition. Then we write

M t -→ M ′ iff M(p) ≥ 1 for every p ∈ • t and M ′ (p) = M(p) -1 if p ∈ • t \ t • , M ′ (p) = M(p) + 1 if p ∈ t • \ • t, and M ′ (p) = M(p) otherwise.
In words, we also say that t is enabled in M, and that firing it leads to M ′ .

A finite sequence σ

:= t 1 . . .t k of transitions is a run iff M 0 t 1 -→ M 1 • • • t k
-→ M k for some markings M 1 , . . . , M k ; if such a run exists, then M k is said to be reachable. The set of reachable markings is denoted R(N). A net is said to be safe if no reachable marking puts more than one token into any place. As explained above, all the nets we are interested in will be safe. Thus, we shall henceforth treat markings as subsets of P.

An infinite sequence t 1 t 2 . . . is called a run if every prefix of it is one. We say that a run σ is fair iff

• either σ is finite, and in the marking reached by σ , no transition is enabled;

• or σ = t 1 t 2 . . . is infinite, where M 1 , M 2 , . . . are the markings generated by firing σ , and there exists no pair t ∈ T and i ≥ 1 such that t is enabled in all M k , k ≥ i and t = t k for all k > i.

In other words, a fair run cannot delay firing an enabled transition forever.

Occurrence nets

Occurrence nets are a specific type of acyclic Petri net. Keeping with tradition, we shall call the places of an occurrence net conditions and its transitions events. Fix a safe Petri net O = (C, E, F,C 0 ) for the rest of this subsection. We let < denote the transitive closure of F and ≤ the reflexive closure of <; further, if e ∈ E is an event, let ⌈e⌉ := { e ′ ∈ E | e ′ ≤ e } be the cone of e, and ⌊e⌋ := ⌈e⌉ \ {e} the pre-cone of e. Two nodes x, x ′ are in conflict, written x # x ′ if there exist e, e ′ ∈ E such that (i) e = e ′ , (ii) • e ∩ • e ′ = / 0, and (iii) e ≤ x and e ′ ≤ x ′ .

O is called an occurrence net if it satisfies the following properties:

1. no self-conflict: ∀x ∈ C ∪ E: ¬(x # x);
2. < is acyclic, i.e. ≤ is a partial order;

3. finite cones: all events e satisfy |⌈e⌉| < ∞;

4. no backward branching: all conditions c satisfy | • c| ≤ 1;

5. C 0 ⊆ C is the set of ≤-minimal nodes.
Example 1 The right hand side of Figure 1 shows an occurrence net. The events a and c are both in conflict with b, yet not with one another; in fact, they are concurrent (neither ordered nor in conflict).

Let O = (C, E, F,C 0 ) be an occurrence net. We call

O ′ = (C ′ , E ′ , F ′ ,C 0 ) a prefix of O if • C ′ ⊆ C, E ′ ⊆ E, F ′ = F ∩ (C ′ ∪ E ′ ) 2 ,
C ′′ = C \ • C , E ′′ = E \ C , F ′′ = F ∩ (C ′′ ∪ E ′′ ) 2 ,

and

C ′′ 0 = Cut(C ).
If C is a finite configuration and e ∈ E \C an event such that • e ⊆ Cut(C ). In this case, C ′ := C ∪{e} is a configuration, and we write C e ❀ or C e ❀ C ′ . By extension, for a finite configuration C and a set A = {e 1 , . . . , e n } of events, we write

C A ❀ C ′ iff there exist C 0 , . . . , C n such that C 0 = C , C n = C ′ , and for all i = 1, . . . , n, C i-1 e i ❀ C i . We write C ⊑ C ′ if there exists a set A such that C A ❀ C ′ .
The following facts are well-known, see e.g. [START_REF] Engelfriet | Branching Processes of Petri Nets[END_REF][START_REF] Esparza | An Improvement of McMillan's Unfolding Algorithm[END_REF]:

• A downward-closed set C ⊆ E is a configuration iff the elements of C can be arranged to form a run σ of O. We have that σ is fair iff C is maximal. Moreover, if C is finite, then σ leads from C 0 to Cut(C ).
• For every event e, ⌈e⌉ and ⌊e⌋ are configurations.

• Let c, c ′ ∈ C be a pair of conditions. Then exactly one of the following three statements holds:

c and c ′ are causally related, i. A set of pairwise concurrent places is called a co-set.

Unfoldings

Let N = (P, T, F, M 0 ) be a safe Petri net. Intuitively, an unfolding of N is an acyclic version of N where loops of N are "unrolled"; an unfolding is usually infinite even if N is finite. Formally, U = (C, E, G,C 0 ) is called an unfolding of N if U is an occurrence net equipped with a mapping f : (C ∪ E) → (P ∪ T ), which we extend to sets and sequences in the usual way. We shall write f : A ↔ B if the restriction of f to A yields a bijection between A and B. Then U is the unfolding of N if the following properties hold:

• f (C) ⊆ P, f (E) ⊆ T , and f :C 0 ↔ M 0 ;
• for every co-set D ⊆ C and transition t ∈ T such that f : D ↔ • t, there is exactly one event e ∈ E with f (e) = t and • e = D;

• if f (e) = t for some event e, then f :

• e ↔ • t and f : e • ↔ t • .
With every configuration C of U we associate the marking Mark(C

) := { f (c) | c ∈ Cut(C ) }.
Example 2 Figure 1 shows a net N on the left and prefix of its unfolding on the right; the function f is reflected in the inscriptions. It is well-known [START_REF] Engelfriet | Branching Processes of Petri Nets[END_REF][START_REF] Esparza | An Improvement of McMillan's Unfolding Algorithm[END_REF] that M is a reachable marking in N iff there exists a configuration C of U such that Mark(C ) = M. Moreover, if σ is a run corresponding to C , then f (σ ) leads from M 0 to M in N. It is in this sense that U mimics the behaviour of N.

A prefix U ′ of U is called complete if it "contains" every marking of N, i.e. for every reachable marking M ∈ R(N) there exists a configuration C of U ′ such that Mark(C ) = M. It is well-known that for any configuration C , the postfix U/ C is isomorphic to the unfolding of the net (P, T, F, Mark(C )).

The "reveals" relation

To illustrate "reveals" we shall study the occurrence net in Figure 2. We are interested in finding relations between events of the form 'if x occurs, then y has already occurred, or will occur eventually', in the sense that any fair run that contains x also contains y. In other words, this means that y is inevitable given x.

In the context of Figure 2, it is obvious that, for any fair run σ ,

k ∈ σ =⇒ e ∈ σ =⇒ b ∈ σ ,
where we use k ∈ σ etc informally to mean that k occurs somewhere in σ . In fact, the statement above simply reflects the causal relationship; if k happens, then surely its cause e must have happened before. But one also obtains the following facts in Figure 2, again for fair runs σ :

a ∈ σ ⇐⇒ ¬(b ∈ σ ) ⇐⇒ c ∈ σ and c ∈ σ ⇐⇒ g ∈ σ .
In fact, a, c are a pair of independent transitions which can happen concurrently, where as c is a causal predecessor of g and yet allows to determine that g will eventually happen. The reader is invited to check that these relations follow from the fairness of runs. We thus define our desired relation as follows:

Definition 1 Let O be an occurrence net and e, e ′ be two of its events. We say that e reveals e ′ , written e ⊲ e ′ , iff for all fair runs σ of O e ∈ σ implies e ′ ∈ σ . The revealed range of event e is ⊲[e] := { e ′ | e ⊲ e ′ }.

Notice that the definition immediately implies that ⊲ is reflexive and transitive. Moreover, there is a reveals relationship along causal successors, i.e. if a < b, then b ⊲ a. The relation ⊲ is not symmetric in general: in fact, in Figure 2 we have h ⊲ e but ¬(e ⊲ h). On the other hand, ⊲ is not a partial order: consider e ⊲ f and f ⊲ e in Figure 2. These examples show that the inheritance of conflict along causality relations is not sufficient to derive the statements above. One might therefore suspect that, to obtain the above facts one would have to explore the entire set of configurations. However, the following is known: Lemma 1 ( [START_REF] Haar | Unfold and cover: Qualitative Diagnosability for Petri Nets[END_REF][START_REF] Haar | Types of Asynchronous Diagnosability and the Reveals-Relation in Occurrence Nets[END_REF]) For an event e, its conflict set is defined as

#[e] := { e ′ | e # e ′ }. We have that e ⊲ e ′ iff #[e] ⊇ #[e ′ ].
Thus, in principle all it takes to see if e ⊲ e ′ holds is to check whether no witness against it exists for (e, e ′ ); we call g a witness for the tuple (e, e ′ ) if ¬(e # g) and e ′ # g. However, notice that this does not provide us with an effective procedure because the conflict sets can be infinite in general (see [START_REF] Haar | Types of Asynchronous Diagnosability and the Reveals-Relation in Occurrence Nets[END_REF]). In Section 3 we shall show that e ⊲ e ′ can effectively be decided.

Facets. Let us just note in passing that the strongly connected components of ⊲, called facets in [START_REF] Haar | Types of Asynchronous Diagnosability and the Reveals-Relation in Occurrence Nets[END_REF], form equivalence class of occurrence in the sense that any run ω that contains any event of a facet must contain all of its events. In Figure 3, the decomposition of the occurrence net from Figure 2 into its facets is shown. The facets are {a, d, c, g}, {b, e, f }, {h}, {k}; the right hand side shows the occurrence net obtained by abstracting every facet into a single event. In general, quotienting an occurrence net into its facets and their boundary conditions yields an occurrence net whose set of maximal runs is in bijection with that of the initial occurrence net; this procedure (for details see [START_REF] Haar | Types of Asynchronous Diagnosability and the Reveals-Relation in Occurrence Nets[END_REF]) can reduce the model size for analyses of any properties regarding maximal behaviours. In [START_REF] Balaguer | Building Tight Occurrence Nets from Reveals Relations[END_REF], we focus on reduced nets, i.e. where the contraction of facets has been carried out, and every event is a facet; in this framework, behavioural properties can be specified in a dedicated logic ERL, for which the synthesis problem is solved in [START_REF] Balaguer | Building Tight Occurrence Nets from Reveals Relations[END_REF]; the occurrence nets obtained in a canonical way from a logical formula belong to a distinguished subclass of reduced occurrence nets, the tight nets. For more traditional applications, the facet decomposition can in general yield fast sufficient criteria for verifying properties. Consider observability-related properties Petri nets (see [START_REF] Haar | Unfold and cover: Qualitative Diagnosability for Petri Nets[END_REF][START_REF] Haar | Qualitative Diagnosability of labeled Petri nets revisited[END_REF] for a detailed discussion on diagnosability): if λ : T → A is a partial labelling in some alphabet A, how can one quickly decide whether some unobservable transition t -i.e. on which λ is undefined -has occured? By pre-computing the reveals-relation and thus the facets on a sufficient finite prefix of the unfolding, online reasonings of the following type become available : If λ is such that every facet in which some instance of t occurs contains an occurrence of a distinctive label a that t free facets do not produce, then detection of a allows to infer occurrence of t with certainty. Given that the facet decomposition and contraction can be computed offline, see below, and reduces the size of unfoldings dramatically, such improvements are valuable in monitoring and supervising large distributed networks, in particular in telecommunications [START_REF] Fabre | Partial Order Techniques for Distributed Discrete Event Systems: Why You Cannot Avoid Using Them[END_REF][START_REF] Benveniste | Diagnosis of asynchronous discreteevent systems: a net unfolding approach[END_REF][START_REF] Fabre | Distributed Monitoring of Concurrent and Asynchronous Systems[END_REF]. Let N = (P, T, F, M 0 ) be a safe Petri net, where P and T are finite, for the rest of the section, and let U = (C, E, G,C 0 ) be its unfolding, where f is the mapping between U and N.

In this section, we shall consider the following problem: Given two events x and y, does x reveal y? As pointed out in Lemma 1, this requires to decide whether a witness exists. We shall show that the height of a witness is bounded, i.e. it suffices to search a finite prefix of U to find a witness. The existence of a finite bound, albeit a much higher one, was first pointed out in [START_REF] Haar | Types of Asynchronous Diagnosability and the Reveals-Relation in Occurrence Nets[END_REF], and we start by re-stating that result.

Definition 2 Associate to each event e a marking of N by taking M e := Mark(⌈e⌉). We shall define a sequence (L i ) i≥1 of sets of events, the so-called level-i cutoffs, and a sequence of prefixes (U i ) i≥1 , the so-called level-i prefixes.

We let e ∈ L 1 if M e = M 0 or there exists an event e ′ such that e ′ < e and M e ′ = M e . For i > 1, we let e ∈ L i iff there exists an event e ′ ∈ L i-1 such that e ′ < e and M e ′ = M e . For i ≥ 1, let L min i be the ≤-minimal events of L i . We let U

i := U[L ′ i ], where L ′ i := e∈L min i ⌈e⌉ is the downward-closure of L min i .
Intuitively, the prefix U 1 contains all reachable markings and unrolls each loop in the Petri net exactly once; notice that the events L 1 are exactly those events that return the net to a marking that was reached before. The prefix U 2 unrolls each loop once more and so on. The following result is shown in [START_REF] Haar | Types of Asynchronous Diagnosability and the Reveals-Relation in Occurrence Nets[END_REF]:

Theorem 1 [START_REF] Haar | Types of Asynchronous Diagnosability and the Reveals-Relation in Occurrence Nets[END_REF] Let m be the the minimal index such that U m contains event x, and let n be the corresponding index for y. Moreover, let K M be the number of reachable markings of the net N. Then, if ¬(x ⊲ y), there exists a witness in U K M +max{m,n}-1 . K M is guaranteed to be finite for safe nets, hence Theorem 1 establishes the decidability of ⊲. However, K M is difficult to determine exactly and in general very large, not to mention the size of U K M +max{m,n}-1 . We shall see that this bound can be improved. Formalizing the discussion after Lemma 1, we define, for events x, y, z, the witness predicate wit(x, y, z):

wit(x, y, z) :⇐⇒ (z # y) ∧ ¬ (z # x) .
To prepare the main result, let us first define the height function H . Let O be an occurrence net and e one of its events. Then

H (e) := 1 + max e ′ ∈ • ( • e) H (e ′ ),
where max / 0 := 0.

We naturally extend the height function to finite prefixes of O:

H (O[E ′ ]) := max e∈E ′ H (e) (1)
Let M be a reachable marking of N and N(M) be the net (P, T, F, M), i.e. N with M as the initial marking. Moreover, let U M be the unfolding of N(M) and U M i the analogous prefixes according to Definition 2. Let K(M) := H (U M 1 ), and

K := max M∈R(N) K(M). ( 2
)
Lemma 2 The value of K is bounded above by the height H (U 2 ) of the level-2 prefix of N.

Proof: We first show that U 1 is a complete prefix. Indeed, in [START_REF] Kenneth | Using Unfoldings to Avoid the State Explosion Problem in the Verification of Asynchronous Circuits[END_REF] an event e is called a cut-off of U if M e = M 0 or there exists an event e ′ such that M e ′ = M e and |⌈e ′ ⌉| < |⌈e⌉|. It is shown in [START_REF] Kenneth | Using Unfoldings to Avoid the State Explosion Problem in the Verification of Asynchronous Circuits[END_REF] that a prefix that contains all minimal cutoffs is complete. Evidently, e ′ < e implies |⌈e ′ ⌉| < |⌈e⌉| and is a stronger condition, therefore our prefix U 1 contains all such minimal cutoffs and is also complete.

Let M ∈ R(N). By completeness of U 1 , there exists a configuration C in U 1 such that Mark(C ) = M. Now, by construction of U 2 , the postfix U 2 / C contains an isomorphic copy of U M 1 . ✷ We now state the main result of this section: Theorem 2 Let N be a safe Petri net, U its unfolding, and let K as defined in [START_REF] Benveniste | Diagnosis of asynchronous discreteevent systems: a net unfolding approach[END_REF]. For any two events x, y such that ¬(x ⊲ y), there exists an event z such that 1. wit(x, y, z) and 2. H (z) ≤ n + K, where n := max(H (x), H (y)).

Proof: The idea of the proof is illustrated in Figure 4. Let f be the mapping between N and U. If ¬(x ⊲ y) then some event z satisfying wit(x, y, z) exists; it remains to determine the maximal height of z. If x # y, we are done immediately, taking z := x. Otherwise, C xy := ⌈x⌉ ∪ ⌈y⌉ is a configuration. Choose z ∈ E such that wit(x, y, z) holds, and such that z ′ < z implies ¬wit(x, y, z ′ ). By assumption we have ¬(x # z), thus C xz := ⌈x⌉ ∪ ⌈z⌉ is also a configuration. Further, let u be such that u # z and u ≤ y and such that u ′ < u implies ¬(u ′ # z). We claim that C uxz := ⌊u⌋ ∪ ⌈x⌉ ∪ ⌊z⌋ is a configuration: if this were not the case, then there would be events e, e ′ ∈ C uxz such that e # e ′ . Since C xy and C xz are configurations, it would follow w.l.o.g. that e ∈ ⌊u⌋ and e ′ ∈ ⌊z⌋, so e < u and e ′ < z. But then e # z and e ′ # y, both of which contradicts the minimality assumptions on u and z. We thus have ❀. Suppose that z satisfies H (z) > n + K. Then the choice of K implies the existence of two distinct configurations

C uxz z ❀ and C uxz u ❀ . (3)
C 1 , C 2 of U such that 1. C uxz n ⊑ C 1 ⊑ C 2 ⊑ C uxz , 2. H (C 1 ) < H (C 2 ), and 3. Mark(C 1 ) = Mark(C 2 ).
In fact, Mark(C 1 ) = Mark(C 2 ) implies that U/ C 1 and U/ C 2 are isomorphic, and there exist sets A 1 ,

A 2 with f (A 1 ) = f (A 2 ) such that C 2 A 2 ❀ C uxz and C 1 A 1 ❀ C for some C . Now, Mark(C ) = Mark(C uxz )
, so there exists an event e such that f (e) = f (z), H (e) < H (z), and C e ❀. Thus, C ∪ {e} is a configuration containing both x and e, so ¬(x # e).

From u # z and (3) it follows that u and z compete directly for a token, i.e. there exists a condition b ∈ We thus obtain wit(x, y, e), and the height of e is strictly less than that of z. Either H (e) ≤ n + K, and we are done; or we replace z by e and repeat the surgery above, obtain another witness with strictly lesser height etc, until we end up with a witness that has the desired height. ✷ Theorem 2 in connection with Lemma 2 implies that for any pair x, y of concurrent events, it suffices to inspect U M xy 2 to determine whether x ⊲ y, where M xy := M(⌈x⌉ ∪ ⌈y⌉). Notice that this bound is much lower than the one given by Theorem 1; in fact, contrary to the previous bound it provides hope to actually compute the relation.

• u ∩ • z. Since f (e) = f (z), there must be b ′ ∈ • e with f (b ′ ) = f (b). Now, b co b ′ cannot hold because N is safe. Suppose b # b ′ . But
The reader will observe that in the proof of Theorem 2 we exploit the fact that a suffix of C uxz n with height K contains two marking-equivalent causally related events. To find two such events, it actually suffices to search an isomorphic copy of the level-1 prefix starting at the marking associated with C uxz n . It is thus tempting to think that Lemma 2 unfolds "one level too much". However, for a given candidate z as witness for x and y, there may be many possible events u for which one would have to search the suffix of C uxz n , therefore limiting the candidates in this manner would not at all be straightforward. The value of Lemma 2 is in bounding the set of candidates for z in a simple, effective manner.

Algorithms for computing the reveals relation

In this section, we exploit the results of Sections 2 and 3 to exhibit two concrete algorithms for determining the reveals relation. The main contribution is in Section 4.1, where we show how to compute the relation between all events in a given prefix. In Section 4.2 we discuss the question how to decide x ⊲ y for a single pair x, y.

Computing reveals on a given prefix

For the rest of this section, let us fix a finite occurrence net O, which should be a finite prefix of some safe Petri net, where E is the set of events. We are going to compute the relation ⊲ between all pairs in E.

An algorithm for this purpose can be useful if either the underlying net is free of loops (and hence the unfolding is finite), or if one wants to compute the relation for all events of height up to n (in which case the prefix should contain the events of height n + K).

Our algorithm consists of three passes over the occurrence net that compute, in turn, the causality relation <, the conflict relation #, and finally the reveals relation ⊲. We assume that events in E are available in topologically sorted order, i.e. an order ≺ where e < e ′ implies e ≺ e ′ . Such an order can be easily established while scanning O: e.g., one first identifies the minimal conditions (those having no incoming arcs) and then traverses the unfolding with a standard worklist algorithm.

For the three passes that compute <, #, and ⊲, we exploit certain causal inheritance properties. It turns out that most operations can be implemented with simple bitset operations.

1. In the first pass, we compute for each event e a set of events post(e) := { e ′ | e ≤ e ′ } containing its successors (and e itself). Initially, that set is empty for all e; we then traverse E in inverse topological order, exploiting the fact that the causal relationship is obviously transitive: e ≤ e ′ iff e = e ′ or there exists e ′′ such that e ′′ ∈ (e • ) • and e ′′ ≤ e ′ .

2. In the second pass, we compute for each event e the set conf (e) := { e ′ | e # e ′ }, i.e., the set of events with which e is in conflict. Here, we exploit that the conflict relation is inherited by causal successors: e # e ′ iff • e ∩ • e ′ = / 0 or there exists f , f ′ such that f ≤ e, f ′ ≤ e ′ , and • f ∩ • f ′ = / 0. We traverse E in topological order; each event e inherits the conflicts of its (direct) causal predecessors and obtains new conflicts with the set post(e ′ ) for all events e ′ with which it directly competes for some condition.

results from [START_REF] Haar | Types of Asynchronous Diagnosability and the Reveals-Relation in Occurrence Nets[END_REF] we know that x ⊲ y iff #[x] ⊇ # µ [y]. To find a witness, it suffices therefore to find an event z that is not in conflict with x, but a root conflict of y; the latter implies that • z ∩ ⌊y⌋ = / 0. We propose the following: First, mark the conditions in ⌊y⌋ as 'goals'. Secondly, mark all conditions and places in conflict with x as 'useless' (they cannot produce a witness), as well as all elements of ⌊x⌋ (which can equally not produce a witness by assumption). One then regards the remaining non-'useless' events up to the height given by Lemma 2, either by unfolding them on-the-fly or by following them on a pre-computed prefix. A witness is found if one such 'non-useless' events consumes a 'goal' condition.

Experiments

We implemented the theoretical and algorithmical results of the preceding sections and evaluated them experimentally. The problems we wanted to address were the following:

• What is the value of K (as given by Lemma 2) for medium-sized nets?

• Provided a prefix is available, how efficiently can one determine ⊲, using Algorithm 1?

As inputs, we chose the safe Petri net examples supplied by the PEP tool [START_REF] Grahlmann | The PEP tool[END_REF]. Table 1 provides some statistics on the nets we used, such as the number of places and transitions, as well as the bound K according to Lemma 2 for each particular net. We obtained K by modifying the Mole unfolding tool [START_REF] Schwoon | The Mole tool[END_REF]. Normally, Mole is used to compute finite complete prefixes; for our experiments, we modified its cutoff criterion so that it would compute the unfolding prefix U 2 . We also give the time, in seconds, to compute the said prefix in the rightmost column. To make the experiments more interesting, we excluded non-cyclic examples, where K would be obvious. For the rest, the computation of K succeeded except in one case (mutual, more than 10 minutes). To give some indications, the size of a complete prefix in these cases was between several dozen and a few thousand events, whereas the size of U 2 was between several hundred and several ten thousands of events. By contrast, the computation of K failed for another set of larger benchmarks provided by Mole, whose complete prefixes already have a size of 10,000 and more events.

To answer the second question, we implemented Algorithm 1 in Java. Our program took a precomputed prefix and computed the relation ⊲ on it, using the BitSet class for most operations. The results are summarized in Table 2. As one can see, the algorithm works well even for several tens of thousands of events, usually computing the relation in a matter of seconds.

We detail the time for the three passes of the algorithm (all times are in seconds); in almost each case, we have the same ordering of computation times. The computation of the causal relation (post) takes hardly significant time, the second pass for the computation of the conflict relation (conf ) takes a little more time, and the third pass for the computation of the reveals relation (rev) slightly dominates the computation time.

Conclusion

We presented theoretical and algorithmic contributions towards the computation of the reveals relation. The analysis in [START_REF] Haar | Types of Asynchronous Diagnosability and the Reveals-Relation in Occurrence Nets[END_REF] had only provided the proof that a ⊲ b could be decided on some bounded prefix of the unfolding; but the bound (see Theorem 1) was prohibitively large, and an efficient procedure for computing ⊲ was lacking. The present paper closes this theoretical and practical gap. Our results show that with a suitable cutoff-criterion, the complete finite prefix U 2 is sufficient to obtain the ⊲-relation on U 1 . Moreover, an efficient algorithm for computing ⊲ on finite occurrence nets has been proposed and tested; the experimental results clearly show that ⊲ can be obtained and used in practice. The theory of reveals can be further developed in the lines of [START_REF] Balaguer | Building Tight Occurrence Nets from Reveals Relations[END_REF], where a dedicated logic (called ERL) is introduced for expressing generalized reveals relation of the form "if all events from set A occur, then at least one event from set B must eventually occur", and the problem of synthesizing occurrence nets from ERL formulas is solved. The study of further variants of logics for concurrency in the light of

Figure 1 :

 1 Figure 1: A Petri net (left) and a prefix of its unfolding (right)

  e. c < c ′ or c ′ < c; c and c ′ are in conflict, i.e. c # c ′ ; c and c ′ are called concurrent, written c co c ′ , i.e. there exists a configuration C such that {c, c ′ } ⊆ Cut(C ).

Figure 2 :

 2 Figure 2: Example of an occurrence net

Figure 3 :

 3 Figure 3: Left: a prefix of the example from Fig. 2 with facets highlighted; right: the occurrence net obtained from the left hand one through facet abstraction

Figure 4 :

 4 Figure 4: Rough sketch of the proof of Theorem 2; there exists a condition b in the preset of both u and z; moreover, u < y and n = max(H (x), H (y)). From C uxz we construct the smaller configuration C .

  then there must exist two events u ′ = e ′ such that u ′ < b and e ′ < b ′ and • u ′ ∩ • e ′ = / 0. By definition, C contains ⌊u⌋ and enables e, so b and b ′ must both be contained in the prefix U[C ], so u ′ , e ′ ∈ C , but, being a configuration, C cannot contain two conflicting events. The only possibilities left are b = b ′ , b < b ′ , or b ′ < b, and in all cases we obtain e # u and therefore e # y.

  and moreoverC ′ ⊇ C 0 ∪ (E ′ ) • ;• C ′ and E ′ are downward-closed, i.e. for any x ∈ C ′ ∪ E ′ and y < x we have y ∈ C ′ ∪ E ′ .

						1		2
	r		t	u		a	b		c
		1	2			3	4	5	6
	a		b	c		d	e	f	g
	3	4	5	6		7	8	9	10
	d	e	f	g		h	k		r
	7	8	9	10	t	11	12	1 1	2 1
	11	h	k	12	1 3	2 3		u
							1 2	2 2

Table 1 :

 1 Net statistics and computation of K

	Petri net	|P| |T | K Time/s
	buf100	200 101 201	2.1
	elevator	59 74 80	0.3
	gas station	30 18 18	0.1
	mutual	62 67 -	t/o
	parrow	77 54 91	1.6
	peterson	27 31 34	0.1
	reader writer 2	53 60 29	2.3
	sdl arq deadlock 202 183 37	0.1
	sdl arq	208 234 129	0.2
	sdl example	323 471 71	0.1
	sem	26 25 35	0.1

Table 2 :

 2 Running times of Algorithm 1

	Petri net	Events	post	conf	rev
			(Time/s) (Time/s) (Time/s)
	bds 1.sync	12900	0.13	0.19	0.30
	buf100	17700	0.17	0.12	0.25
	byzagr4 1b	14724	0.18	0.19	0.68
	dpd 7.sync	10457	0.11	0.15	0.24
	dph 7.dlmcs	37272	0.56	0.91	2.10
	elevator75	234879	15.84	22.58	97.47
	elevator	5586	0.05	0.05	0.13
	elevator 4	16856	0.17	0.27	0.38
	fifo20	100696	2.92	3.72	22.88
	ftp 1.sync	83889	2.08	3.61	6.78
	furnace 3	25394	0.29	0.47	0.95
	gas station	2861	0.01	0.01	0.01
	key 4.fsa	67954	1.40	2.19	4.62
	parrow	85869	2.47	4.17	9.51
	peterson	72829	1.60	2.54	5.23
	q 1.sync	10722	0.11	0.15	0.30
	q 1	7469	0.08	0.09	0.17
	reader writer 2 20229	0.24	0.37	0.53
	rw 12.sync	98361	2.36	5.14	6.36
	rw 12	49179	0.68	1.25	1.70
	rw 1w3r	15401	0.15	0.22	0.50
	rw 2w1r	9241	0.10	0.11	0.25
	sdl arq	2691	0.03	0.03	0.09
	sem	19689	0.20	0.23	0.61

The author was supported by the DFG Graduiertenkolleg 1480 (PUMA).

3. In the third pass, we finally compute a set rev(e) for each event e such that rev(e) := { e ′ | e ⊲ e ′ }.

Here, we mainly exploit two facts: e cannot reveal any events with which it is in conflict, and it reveals all events revealed by its causal predecessors: if e ′′ ⊲ e ′ and e ′′ < e, then e ⊲ e ′ . We thus traverse E in topological order; at each event, all known conflicts are discarded, and events from direct causal predecessors inherited. This leaves some events e ′ for which the status is unknown (concurrent events and causal successors), and for these we check directly whether conf (e) ⊇ conf (e ′ ) (compare Lemma 1). Figure 1 shows a version of the algorithm in pseudo-code. Notice that if post(•), conf (•), and rev(•) are stored as bitsets (containing one bit for every event in E), then almost all operations can be implemented using basic logical operations on bitsets. In the first two passes, the number of such operations is bounded by the number of arcs in U. In the third pass, the number of operations is bounded by the pairs (e, e ′ ) such that e ′ / ∈ (rev(e) ∪ conf (e)), that is by |E| 2 in the worst case. However, it turns out that in most cases the number of such checks is comparatively small.

Computing reveals for a single pair

We briefly discuss the question of how to decide x ⊲ y for a single pair of events x, y. If one is interested in individual pairs, such a procedure may well be more efficient than the one from Section 4.1 because it allows to limit the events one has to consider.

Assume that x, y are events of some unfolding U, of which at least the prefix ⌈x⌉ ∪ ⌈y⌉ is known. (We assume that neither x#y nor x > y hold, otherwise the solution is trivial.) Denote by #

} the set of <-minimal conflicts of y, its so-called root conflicts. Due to

Computing the Reveals Relation in Occurrence Nets

the recent results has only just begun.

In addition, we intend to extend reveals-based analysis to other Petri net classes such as Time nets and contextual nets, and to exploit it in applications that include diagnosis and testing.