Antonio A Casilli

Four Theses on Digital Mass Surveillance and the Negotiation Of Privacy

The current 1 political debate is fueled by growing tensions over the implementation of a digital mass surveillance framework aimed to gather, store and process data from transactions, interactions and everyday uses of information and communication technologies. In the wake of Edward Snowden's early revelations about the US PRISM program and the subsequent international scandal over the NSA/Five Eyes spying, surprise and shock among the general public were mostly due to the extent to which the intelligence agencies of western democratic governments were intercepting information from their own citizens. The subsequent legislative moves in France 2 , United Kingdom 3 , Canada 4 , and Australia 5 , towards long-term mandatory data retention and real-time algorithmic electronic surveillance are still met with strong opposition and suspicion from the civil society. They have been hurried into laws only at the price of strenuous efforts by governments and legislators to silence opposition, by failing to engage in democratic debate in the name of national security and the fight against terrorism.

2. Historically, the deployment of digital mass surveillance systems has been consubstantial with a long-term shift towards the expression of a powerful executive, combined with the infiltration of military interests in the democratic apparatus, or

even by the gradual assimilation between domestic security matters and the doctrine of national security. 6 Although the executive power's tendency to operate with no counterbalance could be seen as part and parcel of a democratic project that is still in fieri (an 'unfinished democracy', to borrow French political theorist Pierre Rosanvallon's 7 expression), the securitarian shift Western countries have endured in the last decades stands apart by the way it has grown into an all-encompassing discourse influencing the methods of democratic deliberation, obstructing the ability of the legislative and judicial branches to check and balance executive functions on the one hand, and the manifestations of a general willingness to respect citizens' freedoms and fundamental rights on the other.

3. The fact that these events are poised to force a profound change to the relationship between governments and those they govern is only one of the variables of the current political equation. The other variable contributing to an unprecedented climate of political instability is represented by the fact that markets are increasingly playing less of a role as third party forces correcting states' securitarian excesses. As stakeholders in the digital economy fail to comply with their own responsibilities in limiting authoritarian allocations of powers, their passive or active roles in the creation of a vast military-industrial complex become clearer. We enter a phase of anxiety and distrust between consumers and private sector businesses as well. In the space where the political challenges of digital technologies are played out, economic and strategic interests of tech companies promote such surveillance methods, maintaining they simply build on the tools that modern states have long used to monitor populations. Conversely, governments push for more privacy-invasive surveillance techniques, on the grounds that the commercial entities are already taking liberties with citizens' personal data 8 . Indeed, this public/private sector feedback loop represents a clean break with past approaches of centralized surveillance.

THESIS 1: SURVEILLANCE HAS BECOME PARTICIPATORY 4. The current debate over mass surveillance is trapped within a false dichotomy between privacy and security. This opposition is instrumental to the promotion of the indiscriminate collection of personal data, which is seen as the only guarantee against the domestic and external threats that democracies face. The main tool of this erosion of citizens' rights to privacy and secrecy is the rhetorical expedient of seeking a balance, a fair ratio between the collective right to security and the individual right to confidentiality. However, as highlighted by privacy advocate Caspar Bowden at an inquiry held by the British parliament's Intelligence and Security Committee in 2014, 'balance is a misleading metaphor. It tends to connote an unstable equilibrium with a single balance point on a linear scale'. 9 Achieving an optimal balance relies on a representation of privacy and public security as sitting in a continuum-of privacy being intrinsically insecure since it suspends surveillance.

5. Yet, the privacy-security continuum has been disrupted by a change in the nature of surveillance itself. In comparison with past ones, the current digital surveillance system for the monitoring populations is unique in that it is not direct, but rather participatory. 10 By 'participatory', we mean a mutual, horizontal surveillance based on the intentional, agonistic disclosure of personal information by users of digital services, mobile applications and online platforms. It is accompanied by a loss of control over the terms of service of technical infrastructures where personal data are stored and circulated. This surveillance is participatory insofar as it is mutual and involves a generalization of bottom-up moderation mechanisms and of the way online communities enforce norms within social platforms. A symbolic transition thus takes place, from surveillance practices relying on a Big Brother vertical conception to those relying on a 'Big Other' horizontal one, embodying a move towards an overwhelming social injunction to real-time connectivity 11 . Without this presupposition, surveillance programs based on direct access to large data collections would have been inconceivable. The surveillance system is constantly fed by the very subjects it monitors, who are part of a social system that rewards participation based on reciprocal disclosure aimed to build online social capital. Connected citizens are not just passive subjects and participatory surveillance does not inhibit their will. Rather, it empowers users by making them responsible for implementing the measures needed for the surveillance, as well as sorting through the duration and quantity of data to be disclosed, depending on the context. 6. Insofar as the quantity of disclosed data is actually determined by criteria that govern day-to-day ICT-mediated sociabilities and not by the need to protect the citizens, the search for a balance or fair ratio between privacy and security proves illusory.

7. We should not see the fact that citizens contribute to these social platforms as a symptom of technological illiteracy or ideological adherence. On the contrary, it should be viewed as a sign that their streams of communication are presently captured by a participatory architecture that uses traces of online presence to personalize usage and record data transfers in digital environments. 12 The order of priorities between protecting privacy and personalizing digital user experience therefore seems reversed in the face of these traces, whose durability and secondary uses (for both commercial and securitarian purposes) are lost on users.

THESIS 2: CLAIMS THAT 'THE END OF PRIVACY IS NIGH' ARE ERRONEOUS AND IDEOLOGICALLY MOTIVATED 8. The issue of privacy -which has inevitably and painfully been at the very center of political and social debates in recent years -reveals the limits of a theoretical stance that has dominated media discourse and the public opinion for some time. This stance focuses on the reports of the 'end of privacy' and sees its alleged disappearance from our everyday life and political concerns as a prelude to its abrogation from our legal systems. 9. The Hypothesis of the End-of-Privacy has in large part been advocated by corporate interests groups and in particular tech giants13 . An imaginary line connects the 1999 press conference during which the Chairman and Managing Director of Sun Microsystems, Scott McNealy, declared 'You have zero privacy anyway. Get over it!'14 and the 2013 Federal Trade Commission event where Vint Cerf, in his capacity as Google's 'Chief Internet Evangelist', claimed that from a historical point of view, 'privacy may be an anomaly'. 15 This perspective sits within a highly stylized, politically focused narrative of the transition to modernity. According to this view, our societies have moved from a social structure characterized by small local communities where each individual had a thorough knowledge of the opinions and whereabouts of friends and neighbors, to an urban society where the idea of a private sphere of action and thinking has been imposed by the emerging middle classes. Today, the historical parenthesis of privacy would supposedly be about to close, as part of an inevitable and spontaneous transformation of behaviors and beliefs of social media users. The 'new norm', according to the definition given by Mark Zuckerberg in 2010 16 , is one of transparency and publicness. This change is seen as part of a longer historical transition. It legitimizes connectivity services that are based on extracting consumers' personal data by incorporating them into a wider collective process. The web giants' spokespeople want nothing less than to show that their aim is to put an end to the isolated and alienated existence of the great industrial cities of the last few centuries. 10. In an attempt at historical and cultural restoration, the outcome of the fully networked society tech giants aim to, would be the return to a time that they portray as one of harmony and openness among primary circles of socialization.

11. Within academia and the civil society, some embrace the Hypothesis of the Endof-Privacy while stigmatizing the attitudes and behaviors of individual ICT users as paradoxical and alarming.17 They maintain that members of online and mobile social platforms would be prepared to gradually give up their privacy in order to benefit from commercial advantages and that usages would be moving towards greater transparency, in a regime of generalized sharing where monitoring by governments goes hand in hand with private companies tracking. Although inspired by quite different theoretical and political motivations from commercial stakeholders, academics who support this approach end up in agreement with the digital economy pundits they are trying to disprove -that privacy has well and truly disappeared.

However, observed behaviors run counter to this conclusion. In this ideologically charged climate, users are making increasingly insistent demands for autonomy and personal and collective empowerment. They are not remaining passive in the face of widespread complicity between businesses and governments, scandals surrounding the passing of draconian laws and the lack of legal and technical means to protect the integrity and confidentiality of personal data. To claim that this is the case, as certain ill-informed commentators have done, is misleading.

12. The distrust among users and producers of technologies goes hand in hand with a growing demand for services that secure and anonymize online interactions. 18 The increasing popularity of encryption tools, of 'anonymous' networks such as Tor, of 'amnesic' operating systems such as Tails, of 'ephemeral' websites and applications are all clear indications of the growing interest for users' control over their online presence. Although commercially motivated, and to a degree ineffectual, these are to be considered as technological responses to a collective demand for privacy protection solutions. Outside commercial offer, the proliferation of fake social media profiles and of quick-and-dirty presence optimization tacticts over the last few years are clear cultural signs of how users anticipate surveillance and put in place ad-hoc procedures to circumvent it19 .

13. Internet giants have reacted to this climate of distrust by offering 'competitive privacy services' (such as Gmail making it easier to encrypt emails, or Facebook allowing anonymous login) or by paying outrageous prices to acquire businesses that allegedly minimize the collection of metadata (e.g. the 19 billion dollars Facebook paid for WhatsApp in 2014). On the flip side, other sectors of the digital economy are suffering the repercussions of this new cultural and political awareness, such as US cloud computing providers, who stand to lose up to an estimated 35 billion dollars over three years. 20 14. Whether it is motivated by commercial interests or political concerns, the historical narrative that underlies the Hypothesis of the End-of-Privacy remains therefore controversial. Rather than a smooth, linear transition from a world where privacy plays a central role to one where it has supposedly lost its raison d'être, we are today engaged in a full-fledged culture war over confidentiality, anonymity, and secrecy.

15. There is no guarantee that this war will be won by civil liberties advocates or by governments, with the complicity of big data-fuelled companies that currently uphold the system of mass participatory surveillance. Today, more than ever, we need to break free of the ideological framework in which we have become trapped, one that paints privacy as just a fortuitous historical circumstance.

THESIS 3: RATHER THAN FADING AWAY, THE 'CARE OF PRIVACY' INCREASINGLY PERMEATES ICT-MEDIATED SOCIABILITIES

16. Contrary to the received wisdom that privacy is disappearing, the importance attributed to managing the limits and content of citizens' personal spheres is in fact growing in the current social and technological climate. After Michel Foucault's notion of 'care of the self' 21 , the care of privacy can be described as the task of defining the boundary between public and private -in other words, between collective responsibilities and constraints, and that which pertains to the individual capacity to think and act. 17. To break free of the current ideological biases, we need to re-contextualize the historical origins of the notion of privacy. According to Philippe Ariès' reconstruction of this historical process, the initial point can be set in Middle Ages, characterized by a social life that was neither private nor public in the sense we use these terms today. Before the modern era, interactions in the public space still fashioned an indistinct sphere where individual intimacy was dispersed in a network of 'collective, feudal and community' structures 'within a system that just about functioned: the solidarities of the seigniorial community, those of lineage and vassal relations'. [START_REF] Ariès | Pour une histoire de la vie privée[END_REF] As the balances of power that supported these structures were gradually dismantled, allowing the distinctive features of the private sphere to emerge -not just an abstract possibility, but rather a concrete concern that affects and permeates into the activities and personal orientations of modern individuals. Over the centuries, this care has been actualized by social measures that reflect this shift in attitude, such as analyzing oneself through writing, aided by the widespread elimination of illiteracy and the invention of printing; autonomous and egalitarian relationships, with an emphasis on friendship between peers; and the reconfiguration of living space, with a preference for private accommodations over communal and family houses.

18. All of these transformations can be seen as echoing the 'changes in the "We-I" balance' referred to by Norbert Elias. [START_REF] Elias | La société des individus[END_REF] Significantly, the 'social turn' of the Internet of recent years has continued this trend through an increasing emphasis on writing about oneself online, forging elective friendships and reconfiguring human spatiality. In doing so, it has made the care of privacy, as well as the public demand to protect it, more widespread.

19. The appearance of the notion of the private sphere is situated between the end of the Middle Ages and the onset of the Modern Era. Yet, the idea of privacy as a right and a prerogative to be defended is much more recent. Philosopher John Deigh [START_REF] Deigh | Privacidad, democracia e internet[END_REF] links its emergence to the need to provide a solution to the problem of the 'tyranny of the majority', first set out by Alexis de Tocqueville. The formidable strength of public opinion and the authority of the majority in modern democracies can become a threat to the autonomy of individuals and minorities. The need to guarantee intellectual freedom and to decide on a set of rights that moderate the government's power over individuals led the philosopher John Stuart Mill to formulate his 'harm principle'. According to this principle, the private sphere is an inviolable area of freedom. Mill states that 'The only part of the conduct of anyone for which he is amenable to society is that which concerns others. In the part that merely concerns himself, his independence is, of right, absolute'. [START_REF] Mill | On Liberty[END_REF] The discussion over the protection of privacy is part of such political and philosophical debate. Continuing this liberal tradition, Samuel Warren and Louis Brandeis set out the now canonical definition of the 'right to privacy' in their 1890 article published in the Harvard Law Review. 26 By developing the harm principle to take into account the need to guarantee not only the freedom to act but also the very ability of individuals to conceal themselves and their 'domestic circles' from public scrutiny, they defined privacy as 'the right to be left alone'. 20. As Deigh highlights, this legal innovation was inherent to the technological context and media environment of the late 19th century. In the period when Warren and Brandeis were writing, it was mainly gossip press, photojournalism and investigative journalism that urged to set out the limitations of one of the very postulates of contemporary democracies: a 'well-informed citizenry'. 21. More than a century after this first definition of the right to privacy, digital media have become instruments to exert citizenship rights. It has therefore become imperative to examine the ways in which they affect the technological ecosystem in order to reproblematize the boundary between private and public. To a large extent, digital social technologies can be regarded as extensions of the 19th and 20th century tools used to document and capture images and other multimedia contents as proof of behaviors and individual opinions. They also make concerns over managing and restricting their effects more widespread. By looking at the issue from a historical perspective, we can see how the supposed 'new social norm' of publicness advocated by corporate interests, but feared by users, hides a completely different reality. Privacy protection remains a key concern, but it undergoes a qualitative transformation that leads to a gradual distancing from the Anglo-Saxon liberal philosophical tradition and its application to 19 th century jurisprudence. Whereas investigative photojournalism would previously have affected only a small number of public figures and politicians, today the risk of improperly capturing and publishing private information is present at all levels of society. Big and small privacy snafus of the past few years have not only impacted celebrities. The need to manage one's digital traces now affects us all, as can be seen by the difficulties involved in applying the 'right to be forgotten' on a large scale.

22. Such a counter-history of the notion of the private sphere goes beyond the basic Hypothesis of the End-of-Privacy and the revisionist views that would make privacy a historical anomaly or even a null-and-void event. The care of privacy is the result of long-term cultural, political, and technological set of processes that are continuing in ICT-mediated social interactions. It fits neatly into our everyday working lives and usages, and reflects the structure of each of the operating social forces. It is closely linked to the democratic functioning and has proved indissociable from the gradual extension of civil liberties and their application to increasingly large swathes of the population. If in the past the requirement to protect privacy was not been perceived equally within populations, that was precisely because, as a concern, it is not immune to the influence of differential hierarchies and forms of subjection. The care of privacy is becoming more widespread insofar as modern democracies advocate -at least theoretically -a political space that is accessible to all. As Hannah Arendt would have it 27 , it is the very possibility of accessing an active, professional and public, life that makes it necessary to draw a line between what pertains to collective achievements and what is confined to the individual's private sphere.

23. Although this possibility was previously restricted to a specific category of individuals (free able-bodied adult men with steady incomes), it now extends to all those (women, children, underprivileged citizens, etc.) who previously had no need to protect their privacy precisely because they were excluded from public life.

THESIS 4: PRIVACY HAS CEASED TO BE AN INDIVIDUAL RIGHT AND HAS BECOME A COLLECTIVE NEGOTIATION

24. Recent decades28 have witnessed the establishment of a technological mediation over the right to a public life and, by implication, a private one. Active citizenship and the expression of the public will are achieved through the use of information and communication technologies. Online presence is therefore becoming a proxy for democratic participation. Far from leading to the erosion of the private sphere, this makes privacy an aspiration that is affecting the lives of an increasing numbers of persons around the world. Yet acknowledging this more widespread concern for private life, however important it may be in strengthening the argument against the Hypothesis of the End-of-Privacy, is not the same as saying that nothing has changed since the rapid rise of digital technologies.

25. We choose to describe the current transition as a shift from privacy-aspenetration to a privacy-as-negotiation.

26. The former approach takes us back to the 'right of the individual to be left alone' as set forth by Brandeis and Warren. It identifies a set of sensitive personal data (the 'privacies of life' referred to in a famous US ruling dating from the same period29 ) and places them at the heart of an individual space understood as a set of concentric circles of action. Such data would be 'private' by their very nature. This vision is based on a strict hierarchy of information, from more personal data that require greater protection to those that are less sensitive and are known by an ever-growing number of social stakeholders. According to this approach, there is therefore a set of core sensitive data that need to be protected, while the rest can easily be made public in line with a clearly unidirectional vision. An invasion of privacy is perpetrated by an external agent who manages to penetrate an individual's core sensitive data.

27. The concept of privacy as an individual right, insofar as it embodies a normative stance, represents an ideal situation that is barely recognizable in our day-to-day lives. It becomes a starting point from where to start factoring in new cultural sensibilities and technological advancements. Against a backdrop of social connectivity provided by digital devices, the intimate sphere of each individual cannot be composed in isolation. No one wants 'to be left alone' on social platforms and yet everyone expresses a care of privacy that is specific to them. In their everyday interactions, individuals endeavor to contribute actively either to disclosing or to keeping information secret, in order to limit intrusions from the outside and, more generally, to establish a set of rules and privileges for accessing specific aspects of their lives. By accepting or avoiding interactions and by adapting their frequency and intensity, individuals themselves adopt behaviors that are aimed, either explicitly or implicitly, at sorting all the information that could be the subject of social interactions in a dialectical and dynamical manner.

28. The increasing prominence of networked interactions empowers social stakeholders to display a strategic desire to create and maintain their areas of autonomy. In this new paradigm, privacy is not be construed as an individual prerogative, but rather a collective negotiation. It results from a relational arrangement that takes into account inter-subjective factors and is modeled around the signals received from those with whom an individual interacts. Privacy in online social platforms and in relationships mediated by mobile technologies is unique in that it is a decentralized, complex and multidirectional process.

29. Within ICT-mediated sociabilities, the social environment of each individual is not established in advance, but is supposedly defined by them. This situation, which typically arises when a user joins an online social network, requires above all that they evaluate the context in which interactions will take place (the participants, limits, norms, etc.) to be able to adjust the content of their communications. Building an online presence also requires users to protect themselves against intrusions from the outside, as well as managing the outgoing flow of data. To do this, each individual normally starts by a gradual disclosure of personal information that is intended to encourage feedback from the community of their interactors. 30. Unlike the traditional privacy-as-penetration model, none of the data shared are private, sensitive or intimate per se. All information is a signal sent by its author to their own environment, to the members of their personal online network. Because this signal aims to provoke a reaction from these members, the individuals help one another to adapt the information that they share by developing response and collaboration mechanisms. It is primarily by gathering this feedback and these evaluations -whether positive or negative -that users are able to establish, via trial and error, which data should be considered private and which can on the contrary be disclosed in a given context30 .

31. In that it is based on seeking an agreement between several parties rather than on a rule decreed by just one of them, this vision of privacy can be likened to a collective bargaining.

32. Stakeholders seek a consonance, compare their different interests and make mutual concessions in terms of disclosure and access to potentially sensitive information. The loss of privacy in certain areas is not equivalent to an uncontrolled debacle, but rather to a strategic withdrawal over subjects where negotiation proves challenging. It is through this collaborative disclosure accompanied by complex processes of selection and influence, that participatory surveillance is made possible -and can eventually be surpassed. From a citizen's standpoint, mass surveillance programs cannot be countered by asserting an individual right to privacy as a sphere that resists all penetration, but rather by re-establishing a symmetry between the forces involved in this negotiation process: governments, markets, and users-citizens.

CONCLUSION: AGAINST THE 'PRIVATIZATION OF PRIVACY'

33. In the current political climate, defining the notion of privacy by emphasizing the aspects that make up the conflicting interests of various social stakeholders gives rise to a reaction that we should try to avoid -that of likening the 'negotiation' of privacy to its 'commercial exploitation'.

34. Privacy has undergone a transformation. It is no longer a transaction where each individual is alone against all others, but rather a collaborative process where the motivations of each citizen combine to create social collectives (such as advocacy groups, trade associations, and recognized bodies serving shared interests) engaging commercial organizations and governments in confrontations. The eminently collective nature of the current negotiation over privacy enables us to see its advocacy above all as an antagonistic and iterative conflict around the adaptation of rules and terms of service to users' needs. This process has been marked by a series of disputes and controversies that governments have had difficulty framing, in a generalized scheme involving the whole of civil society, owners of big data-processing companies and state intelligence agencies. No one doubts that this collective negotiation is inextricable from the protection of individual liberties, which must be enabled by specific legislation to counterbalance the bargaining powers between different stakeholders.

35. The existing legislative framework is still based on a privacy-as-penetration model and aimed to 'leave users alone' by interrupting communication flows and interconnections. It does not reflect the key demands of the citizens of an ICTmediated society: to gain greater control over their own data through digital literacy, as well as through comprehensive citizen empowerment programs, and the introduction of infrastructures promoting the autonomy of communities of users. 36. Inevitably, this vision does not sit well with contemporary moves to apply the principles of private ownership to personal data, something that could be labeled as 'privatization of privacy'. Viewing privacy solely as an individual issue, or indeed as an infinitely monetizable and alienable asset, is sometimes presented as a way of making up for the commercial exploitation of personal data in which digital platforms and data brokers are already engaged. This is the argument put forward by commentators such as Jaron Lanier, who, while highlighting the inability of civil liberties to protect privacy in the age of the Internet, advocates the use of commercial rights through the introduction of a system of micro-royalties that Internet companies would have to pay to users in order to collect, store and use their personal data for commercial purposes. [START_REF] Lanier | Who Owns the Future?[END_REF] 37. Whether seen as a simple cultural provocation or as a dystopian vision, steps towards making this proposition a reality have so far been taken both by tech giants and by start-ups willing to experiment with offering remuneration to digital platform users in exchange for access to their data. [START_REF]For example, companies such as YesProfile.com[END_REF] The World Economic Forum was already describing personal data as a type of emerging asset as early as 2011. [START_REF]Personal Data: The Emergence of a New Asset Class[END_REF] This classification, that would equate personal data to a 'repugnant market' (such as the trade in human organs or of citizenship rights), poses a problem for both legislators and citizens. Interestingly, some European countries have taken strong stances against these commercial practices. For example, in 2014 the French Council of State has deemed private ownership over personal data incompatible with the "right to informational self-determination" 34 , while the National Digital Council (CNNum) has declared its opposition to applying private ownership rights to personal data. The main reason given, which is in line with the need to respect the collective nature of the negotiation of personal data, was to balance 'the power relationship between consumers and businesses'.

38. The sale of data under a private ownership system would generate only inconsequential incomes and would further foster socio-economic inequalities. Moreover, the framing of the current 'privatization of privacy' proposals, with their excessive focus on the commercial element, would do away with the role of governments as participants in this market, in their capacity as buyers of citizens' personal data for surveillance purposes. [START_REF] Soghoian | The Spies We Trust: Third Party Service Providers and Law Enforcement Surveillance[END_REF] With a private ownership system, citizens would be in even less of a position to defend themselves and their negotiating power would therefore be weakened.

39. These issues are destined to become only more pressing with the expansion of the Internet of Things. One of its immediate repercussions is the upsetting of the balance between the 'Internet of publication' (which includes contents voluntarily put online by users) and the 'Internet of emission' (which includes data and metadata transmitted by our smart devices, over which users have little or no configurating and negotiating prospects). To date, in this new paradigm consent to sharing personal data is largely assumed by default, on an opt-out basis, and has not been accompanied by any attempts to raise awareness and understanding of the related personal and social issues. The capture of data emitted by meters, electronics, and smart appliances installed in private homes, as well as by public transports and ambient components of urban infrastructure (sensors, cameras, etc.), is already a part of our everyday lives. However, it is destined to reach a critical point at which neither individual rights nor measures to protect the private ownership of personal data will be enough to counter the increasingly powerful forms of data expropriation to which citizens will be exposed. In the political context that is currently brewing, legislation based on individual rights would be nothing but a paper tiger. 40. Breaking free of the conceptual trap of the 'privatization of privacy' means both recognizing the dangers of reducing the elements that make up the connected lives of citizens to purely commercial assets, and the need to move away from the logic of personalized privacy, so that it can be envisioned as a collective concern, sitting within a framework that respects autonomy and liberties.

  20 Castro, Daniel (2013). How Much Will PRISM Cost the U.S. Cloud Computing Industry?. ://www.itif.org/publications/how-much-will-prism-cost-us-cloud-computing-industry 21 "The task of testing oneself, examining oneself, monitoring oneself in a series of clearly defined exercises, makes the question of truth -the truth concerning what one is, what one does, and what one is capable of doing -central to the formation of the ethical subject.", Foucault, Michel (1984) Le Souci de soi, Gallimard, Paris.

Merzeau, Louise (2013) L'intelligence des traces. Intellectica, 59 (1): pp.115-135.

Tubaro, Paola, Casilli, Antonio A. & Yasaman Sarabi (2014). Against the Hypothesis of the End-of-Privacy. An agent-based modelling approach to social media, New York: Springer.

Sprenger, Polly (1999). Sun on Privacy: "Get Over It". Wired, January 26, http://archive.wired.com/politics/law/news/1999/01/17538

Ferenstein, Gregory (2013). Google's Cerf Says "Privacy May Be An Anomaly". Historically, He's Right. TechCrunch, November 20, http://techcrunch.com/2013/11/20/googles-cerf-says-privacy-may-be-an-anomaly-historicallyhes-right/

 16 The Zuckerberg Files (2010) Facebook CEO Mark Zuckerberg: TechCrunch Interview At The Crunchies, transcript, January 8, http://dc.uwm.edu/zuckerberg_files_transcripts/32/

Norberg, Patricia A., Horne, Daniel R. &, David A. Horne (2007). The Privacy Paradox: Personal Information Disclosure Intentions versus Behaviors. Journal of Consumer Affairs, 41 (1): 100-126.

Rainie, Lee, Kiesler, Sara, Kang, Ruogu & Mary Madden (2013). Anonymity, Privacy, and Security Online. Pew Research Center's Internet & American Life Project, http://www.pewinternet.org/2013/09/05/anonymity-privacy-and-security-online/

Pailler, Fred & Antonio A. Casilli (2015). S'inscrire en faux : les fakes et les politiques de l'identité des publics connectés. Communication, 33(2) [forthcoming].

Arendt, Hannah (1958). The Human Condition. Chicago: The University of Chicago Press.

The following pages take up and develop the topics discussed in Casilli, Antonio A. (2013). Contre l'hypothèse de la fin de la vie privée. La négociation de la privacy dans les médias sociaux. Revue française des sciences de l'information et de la communication, 3 (1), http://rfsic.revues.org/630

Boyd v. United States (1886) 116 U.S. 616

Cf Donath, Judith (2007). Signals in social supernets. Journal of Computer-Mediated Communication, 13 (1): 231-251.

.parliament.uk/bills/2014-15/dataretentionandinvestigatorypowers.html 4 Anti-terrorism Act, 2015 https://openparliament.ca/bills/41-2/C-51/ 5 Telecommunications (Interception and Access) Amendment (Data Retention) Bill 2015 http://www.aph.gov.au/Parliamentary_Business/Bills_Legislation/Bills_Search_Results/Result ?bId=r5375 6 Périès, Gabriel (2013). Les dilemmes européens de la gestion des identités numériques : entre la confiance et la sécurité nationale. CVPIP (Personal Data Values and Policies Chair), Paris, Institut Mines-Télécom, 17 September http://cvpip.wp.mines-telecom.fr/2013/09/17/deuxiemerencontre-de-la-chaire-le-mardi-17-septembre-2013-de-17h-a-19h-a-linstitut-mines-telecom/ 7 Rosanvallon, Pierre (2000). La démocratie inachevée. Histoire de la souveraineté du peuple en France. Paris: Gallimard. 8 Grubb, Ben (2014).

sources. Sydney Morning Herald, August 22, http://www.smh.com.au/digitallife/digital-life-news/metadata-ambiguity-to-be-resolved-by-government-data-retention-policypaper-sources-


S ¸tefan Ciobâcȃ

Dorel Lucanu

Vlad Rusu

Grigore Roşu

A Theoretical Foundation for Programming Languages Aggregation

Programming languages should be formally specified in order to reason about programs written in them. We show that, given two formally specified programming languages, it is possible to construct the formal semantics of an aggregated language, in which programs consist of pairs of programs from the initial languages. The construction is based on algebraic techniques and it can be used to reduce relational properties (such as equivalence of programs) to reachability properties (in the aggregated language).

Introduction

In this paper we are concerned with the problem of language aggregation: given two programming languages (in some formalism), construct a new language in which programs consist of pairs of programs from the original languages. Furthermore, a program (P, Q) in the aggregated language should behave as if the programs P and Q (in the initial languages) would run interleaved or in parallel.

The main motivation behind the construction of the aggregated language is to be able to reduce reasoning about relational properties of programs (such as the equivalence of two programs P and Q) to reasoning about a single program (the aggregated program (P, Q)). We have shown [START_REF] S ¸tefan | Reducing Partial Equivalence to Partial Correctness[END_REF] for example that partial equivalence of programs reduces to partial correctness in an aggregated language. In general, aggregation is important because there are fewer results and tools for relational properties (e.g. equivalence of programs) than single program properties (e.g. partial correctness). All of our constructions are effective and therefore aggregation can be implemented as a module in a language framework such as K [START_REF] Roşu | An overview of the K semantic framework[END_REF].

The main difficulty in aggregating two languages is making sure that there is a link between the datatypes being shared by the two languages. For example, if both languages have variables of type natural numbers, it is important that the naturals be interpreted consistently in the aggregated language in order to be able to express properties such as the equality of a variable in the first language with a variable in the second language. We use known results like pushouts of first-order signatures and amalgamation of first-order models in order to formalize the sharing of information between the two languages. In order to show that the language resulting from the construction is indeed the language we want (i.e. that is has the desirable properties), we have to show several non-trivial results about aggregated configurations (Lemmas 1 and 3) and about the aggregated semantics (Theorems 3, 4 and 5) that were not known before.

In this paper, we show that if the two languages are formalized by their matching logic semantics [START_REF] Roşu | Matching Logic: An Alternative to Hoare/Floyd Logic[END_REF], then the matching logic semantics of the aggregated language can also be constructed. The main advantage of a matching logic semantics is that it allows to faithfully express several operational semantics ( [START_REF] Roşu | A rewriting logic approach to operational semantics[END_REF]) and that a Hoare-like proof system can be obtained for free directly from the semantics [START_REF] Roşu | One-Path Reachability Logic[END_REF][START_REF] ¸tefan Ciobâcȃ | All-Path Reachability Logic[END_REF]. Therefore, our method allows one to reason about relational properties (such as equivalence) of programs written in two potentially different programming languages "for free", starting from the matching logic semantics of the languages.

Topmost Matching Logic

Matching logic was introduced by Roşu et al. ( [START_REF] Roşu | Matching Logic: An Alternative to Hoare/Floyd Logic[END_REF][START_REF] Roşu | Matching Logic: A Logic for Structural Reasoning[END_REF]) for specifying programming languages and reasoning about programs. In this section, we recall topmost matching logic, a subset of the full matching logic theory described in [START_REF] Roşu | Matching Logic (invited talk)[END_REF]. For simplicity, we use "matching logic" instead of "topmost matching logic" in this paper.

Signature

A matching logic signature (Cfg, S, Σ, Π) extends a many-sorted first order signature (S, Σ, Π) (where S is the set of sorts, Σ is the many-sorted set of function symbols and Π is the many-sorted set of predicate symbols) with a sort Cfg ∈ S of configurations. By Var we denote the (sorted) set of variables. By T s (Var ) we denote the set of (well-sorted) terms of sort s built from function symbols in Σ and variables in Var . Matching logic signatures are used to define the abstract syntax of programming languages. The difference between the operators + , * , etc. and their correspondants + Int , * Int, etc. is that the former are the syntactic language constructs for addition, etc., while the latter are the actual function symbols denoting integer addition, etc.

Σ 0 = { + , -, * , / , < , == } ∪ { + Int , -Int , * Int , / Int , < Int , <= Int , == Int } Σ I = Σ 0 ∪ { := , skip, ; , if then else , while do , , } Σ F = Σ 0 ∪ { , letrec = in , if then else , µ . , λ . , }.
The functions above are written in Maude-like notation [START_REF] Clavel | All About Maude, A High-Performance Logical Framework[END_REF], the underscore ( ) denoting the position of an argument. Althought not written explicitly above, the signatures also include the one-argument injections needed to inject sorts like Int and Id into ExpI.

Syntax

Given a matching logic signature (Cfg, S, Σ, Π), the set of matching logic formulae is given by the following grammar:

ϕ ::= P (t 1 , . . . , t n ), ¬ϕ, ϕ ∧ ϕ, ∃x.ϕ, π, where P ranges over Π, t 1 , . . . , t n are terms of the appropriate sort for the predicate P , x ∈ Var is a variable and π ∈ T Cfg (Var ) is a term of sort Cfg.

Matching logic formulae include the classical constructs in first-order logic (predicates P (t 1 , . . . , t n ), negation, conjunction and existential quantifier) and also a new construct π, called basic pattern, which allows to use terms of sort Cfg as atomic formulae. We also assume that the other first-order connectives (disjunction -∨, implication -→, universal quantifier -∀) are available and interpreted as usual as syntactic sugar over the existing connectives.

Example 2. The expression

while (E) S, x → a y → b ∧ a < Int b
is a (CfgI, S I , Σ I , Π I )-matching logic formula, where (CfgI, S I , Σ I , Π I ) is that given in Figure 1.

We distinguish two particular types of matching logic formulae: Definition 1. A matching logic formula is patternless if it conforms to the following grammar: ϕ pless ::= P (t 1 , . . . , t n ), ¬ϕ pless , ϕ pless ∧ ϕ pless , ∃x.ϕ pless .

Patternless matching logic formulae simply do not contain basic patterns. Therefore they can be identified with FOL formulae. The second particular type of formulae we consider are pure formulae: Definition 2. A matching logic formula is pure if it conforms to the following grammar:

ϕ pure ::= π, ϕ pure ∧ ϕ pless , ∃x.ϕ pure .

Pure formulae contain at least one basic pattern and no basic pattern appears under negation.

Semantics

We denote by T a first-order model for the many-sorted first-order signature (S, Σ, Π) that assigns sets to sorts, functions to function symbols and predicates to predicate symbols. By T o we denote the interpretation of the object o in the model T . Well-sorted valuations are denoted by ρ : Var → T . Elements of T Cfg (the set interpreting the sort of configurations) are denoted by the greek letter γ ∈ T Cfg and are called configurations.

Matching logic formulae are interpreted in the presence of a (first-order) model T , a (well-sorted) valuation ρ and an element γ ∈ T Cfg .

(Var ) if ρ(π) = γ.
The first four cases are as in first-order logic and the last case (for basic patterns) is new. The semantics of basic patterns is given by matching the element γ in the presence of which matching logic formulae are evaluated. This is where the name of matching logic comes from. When two basic patterns are connected by a logical and (∧) in the formula, the element γ has to match both basic patterns, hence ∧ plays the role of intersection. Using basic patterns under implications, logical or and existential/universal quantifiers makes it possible to express several interesting properties, but this is outside the scope of the current article.

Example 3. Let T I denote the model for Σ I that interprets Int as the set of integers, the function and the predicate symbols over Int with the usual functions and predicates, respectively, and the function symbols corresponding to the BNF productions as term constructors. If

γ = while (x<y) x := x+1;, x → 2 y → 5 x, σ ⇒ eval (σ, x), σ i1 op i2, σ ⇒ i1 op Int i2, σ X := I, σ ⇒ skip, σ[I/X] skip;S, σ ⇒ S, σ if I then S1 else S2, σ ∧ I = 0 ⇒ S1, σ if 0 then S1 else S2, σ ⇒ S2, σ while E do S, σ ⇒ if E then S; while E do S else skip, σ C[code], σ ⇒ C[code ], σ if code, σ ⇒ code , σ
where

C ::= | C op E | i op C | if C then S1 else S2 | v := C | C; S
T I , γ, ρ |= while (E) S, x → a y → b ∧ a < Int b.
The Σ F -model T F is defined in a similar way. If

γ = letrec f x = if (x<1) then 1 else x*f(x-1) in f(5)
and ρ (F ) = f, ρ (X) = x and

ρ (E 1 ) = if (x<1) then 1 else x*f(x-1), ρ (E 2 ) = f(5), then T F , γ , ρ |= letrec F X = E 1 in E 2 ∧ true.

Reachability Logic

While matching logic allows to reason about individual configurations (of a program), reachability logic builds on matching logic to allow to reason and define the dynamic behaviour of programs.

Syntax

Reachability logic formulae are constructed in the presence of a matching logic signature (Cfg, S, Σ, Π) as pairs of matching logic formulae: Definition 4. A reachability logic formula (or equivalently, a reachability rule) ϕ ⇒ ϕ is a pair of matching logic formulae.

The intuition behind reachability formulae is that a configuration matching ϕ advances into a configuration matching ϕ .

C[code], σ ⇒ C[code ], σ if code, σ ⇒ code , σ , (resp. C[c] ⇒ C[c ] if c ⇒ c
) is a rule schemata that defines an infinite set of reachability logic formulas.

I1op I2 ⇒ I1op Int I2 if I then E1 else E2 ∧ i = 0 ⇒ E1 if 0 then E1 else E2 ⇒ E2 letrec F X = E in E ⇒ E [f → (µF.λX.E)] (λX.E) V ⇒ E[V /X] µX.E ⇒ E[X → (µX.E)] C[c] ⇒ C[c ] if c ⇒ c
where

C ::= | C op e | if C then e1 else e2 | C e | v C Fig. 3.
Specifying the semantics of FUN as a set AF of reachability rules schemata. op ranges over the binary function symbols and op Int is their denotation in TF

Semantics

Reachability logic formulae are interpreted in the presence of a first-order model T and a (well-sorted) valuation ρ : Var → T as in the case of matching logic, and also in the presence of a transition relation -→ ⊆ T Cfg × T Cfg over the set of configurations T Cfg . Intuitively, a reachability logic formula ϕ ⇒ ϕ holds if any configuration matched by ϕ reaches (in one step) a configuration matched by the formula ϕ . Note that the one-step requirement we work with in this article defines a satisfaction relation that is different from the ones used in the previous presentations [START_REF] Roşu | One-Path Reachability Logic[END_REF][START_REF] ¸tefan Ciobâcȃ | All-Path Reachability Logic[END_REF] of reachability logic. The satisfaction relation defined here is mainly used to specify transition systems. Note that the free variables of ϕ and the free variables of ϕ are "shared" in the reachability formula, in the sense that both are interpreted by the same valuation.

Example 5. If if (1) then x=x+y else x := 0, x → 2 y → 5 ⇒ x=x+y, x → 2 y → 5 and ϕ ⇒ ϕ is if (I) then S 1 else S 2 , σ ∧ I = Int 0 ⇒ S 1 , σ , then we have T I , -→, ρ |= ϕ ⇒ ϕ , where ρ(I) = 1, ρ(S 1 ) = x := x+y, ρ(S 2 ) = x := 0, and ρ(σ) = x → 2 y → 5.
If the valuation ρ is missing, the free variables of reachability rules are interpreted universally: Definition 6. Given a first-order model T and a transition relation -→, we say that the pair (T , -→) is a model of ϕ ⇒ ϕ , written

T , -→ |= ϕ ⇒ ϕ if, for all (well-sorted) valuations ρ : Var → T , we have that T , -→, ρ |= ϕ ⇒ ϕ .
The universal interpretation of the free variables is justified in the following section, but note that it is not unusual to do so: for example, the same happens with first-oder clauses, where the variables are (implicitly) universally quantified.

Language Semantics

In this section, we show that reachability formulae can be used to formally define the operational semantics of a programming language. We consider that a matching logic signature (Cfg, S, Σ, Π) is fixed. Definition 7. A (Cfg, S, Σ, Π)-programming language is a pair (T , -→) of a first-order model T of (Cfg, S, Σ, Π) and a transition relation -→ ⊆ T Cfg ×T Cfg .

When (Cfg, S, Σ, Π) is understood from the context, we omit it and write programming language instead of (Cfg, S, Σ, Π)-programming language.

The matching logic signature defines the syntax of the language, the model T mainly defines program configurations and -→ defines the (one-step) transition relation between configurations. Let A be a set of reachability formulae (the axioms of the language). Definition 8. We say that (T , -→) is a model of A, and we write (T , -→) |= A if (T , -→) |= ϕ ⇒ ϕ for every reachability formula ϕ ⇒ ϕ ∈ A.

F , -→ F ) |= A F , i.e., (T F , -→ F ) is a model of A F .
Therefore, the set A of reachability rules are considered to be the specification (the formal semantics) of any language (T , -→) that is a model of the rules. In [START_REF] Roşu | A rewriting logic approach to operational semantics[END_REF] it is shown that any operational semantics (small-step SOS, big-step SOS, reduction contexts, etc) can be faithfully captured by a (possibly infinite) set of reachability rules. Moreover, all such reachability rules from the semantics are pure: Definition 9. A reachability formula ϕ ⇒ ϕ is pure if both ϕ and ϕ are pure.

From here on, we assume that the formal semantics of any language is given as a (possibly infinite) set of pure reachability formulae.

We assume two signatures (Cfg 1 , S 1 , Σ 1 , Π 1 ) and (Cfg 2 , S 2 , Σ 2 , Π 2 ) for two languages (T 1 , -→ 1 ) and (T 2 , -→ 2 ) specified by the sets A 1 and A 2 of reachability rules.

In this section, we construct the aggregated signature (Cfg, S, Σ, Π) of the aggregated language from the signature of the first language and the signature of the second language. Also, we define the aggregated language (T , -→) itself and show how to constructively give the aggregated axioms A of the new language from the initial languages.

Signature Aggregation

This subsection is dedicated to showing how to construct the aggregated signature (Cfg, S, Σ, Π) from the individual signature (Cfg 1 , S 1 , Σ 1 , Π 1 ) (of the first language) and (Cfg 2 , S 2 , Σ 2 , Π 2 ) (of the second language).

The most delicate part is to make sure that the sorts, function and predicate symbols "shared" between the two language are identified in the aggregated configuration, even if their names are not the same in the first and in the second language.

Therefore, we assume that there exists a first-order signature (S 0 , Σ 0 , Π 0 ) that the two languages have in common. This means there exist two morphisms

h 1 : (S 0 , Σ 0 , Π 0 ) → (S 1 , Σ 1 , Π 1 ) and h 2 : (S 0 , Σ 0 , Π 0 ) → (S 2 , Σ 2 , Π 2 ).
Example 7. For the signatures of the two languages, IMP and FUN, we have S 0 = {Int, Id, Exp}, Σ 0 that was defined on Page 1, and Π 0 = Π 1 , Π 2 . The morphisms h 1 and h 2 are given by the component inclusions.

The following theorem (the pushout theorem) allows us to combine the two signatures into a single signature, while identifying the objects shared between them. This result is not new, see, for example, [START_REF] Diaconescu | Institution-independent Model Theory[END_REF].

Theorem 1 (Pushout of Signatures). Let (S 1 , Σ 1 , Π 1 ), (S 2 , Σ 2 , Π 2 ) and (S 0 , Σ 0 , Π 0 ) be many-sorted FOL signatures, h 1 a morphism from (S 0 , Σ 0 , Π 0 ) to (S 1 , Σ 1 , Π 1 ) and h 2 a morphism from (S 0 , Σ 0 , Π 0 ) to (S 2 , Σ 2 , Π 2 ).

Then the diagram (S 1 , Σ 1 , Π 1 ) h1 ←-(S 0 , Σ 0 , Π 0 ) h2 -→ (S 2 , Σ 2 , Π 2 )
admits a pushout, i.e., there exists a tuple (h 1 , (S , Σ , Π ), h 2 ) with h 1 a morphism from (S 1 , Σ 1 , Π 1 ) to (S , Σ , Π ) and h 2 a morphism from (S 2 , Σ 2 , Π 2 ) to (S , Σ , Π ) such that:

1. (commutativity) h 1 (h 1 (x)) = h 2 (h 2 (x)) for any object x from the signature (S 0 , Σ 0 , Π 0 ) and 2. (minimality) if there exist (S , Σ , Π ) and morphisms

h 1 from (S 1 , Σ 1 , Π 1 ) to (S , Σ , Π ) and h 2 from (S 2 , Σ 2 , Π 2 ) to (S , Σ , Π ) with h 1 (h 1 (x)) = h 2 (h 2 (x)
) for all x ∈ S 0 , ∪Σ 0 ∪ Π 0 , then there exists a morphism h from (S , Σ , Π ) to (S , Σ , Π ).

(S0, Σ0, Π0)

(S2, Σ2, Π2) (S1, Σ1, Π1) (S , Σ , Π ) h2 h1 h 1 h 2
Fig. 4. Push-out diagram assumed throughout the paper.

Furthermore, the pushout is unique (up to isomorphisms). The push-out is summarised in Figure 4.

The first step to obtain the aggregated signature is to apply the push-out theorem in order to obtain the intermediate signature (S , Σ , Π ) and the two morphisms

h 1 : (S 1 , Σ 1 , Π 1 ) → (S , Σ , Π ) and h 2 : (S 2 , Σ 2 , Π 2 ) → (S , Σ , Π ).
The first-order signature (S , Σ , Π ) contains all of the objects from the initial signatures (properly renamed to account for shared objects), but it does not yet have a sort for aggregated configurations. Let Cfg = h 1 (Cfg 1 ) and Cfg 2 = h 2 (Cfg 2 ) be the names of the sorts of configurations in the new signature.

We therefore choose a fresh sort Cfg for aggregated configurations and we let S = S {Cfg} be the set of sorts. The signature Σ contains, in addition to the symbols in Σ , a pairing symbol and the respective projections. Formally,

Σ = Σ { , : Cfg 1 × Cfg 2 → Cfg, pr 1 : Cfg → Cfg 1 , pr 2 : Cfg → Cfg 2 }.
The pairing symbol , takes as input two configurations of the initial languages and returns a configuration of the aggregated language. The projection operations pr 1 and pr 2 take an aggregated configuration and deconstruct it into the initial configurations. Finally, we let Π = Π .

The signature (Cfg, S, Σ, Π) is the aggregated signature of the language and its construction is summarised in Figure 5.

If h : (S, Σ, Π) → (S , Σ , Π ) is a morphism between the two first order signatures, we extend h to terms as expected: if t ∈ T s (Σ), then h(t) ∈ T h(s) (Σ ). We also extend h to transform matching logic formula in the signature (Cfg, S, Σ, Π) to matching logic formula in the signature (h(Cfg), S , Σ , Π ) as follows:

1. h(ϕ 1 ∧ ϕ 2 ) = h(ϕ 1 ) ∧ h(ϕ 2 ), 2. h(∃x.ϕ 1 ) = ∃x.h(ϕ 1 ), 3. h(¬ϕ 1 ) = ¬h(ϕ 1 ) and 4. h(P (t 1 , . . . , t n )) = P (h(t 1 ), . . . , h(t n ))).
Note that there is no need to have a case for computing h(π), since a basic pattern π is nothing but a term. Therefore h(π) is already defined. We also extend h to transform reachability formulae over the signature (Cfg, S, Σ, Π) into reachability formulae over the signature (h(Cfg), S , Σ , Π ):

h(ϕ ⇒ ϕ ) = h(ϕ) ⇒ h(ϕ ). (S0, Σ0, Π0) (Cfg 1 , S1, Σ1, Π1) (Cfg 2 , S2, Σ2, Π2) (S1, Σ1, Π1) (S2, Σ2, Π2) (S , Σ , Π ) (S, Σ, Π) (Cfg, S, Σ, Π) h2 h1 h 1 h 2
add Cfg, , , pr 1 , pr 2 "forget" Cfg "forget" Cfg 1 "forget" Cfg 2 Fig. 5. The aggregation of the two signatures.

Model Amalgamation

In this subsection, given two models T 1 and T 2 for the matching logic signatures (Cfg 1 , S 1 , Σ 1 , Π 1 ) and (Cfg 2 , S 2 , Σ 2 , Π 2 ), we show how to construct a model T for the aggregated signature (Cfg, S, Σ, Π) above.

In order to construct such a model, we need to make sure that the two models T 1 and T 2 agree on the common part of the signature. Formally, we assume that there exists a model T 0 of the signature (S 0 , Σ 0 , Π 0 ) such that T 1 h1 = T 0 = T 2 h2 (i.e. the reduct of T 1 through h 1 is the same as the reduct of T 2 through h 2 ). Figure 6 below summarizes the construction of T .

We can combine the two languages through the model amalgamation theorem. The theorem is not new (see for example [START_REF] Schröder | Amalgamation in the semantics of CASL[END_REF]). A proof can also be found in our technical report [START_REF] Ciobâcȃ | A Language-Independent Proof System for Mutual Program Equivalence[END_REF].

Theorem 2 (Amalgamation).

If T 1 , T 2 and T 0 are models of (S 1 , Σ 1 , Π 1 ), (S 2 , Σ 2 , Π 2 ) and respectively (S 0 , Σ 0 , Π 0 ) such that T 1 h1 = T 0 = T 2 h2 , there exists a unique model T of (S , Σ , Π ) such that T h 2 = T 2 and T h 1 = T 1 .

In order to obtain the model T for the aggregated signature (Cfg, S, Σ, Π), we need to augment T to interpret the Cfg sort, the pairing symbol , and the projection symbols pr 1 and pr 2 . Formally, we define T as follows:

1. T Cfg = T Cfg 1 × T Cfg 2 , 2. T , (γ 1 , γ 2 ) = (γ 1 , γ 2 ) for any γ 1 ∈ T Cfg 1 and any γ 2 ∈ T Cfg 2 , 3. T pr 1 ((γ 1 , γ 2 )) = γ 1 for any (γ 1 , γ 2 ) ∈ T Cfg = T Cfg 1 × T Cfg 2 , 4. T pr 2 ((γ 1 , γ 2 )) = γ 2 for any (γ 1 , γ 2 ) ∈ T Cfg = T Cfg 1 × T Cfg 2
, and The aggregated signature and model have the following properties:

(S0, Σ0, Π0) T0 T2 (S1, Σ1, Π1) T1 (S2, Σ2, Π2) (Cfg 1 , S1, Σ1, Π1) (Cfg 2 , S2, Σ2, Π2) (S , Σ , Π ) T (S, Σ, Π) (Cfg, S, Σ, Π) T h2 h1 h 1 h 2 add Cfg, , , pr 1 , pr 2 h1 h2 h 1 h 2 "forget" Cfg "forget" Cfg 1 "forget" Cfg 2
Lemma 1. For any basic patterns π 1 ∈ T Cfg 1 (Var ) and π 2 ∈ T Cfg 2 (Var ), for any aggregated configuration (γ 1 , γ 2 ) ∈ T Cfg , for any (well-sorted) valuation ρ, we have that

T , (γ 1 , γ 2 ), ρ |= π 1 , π 2 iff T 1 , γ 1 , ρ h 1 (S1) |= π 1 and T 2 , γ 2 , ρ h 2 (S2) |= π 2 .
Proof. We show the direct implication first. Assume T , (γ 1 , γ 2 ), ρ |= π 1 , π 2 . By definition, we have that ρ( π 1 , π 2 ) = (γ 1 , γ 2 ). By the interpretation of , in the model T , we have that

ρ h 1 (S1) (π 1 ) = γ 1 and ρ h 2 (S2) (π 2 ) = γ 2 . But this is equivalent to T 1 , γ 1 , ρ h 1 (S1) |= π 1 and T 2 , γ 2 , ρ h 2 (S2) |= π 2 ,
which is what we had to show. For the reverse direction, we assume that

T 1 , γ 1 , ρ h 1 (S1) |= π 1 and that T 2 , γ 2 , ρ h 2 (S2) |= π 2 . Therefore ρ h 1 (S1) (π 1 ) = π 1 and ρ h 2 (S2) (π 2 ) = π 2 , which implies, by the interpretation of , in T , that ρ( π 1 , π 2 ) = (γ 1 , γ 2 ). But this is equivalent to T , (γ 1 , γ 2 ), ρ |= π 1 , π 2 ,
which is what we had to prove.

Language Aggregation

Having shown how to construct the matching logic signature (Cfg, S, Σ, Π) and model T for the aggregated language, we now show how the transition relation -→ for the aggregated language is defined and how to construct the axioms A of the aggregated language from the axioms A 1 and A 2 of the initial languages.

We identify three types of language aggregations, depending on how the -→ transition relation is defined from -→ 1 and -→ 2 . Each of the three constructions could be useful in various contexts:

1. -→ 1 ⊗ a -→ 2 is the asynchronous interleaving product of the two transition relations, i.e. (γ 1 , γ 2 )-→(γ 1 , γ 2 ) if

γ 1 = γ 1 and γ 2 -→ 2 γ 2 or γ 1 -→ 1 γ 1 and γ 2 = γ 2 , 2. -→ 1 ⊗ p -→ 2
is the parallel product of the two transition relations, i.e.

(γ 1 , γ 2 )-→(γ 1 , γ 2 ) if γ 1 -→ 1 γ 1 and γ 2 -→ 2 γ 2 , 3. finally, -→ 1 ⊗-→ 2 = (-→ 1 ⊗ a -→ 2 )∪(-→ 1 ⊗ p -→ 2 ) is the (general) product of -→ 1 and -→ 2 .
The asynchronous product with interleaving semantics means that in one step of the aggregated language, either the left-hand side takes a step (in the first language) or the right-hand side takes a step (in the second language). The parallel product forces both sides to take steps simultaneously. The (general) product requires at least one side to take a step and it allows (but not requires) the other side to do the same.

Constructing the Axioms for the Three Products

We next show how to construct a set of axioms A for the aggregated language from the set of axioms A 1 and A 2 of the initial languages, depending on which of the three constructions is chosen for the aggregated transition relation. The main result is that, for each of the three constructions, the transition relation is a model of the aggregated axioms. This means that we can construct the formal semantics of the aggregated language directly from the formal semantics of the initial languages.

Let A 1 be a set of pure reachability rules over the signature (Cfg 1 , S 1 , Σ 1 , Π 1 ) that capture the semantics of the first language (the axioms of the first language): T 1 , -→ 1 |= A 1 . Let A 2 be a set of pure reachability rules over the signature (Cfg 2 , S 2 , Σ 2 , Π 2 ) that capture the semantics of the second language (the axioms of the second language):

T 2 , -→ 2 |= A 2 .
In order to define the axioms for the aggregated language, we need a way to transform reachability formulae from the two initial signatures into reachability formulae of the target signature. This is performed with the help of the following function:

Definition 10. We define the function ι i

x (for i ∈ {1, 2} and x a distinguished variable in Var of sort Cfg i ) that takes as input a matching logic formula over

(Cfg 1 , S 1 , Σ 1 , Π 1 ) (respectively (Cfg 2 , S 2 , Σ 2 , Π 2 )
) and changes all basic patterns π into π, x (respectively x, π ) in order to obtain a formula over (Cfg, S, Σ, Π):

1. ι 1 x (π) = h 1 (π), x 2. ι 2 x (π) = x, h 2 (π) 3. ι i x (ϕ 1 ∧ ϕ 2 ) = ι i x (ϕ 1 ) ∧ ι i x (ϕ 2 ), 4. ι i x (∃y.ϕ 1 ) = ∃y.ι i x (ϕ 1 ), 5. ι i x (¬ϕ 1 ) = ¬ι i x (ϕ 1 ) and 6. ι i x (P (t 1 , . . . , t n )) = P (h i (t 1 ), . . . , h i (t n )). Example 8. If ϕ 1 is the matching formula while (E) S, σ ∧ eval (σ, E) = Int 0 and ϕ 2 is letrec f x = if (I) then E 1 else E 2 in f(x) ∧ I < Int 5, then ι i x (ϕ 1 ) is while (E) S, σ , x ∧ eval (σ, E) = Int 0 and ι i x (ϕ 2 ) is the aggregate formula x, letrec f x = if (I) then E 1 else E 2 in f(x) ∧ I < Int 5.
Next, we show the link, in terms of matching logic formulae, between the aggregated model and the initial model. Lemma 2. Let ϕ 1 and ϕ 2 be matching logic formulae over (Cfg 1 , S 1 , Σ 1 , Π 1 ) and respectively (Cfg 2 , S 2 , Σ 2 , Π 2 ). For any aggregated configuration (γ 1 , γ 2 ) ∈ T Cfg , for any (well-sorted) valuation ρ, if x is a fresh variable, we have that

T , (γ 1 , γ 2 ), ρ |= ι i x (ϕ i ) iff T i , γ i , ρ h i (Si) |= ϕ i .
Proof. For simplicity, we assume that i = 1 (since the case with i = 2 is analogous). We prove the lemma by structural induction on ϕ 1 . We only show the case of negation, the other cases being similar:

-if ϕ 1 = ¬ϕ 1 , then T , (γ 1 , γ 2 ), ρ |= ι 1 x (ϕ 1 ) iff T , (γ 1 , γ 2 ), ρ |= ¬ι 1 x (ϕ 1 ) iff T , (γ 1 , γ 2 ), ρ |= ι 1 x (ϕ 1 ) iff T 1 , γ 1 , ρ h 1 (S1) |= ϕ 1 iff T 1 , γ 1 , ρ h 1 (S1) |= ¬ϕ 1
Lemma 3. For any pure matching logic formulae ϕ 1 over (Cfg 1 , S 1 , Σ 1 , Π 1 ) and ϕ 2 over (Cfg 2 , S 2 , Σ 2 , Π 2 ), for any aggregated configuration (γ 1 , γ 2 ) ∈ T Cfg , for any (well-sorted) valuation ρ, if x is a fresh variable, we have that

T , (γ 1 , γ 2 ), ρ |= ι i x (ϕ i ) iff T i , γ i , ρ h i (Si) |= ϕ i and ρ(x) = γ 3-i .
Proof. For simplicity, we assume that i = 1 (since the case with i = 2 is analogous). We prove the lemma by structural induction on ϕ 1 , showing that

T , (γ 1 , γ 2 ), ρ |= ι 1 x (ϕ 1 ) iff T 1 , γ 1 , ρ h 1 (S1) |= ϕ 1 and ρ(x) = γ 2 .
We distinguish the following cases:

1. if ϕ 1 = π, then ι 1 x (ϕ 1 ) = (h 1 (π), x). We have that T , (γ 1 , γ 2 ), ρ |= ι 1 x (ϕ 1 ) iff T , (γ 1 , γ 2 ), ρ |= (h 1 (π), x) iff (γ 1 , γ 2 ) = ρ(h 1 (π), x) iff γ 1 = ρ(h 1 (π)) and γ 2 = ρ(x) iff γ 1 = ρ h 1 (S1) (π) and γ 2 = ρ(x) iff T 1 , γ 1 , ρ h 1 (S1) |= π and γ 2 = ρ(x).
2. if ϕ 1 = ∃y.ϕ 1 for a variable y of sort s (with y = x since x is a fresh variable) then ι 1

x (ϕ 1 ) = ∃y.ι 1 x (ϕ 1 ). We have that

T , (γ 1 , γ 2 ), ρ |= ι 1 x (ϕ 1 ) iff T , (γ 1 , γ 2 ), ρ |= ∃y.ι 1 x (ϕ 1 ) iff there is u ∈ T 1s s.t. T , (γ 1 , γ 2 ), ρ[y → u] |= ι 1 x (ϕ 1 ) iff there is u ∈ T 1s s.t. T 1 , γ 1 , ρ[y → u] h 1 (S1) |= ϕ 1 and γ 2 = ρ[y → u](x) iff T 1 , γ 1 , ρ h 1 (S1) |= ∃y.ϕ 1 and γ 2 = ρ(x) iff T 1 , γ 1 , ρ h 1 (S1) |= ϕ 1 and γ 2 = ρ(x).
3. if ϕ 1 = ϕ 1 ∧ ϕ 2 for a pure formula ϕ 1 and a patternless formula ϕ 2 , then

ι 1 x (ϕ 1 ) = ι 1 x (ϕ 1 ) ∧ ι 1 x (ϕ 2 ). We have that T , (γ 1 , γ 2 ), ρ |= ι 1 x (ϕ 1 ) iff T , (γ 1 , γ 2 ), ρ |= ι 1 x (ϕ 1 ) ∧ ι 1 x (ϕ 2 ) iff T , (γ 1 , γ 2 ), ρ |= ι 1 x (ϕ 1 ) and T , (γ 1 , γ 2 ), ρ |= ι 1 x (ϕ 2 ) iff T 1 , γ 1 , ρ h 1 (S1) |= ϕ 1 and ρ(x) = γ 2 and T 1 , γ 1 , ρ h 1 (S1) |= ϕ 2 iff T 1 , γ 1 , ρ h 1 (S1) |= ϕ 1 ∧ ϕ 2 and ρ(x) = γ 2 iff T 1 , γ 1 , ρ h 1 (S1) |= ϕ 1 and ρ(x) = γ 2 .
In the following subsections, we define three types of aggregations for these sets of axioms, for each type of language aggregation.

The Axioms for the Asynchronous Product with Interleaving Semantics We let

A 1 ⊗ a A 2 = {ι 1 y (ϕ 1 ) ⇒ ι 1 y (ϕ 1 ) | ϕ 1 ⇒ ϕ 1 ∈ A 1 } ∪ {ι 2 x (ϕ 2 ) ⇒ ι 2 x (ϕ 2 ) | ϕ 2 ⇒ ϕ 2 ∈ A 2 }
where x is a fresh variable of sort Cfg 1 and y is a fresh variable of sort Cfg 2 . The intuition is that x captures any left-hand side and allow the right-hand to take a step while y captures any right-hand side and allow the left-hand side to take a step. We show formally that A 1 ⊗ a A 2 is indeed a formal specification of the language (T , -→ 1 ⊗ a -→ 2 ):

Theorem 3 (correctness for asynchronous product).

Let A = A 1 ⊗ a A 2 and -→ = -→ 1 ⊗ a -→ 2 .
We have that (T , -→) |= A.

Proof. We have to show that (T , -→) |= A. By definition, (T , -→) |= A if, for any reachability rule ϕ ⇒ ϕ ∈ A, we have that (T , -→) |= ϕ ⇒ ϕ . Let ϕ ⇒ ϕ ∈ A be an arbitrary reachability rule. We show that (T , -→) |= ϕ ⇒ ϕ .

As ϕ ⇒ ϕ ∈ A = A 1 ⊗ a A 2 , it follows that ϕ ⇒ ϕ = ι 1 y (ϕ 1 ) ⇒ ι 1 y (ϕ 1 ) for some ϕ 1 ⇒ ϕ 1 ∈ A 1 and a fresh variable y or that ϕ ⇒ ϕ = ι 2

x (ϕ 2 ) ⇒ ι 2 x (ϕ 2 ) for some ϕ 2 ⇒ ϕ 2 ∈ A 2 and a fresh variable x. Since the two cases are analogous, we deal only with the first and we assume therefore that ϕ ⇒ ϕ = ι 1 y (ϕ 1 ) ⇒ ι 1 y (ϕ 1 ) for some ϕ 1 ⇒ ϕ 1 ∈ A 1 and a fresh variable y. Therefore it remains to show that (T , -→) |= ι 1 y (ϕ 1 ) ⇒ ι 1 y (ϕ 1 ). Let ρ be an arbitrary valuation. Let (γ 1 , γ 2 ) ∈ T Cfg be an arbitrary configuration such that T , (γ 1 , γ 2 ), ρ |= ι 1 y (ϕ 1 ). By Lemma 3, we have

T 1 , γ 1 , ρ h 1 (S1) |= ϕ 1 and ρ(x) = γ 2 . Given that ϕ 1 ⇒ ϕ 1 ∈ A 1 and T 1 , -→ 1 |= A 1 , there exists γ 1 ∈ T 1Cfg such that γ 1 -→ 1 γ 1 and T 1 , γ 1 , ρ h 1 (S1) |= ϕ 1 . By Lemma 3, we have that T , (γ 1 , γ 2 ), ρ |= ι 1 y (ϕ 1 )
. But, by the definition of -→ (-→ = -→ 1 ⊗ a -→ 2 ), we also have that (γ 1 , γ 2 )-→(γ 1 , γ 2 ).

We have shown that for an arbitrary valuation ρ and for an arbitrary configuration (γ 1 , γ 2 ) ∈ T Cfg such that T , (γ 1 , γ 2 ), ρ |= ι 1 y (ϕ 1 ), there exists a configuration

(γ 1 , γ 2 ) such that (γ 1 , γ 2 )-→(γ 1 , γ 2 ) and T , (γ 1 , γ 2 ), ρ |= ι 1 y (ϕ 1 ). But this means that (T , -→) |= ι 1 y (ϕ 1 ) ⇒ ι 1 y (ϕ 1 )
, which is what we had to show.

The Axioms for the Parallel Product We let

A 1 ⊗ p A 2 = {ι 1 y (ϕ 1 ) ∧ ι 2 x (ϕ 2 ) ⇒ ∃x.∃y.(ι 1 y (ϕ 1 ) ∧ ι 2 x (ϕ 2 )) | ϕ 1 ⇒ ϕ 1 ∈ A 1 , ϕ 2 ⇒ ϕ 2 ∈ A 2 }
where x is a fresh variable of sort Cfg 1 and y is a fresh variable of sort Cfg 2 . The intuition is that x captures any left-hand side and y captures any right-hand side. We show formally that A 1 ⊗ p A 2 is indeed a formal specification of the language (T , -→ 1 ⊗ p -→ 2 ): Theorem 4 (correctness for parallel product).

Let

A = A 1 ⊗ p A 2 and -→ = -→ 1 ⊗ p -→ 2 . We have that (T , -→) |= A.
Proof. We have to show that (T , -→) |= A. By definition, (T , -→) |= A if, for any reachability rule ϕ ⇒ ϕ ∈ A, we have that (T , -→) |= ϕ ⇒ ϕ . Let ϕ ⇒ ϕ ∈ A be an arbitrary reachability rule. We show that (T , -

→) |= ϕ ⇒ ϕ . As ϕ ⇒ ϕ ∈ A = A 1 ⊗ p A 2 , it follows that there exist ϕ 1 ⇒ ϕ 1 ∈ A 1 , ϕ 2 ⇒ ϕ 2 ∈ A 2 , fresh variables x and y such that ϕ ⇒ ϕ = ι 1 y (ϕ 1 ) ∧ ι 2 x (ϕ 2 ) ⇒ ι 1 y (ϕ 1 ) ∧ ι 2
x (ϕ 2 ). Let ρ be an arbitrary valuation. Let (γ 1 , γ 2 ) be an arbitrary configuration such that T , (γ 1 , γ 2 ), ρ |= ι 1 y (ϕ 1 ) ∧ ι 2 x (ϕ 2 ). By the semantics of ∧, we have that T

, (γ 1 , γ 2 ), ρ |= ι 1 y (ϕ 1 ) and T , (γ 1 , γ 2 ), ρ |= ι 2 x (ϕ 2 ). By Lemma 3 it follows that T 1 , γ 1 , ρ h 1 (S1) |= ϕ 1 , ρ(y) = γ 2 , T 2 , γ 2 , ρ h 2 (S2) |= ϕ 2 and ρ(x) = γ 1 . Because T 1 , γ 1 , ρ h 1 (S1) |= ϕ 1 , ϕ 1 ⇒ ϕ 1 ∈ A 1 and T 1 , -→ 1 |= A 1 , we obtain that there exists γ 1 such that γ 1 -→ 1 γ 1 and T 1 , γ 1 , ρ h 1 (S1) |= ϕ 1 . Similarly, there exists γ 2 such that γ 2 -→ 2 γ 2 and T 2 , γ 2 , ρ h 2 (S2) |= ϕ 2 .
By Lemma 3, it follows that T , (γ

1 , γ 2 ), ρ[x → γ 1 ][y → γ 2 ] |= ι 1 y (ϕ 1 ) and T , (γ 1 , γ 2 ), ρ[x → γ 1 ][y → γ 2 ] |= ι 2 y (ϕ 2 ), which implies that T , (γ 1 , γ 2 ), ρ |= ∃x.∃y.(ι 1 y (ϕ 1 )∧ι 2 y (ϕ 2 ))
. By the definition of -→, we also have (γ 1 , γ 2 )-→(γ 1 , γ 2 ). We have started with an arbitrary valuation ρ and an arbitrary configuration (γ 1 , γ 2 ) such that T , (γ 1 , γ 2 ), ρ |= ι 1 y (ϕ 1 ) ∧ ι 2 x (ϕ 2 ) and we have shown that there exists a configuration (γ

1 , γ 2 ) such that (γ 1 , γ 2 )-→(γ 1 , γ 2 ) and T , (γ 1 , γ 2 ), ρ |= ∃x.∃y.ι 1 y (ϕ 1 ) ∧ ι 2 y (ϕ 2 ). Therefore (T , -→) |= ι 1 y (ϕ 1 ) ∧ ι 2 x (ϕ 2 ) ⇒ ∃x.∃y.ι 1 y (ϕ 1 ) ∧ ι 2 y (ϕ 2 ,
which is what we had to show.

The Axioms for the General Product For the general product, which allows for both interleaving and parallel steps, we define

A 1 ⊗ A 2 = A 1 ⊗ a A 2 ∪ A 1 ⊗ p A 2 .
The correctness result for the general product follows quickly from Theorem 3 and Theorem 4.

Theorem 5 (correctness for the general product).

Let

A = A 1 ⊗ A 2 and -→ = -→ 1 ⊗ -→ 2 .
We have that (T , -→) |= A.

Proof. Let ϕ ⇒ ϕ ∈ A be an arbitrary rule. We show that (T , -→) |= ϕ ⇒ ϕ . Let γ ∈ T Cfg be an arbitrary configuration and let ρ be an arbitrary valuation such that T , γ, ρ |= ϕ.

We distinguish two cases:

1. if ϕ ⇒ ϕ ∈ A 1 ⊗ a A 2 , then, by Theorem 3, there exists γ such that γ(-→ 1 ⊗ a -→ 2 )γ and T , γ , ρ |= ϕ . But, by definition, -→ 1 ⊗ a -→ 2 ⊆ -→. Therefore there exists γ such that γ-→γ and T , γ , ρ |= ϕ , which implies (T , -→) |= ϕ ⇒ ϕ . 2. if ϕ ⇒ ϕ ∈ A 1 ⊗ p A 2 , then, by Theorem 4, there exists γ such that γ(-→ 1 ⊗ p -→ 2 )γ and T , γ , ρ |= ϕ . But, by definition, -→ 1 ⊗ p -→ 2 ⊆ -→. Therefore there exists γ such that γ-→γ and T , γ , ρ |= ϕ , which implies (T , -→) |= ϕ ⇒ ϕ .

Conclusion and Future Work

In this paper we have shown that if two programming languages are defined using reachability logic axioms and matching-logic based semantics, then we can effectively construct products of the two languages, such that a pair of programs belonging to the product can be executed asynchronously with interleaving, in parallel (synchronised), or a combination of the two. The construction can be automated in definitional frameworks like K [START_REF] Roşu | An overview of the K semantic framework[END_REF]. A programming language definition consists of a signature and a semantics. In our approach, the signature is a many-sorted first-order signature, that includes both the syntax of the programming languages and the data structures required by the semantics. The category of the many sorted first-order signatures has colimits, in particular pushouts. Moreover, this category has the amalgamation property [START_REF] Diaconescu | Institution-independent Model Theory[END_REF][START_REF] Sannella | Foundations of Algebraic Specification and Formal Software Development[END_REF]. The semantics of the programming languages is given by transitions systems. The category of the transition systems has also several nice constructions [START_REF] Winskel | Categories in Concurrency[END_REF]. We combine these constructions in order to get the definition for aggregated languages. The approach is flexible enough to allow various aggregations. The semantics of a programming language can be specified with (one-step) reachability logic formulae. We show that the specification of the aggregated language can be obtained from the specifications of the components.

We used many-sorted first-order signatures in order to make the presentation easier to follow. However, the syntax of programming languages is usually given by BNF rules, which correspond to order-sorted first-order signatures. Unfortunately, order-sorted first-order logic does not have pushouts of signatures and the amalgamation property. There are several approaches dealing with this issue, see, e.g., [START_REF] Schröder | Amalgamation in the semantics of CASL[END_REF][START_REF] Alpuente | Order-Sorted Generalization[END_REF][START_REF] Haxthausen | Pushouts of Order-Sorted Algebraic Specifications[END_REF]. It is challenging to see which one of these is the best candidate for programming languages products and this will be investigated in the future. It is also interesting to see if the formalisation of the matching logic and reachability logic as institutions [START_REF] Chirit ¸ȃ | An Institutional Foundation for the K Semantic Framework[END_REF][START_REF] Chirit | An Institutional Foundation for the K Semantic Framework[END_REF] could help.

An interesting observation can be made for the case where -→ = -→ 1 ⊗-→ 2 . The transition system (T , -→) is a product in the category of the transitions systems [START_REF] Winskel | Categories in Concurrency[END_REF]. So, the syntax of the aggregation of the language is defined by a pushout (which is a shared sum) and the semantics by a product.

Language aggregation has uses in proving equivalence properties [START_REF] S ¸tefan Ciobâcȃ | A Language-Independent Proof System for Mutual Program Equivalence[END_REF][START_REF] S ¸tefan | Reducing Partial Equivalence to Partial Correctness[END_REF]. We intend to explore its use in proving other kinds of relations and in compiler verification.

Example 1 .

 1 The signatures (CfgI, S I , Σ I , Π I ) and (CfgF, S F , Σ F , Π F ) in Figure 1 model the syntax of an imperative and, respectively, of a functional programming language, with sorts S I = {Int, Id, Exp, ExpI, Stmt, Code, CfgI} in IMP and sorts S F = {Id, Int, Exp, ExpF, Val, CfgF} in FUN, and function symbols

Fig. 1 .

 1 Fig. 1. (CfgI, SI , ΣI , ΠI ) and (CfgF, SF , ΣF , ΠF ), the signatures of IMP and FUN, detailed in Example 1. Only the function symbols are detailed in the figure; the predicates consist of the arithmetic comparison operators: ΠI = ΠF = {=Int, <Int, ≤Int}.The difference between the operators + , * , etc. and their correspondants + Int , * Int, etc. is that the former are the syntactic language constructs for addition, etc., while the latter are the actual function symbols denoting integer addition, etc.

Fig. 2 .

 2 Fig. 2. Specifying the semantics of IMP as a set AI of reachability rules (schemata). op ranges over the binary function symbols and op Int is their denotation in TI . and ρ(E) = x<y, ρ(S) = x := x+1;, ρ(a) = 2, ρ(b) = 5 then

Example 4 .

 4 The set of reachability logic formulas A I given in Figure2are specifying the semantics of IMP and the set of reachability logic formulas A F given in Figure3are specifying the semantics of FUN. The specification

Definition 5 .

 5 Formally, the satisfaction relation |= of reachability logic is defined as follows: T , -→, ρ |= ϕ ⇒ ϕ if for any γ ∈ T Cfg such that T , γ, ρ |= ϕ there exists a γ ∈ T Cfg such that γ-→γ and T , γ , ρ |= ϕ .

Example 6 .

 6 If (T I , -→ I ) gives the semantics of IMP, then we have (T I , -→ I ) |= A I , i.e., (T I , -→ I ) is a model of A I . Similarly, if (T F , -→ F ) gives the semantics of FUN, then we must have (T

Fig. 6 .

 6 Fig. 6. Construction of amalgamated model

This paper is supported by the Sectorial Operational Programme Human Resource Development (SOP HRD), financed from the European Social Fund and by the Romanian Government under the contract number POSDRU/159/1.5/S/137750. Exp::= Id | Int | ExpI + ExpI | ExpI -ExpI | ExpI * ExpI | ExpI / ExpI | ExpI < ExpI | ExpI <= ExpI | ExpI == ExpI ExpI ::= Exp Stmt ::= Id := ExpI | skip | Stmt ; Stmt | if ExpI then Stmt else