Thomas Begin

Alexandre Brandwajn

Predicting the System Performance by Combining Calibrated Performance Models of its Components A Preliminary Study

Keywords: performance models, component-level models, overall system performance, validation, calibration

In this paper we consider the problem of combining calibrated performance models of system components in order to predict overall system performance. We focus on open workload system models, in which, under certain conditions, obtaining and validating the overall system performance measures can be a simple application of Little's law. We discuss the conditions of applicability of such a simple validation methodology, including examples of successful application, as well as examples where this approach fails.

Additionally, we propose to analyze the deviations between the model predictions and system measurements, so as to decide if they correspond to "measurement noise" or if an important system component has not been correctly represented. This approach can be used as an aid in the design of validated system performance models.

INTRODUCTION

Faced with increasingly complex system architectures, an obvious and commonly used approach is to characterize the behavior of selected system components deemed crucial to overall system performance. These performance components have then to be combined in a global system model so as to produce the desired overall system performance characterization. A number of methods have been employed to effect such combination.

For closed system models, fixed-point iterations (e.g. [START_REF] Marie | An approximate analytical method for general queueing networks[END_REF]), state-dependent equivalence (e.g. [START_REF] Brandwajn | A model of a time sharing virtual memory system solved using equivalence and decomposition methods[END_REF]), and near-decomposability (e.g. [START_REF] Courtois | Decomposability: queueing and computer system applications[END_REF]) are just a very partial list of methods that were employed in this area. The resulting overall performance model must then be validated against real or simulated system performance measurements. In an open system, under certain conditions, obtaining and validating the ACM ISBN 978-1-4503-2138-9. DOI: 10.1145/1235 overall system performance measures can be a simple application of Little's law.

In this paper, we focus on open workload system models, but several aspects of our discussion are applicable to closed systems as well. We discuss the conditions of applicability of such simple validation methodology using Little's law, including examples of successful application, as well as examples where this approach fails. Even if the applicability conditions are met, some degree of deviation between the model and the system measurements is expected. We propose to analyze these deviations, so as to decide if they correspond to simple "measurement noise" or if an important system component has not been correctly represented. As such, this approach can be used as an aid in the design of validated system performance models.

In the next section, we review related work. In Section 3 we discuss the simple use of Little's law in open models and its applicability conditions. Section 4 is devoted to examples of application of this methodology, and in Section 5 we discuss the use of this approach to discover and model hidden system components. Section 6 concludes this paper.

RELATED WORK

From the early days of computer system and network models, it was clear that "divide and conquer" approaches may be beneficial when dealing with complex systems. This gave rise to many flavors of decomposition approaches where different parts of a system are analyzed in isolation (X-model [START_REF] Herzog | Some remarks concerning the extended analytic models for system evaluation[END_REF], Kühn [START_REF] Kühn | Analysis of Complex Queueing Networks by Decomposition[END_REF], near-decomposability [START_REF] Courtois | Decomposability: queueing and computer system applications[END_REF], Norton equivalent [START_REF] Chandy | Parametric analysis of queuing networks[END_REF][START_REF] Balsamo | An extension of Norton's theorem for queueing networks[END_REF], equivalence and decomposition, etc). For instance, it is usually considerably easier to analyze the I/O subsystem separately from the complexity of CPU priority scheduling when analyzing the performance of a computer system.

Of course, we need a way to combine the results of the analysis of decomposed subsystems to obtain the desired overall system performance metrics. Depending on the decomposition approach used, such "assembly" of the decomposed models may be accomplished by replacing a whole subsystem by a simple delay representing the average time a task spends in the subsystem (X-model). In other approaches, the performance of a subsystem may be represented as a state-dependent server (Norton, near-decomposability, equivalence and decomposition). As shown in [START_REF] Brandwajn | Equivalence and decomposition in queueing systems -A unified approach[END_REF], many of these approaches may be viewed in a unified way as relying (implicitly or explicitly) on the use of marginal and conditional probabilities, which provides, at least in theory, a clean way to assemble the results of the analysis of decomposed subsystems.

Present-day systems often comprise a number of components that work together to process incoming requests. As mentioned above, it may be easier to model the performance of each individual component than directly that of the whole system. The component modeling may be performed using a constructive approach requiring knowledge and expertise, or using a "black box" approach, which parameterizes predefined models by observing the relationships between the component input and output parameters [START_REF] Begin | High-level approach to modeling of observed system behavior[END_REF][START_REF] Awad | On the Predictive Properties of Performance Models Derived through Input-Output Relationships[END_REF][START_REF] Awad | Dynamic Derivation of Analytical Performance Models in Autonomic Computing Environments[END_REF]. Several approaches have been proposed in the literature for combining component-level models into system-level performance.

In the context of disk I/O requests, a case in point is the work done by Ganger and Patt [START_REF] Ganger | The process-flow model: examining I/O performance from the system's point of view[END_REF]. At that time, accurate and sound models have been proposed for I/O subsystem performance. But it was unclear how the improvements of subsystems will be reflected in the overall system performance. Among other things, the authors stress that looking to improve the overall system performance is not directly the same as improving the I/O subsystem performance. This is because composing the performance of subsystems is not always straightforward.

The issue of predicting performance of a system based on the behavior of its components has also been addressed in the area of autonomic systems. Harbaoui et al. have proposed a framework to predict the performance of a target configuration when planning a system reconfiguration [START_REF] Harbaoui | Introducing queuing network-based performance awareness in autonomic systems[END_REF]. They decompose a distributed application into black boxes, identifying the queue model for each black box and assembling these models into a queueing network according to the candidate target configuration.

More recently, Kraft et al. have studied the response times experienced by disk I/O requests in consolidated virtualized environments [START_REF] Kraft | IO performance prediction in consolidated virtualized environments[END_REF][START_REF] Kraft | Performance models of storage contention in cloud environments[END_REF]. The authors have shown how to extrapolate the model of a single Virtual Machine (VM) into a model to predict the degree of contention when multiple VMs are accessing a remote storage server.

These previous works have emphasized the need and proposed a specific-area solution to the problem of combining models of components to represent the performance of a system. In this paper, we attempt to propose a more general framework for this problem.

FROM LOCAL TO GLOBAL SYSTEM PERFORMANCE

We concentrate on systems in which requests (tasks, transactions, jobs) arrive from an outside source, are processed by the system and eventually depart from the system. We refer to such systems as "open systems".

The system considered consists of K known components (see Figure 1) that are deemed important with respect to a specific average performance measure F (e.g. mean number of requests in system (L), mean response time (R) or loss probability (P )). We assume that we have a set of I system-level measurement points {x exp S , f exp S }, i = 1, . . . , I, where x exp S denotes the mean measured system throughput, i.e., the number of requests successfully processed by the system per time unit, and f exp S is the corresponding value of the selected performance measure. We use the superscript exp to refer to measured values and the superscript mod to denote values obtained from a model. We assume that calibrated models have been developed for each of the K system ) with k = 1, . . . , K. In order to be able to use our component models to assess overall system performance, we must know the relationship between the overall system throughput XS and the component throughputs X k , k = 1, . . . , K. This is an essential assumption. In practice, this relationship will be known from the nature of the system or from measurements. Another essential assumption is that a given request occupies a single component at a time.

Given this assumption, obviously, if the selected performance measure is the mean number of requests L, the overall mean number of requests in the system should be equal to the sum of the mean numbers obtained from the component models for throughput levels that correspond to the measured system throughput levels {x exp S }i. If the selected performance measure is the mean response time R, Little's formula [START_REF] Bolch | Queueing Networks and Markov Chains[END_REF] can be used to obtain the overall mean response time for arbitrary values of system throughput x mod S :

r mod S = K k=1 (r mod k x mod k ) x mod S (1)
Clearly, to attempt to validate this approach, we select system throughput values x mod S = x exp S and we compare the mean response time values obtained from Formula (1) with those known from measurements r exp S for the same values of system throughput.

If the loss probability is the selected performance measure, the overall loss probability can be expressed as:

p mod S = 1 1 + x mod S K k=1 x mod k .p mod k /(1-p mod k ) (2)
Formula (2) allows us to assess the overall loss probability in terms of component-level loss probabilities and request throughputs.

As mentioned earlier, for our approach to work, we need to know the relationship between the overall system throughput and the throughputs of individual components. If this relationship is not obvious or known from the structure of the system, we may be able to determine it using measurements. To this end, we need at least one set of reasonably synchronized measurements of x exp S and x exp k , k = 1, . . . , K. If only one set of synchronized measurements is available, the best one can do is to assume that the observed ratios x exp k /x exp S carry over to other workload levels, i.e., remain constant as the overall system throughput varies. With multiple measurement points, one can check if this is indeed the case or possibly try to infer a more involved relationship between throughputs. Note that the throughput ratios discussed above are analogous to the so-called visit ratios in analytical modeling methods such as Mean Value Analysis [START_REF] Reiser | Mean Value Analysis fo Queueing Networks -A New Look at an Old Problem[END_REF][START_REF] Reiser | Mean-value analysis of closed multichain queuing networks[END_REF] or BCMP theorem [START_REF] Baskett | Open, closed, and mixed networks of queues with different classes of customers[END_REF]. With few exceptions, in general solution methods, these ratios are taken to be constant. Additionally, the general analytical solutions require specific restrictions on the types of service discipline and service time distributions in order to be applicable. On the other hand, our approach requires no specific assumptions on service disciplines and distributions or arrivals of requests (even if we may assume that the throughput ratios remain constant).

ILLUSTRATIVE CASES 4.1 Successful case

In this first case we focus on the mean response time, RS, for a system with a centralized architecture and a total of K = 3 components, one of which, is referred to as the central server(s) and the remaining K-1 components are referred as the peripheral servers. Our goal is to study how well RS can be determined from correctly calibrated performance models of the components.

Centralized architectures are common in telecommunication and computer network. In our example, we assume that the incoming tasks, representing the system workload, require first a burst of service from the central server(s). Upon completion of a service burst, a task may request another service burst at the central server(s) or it may need service from one of the peripheral servers. Upon completion of service at a peripheral server, a task may require another round of processing at the central server or it may leave the system.

For the sake of convenience and reproducibility, the "measured" values of the overall system performance, {x exp S , r exp S }i, i = 1, . . . , I as well as those of its components, were obtained using a discrete-event simulation. The system simulated is the machine repairman network shown in Figure 2. The task arrivals are represented through a Poisson process of rate λ. The central server(s) and the peripherals are each represented by a single queue, labeled Comp-1, Comp-2 and Comp-3, respectively. Table 1 gives the details of the simulated system parameters. Thus, in our system: (i) 30% of tasks require another burst of service at the central server(s) after completing a service burst (p11 = 0.3), (ii) two requests can be processed simultaneously at the central servers (C1 = 2), (iii) the service time of Comp-2 is considerably faster than at Comp-3 (mst3 = 5.mst2), (iv) the variability of service times is much larger for Comp-2 than for Comp-3 (although the mean time is less) (cvs2 = 4.cvs3), (v) 70% of requests return to the central servers queue upon completion of service at a peripheral server (p21 = p31 = 0.7).

As discussed above, we assume that accurate and calibrated models have been developed for each of the 3 components (Comp-1, Comp-2 and Comp-3) of the system. In ) that returns a predicted level of mean response time for any given value of the mean throughput at the given component. Note that we used the high-level modeling approach [START_REF] Begin | High-level approach to modeling of observed system behavior[END_REF] to find calibrated models for the components. In our case, these happen to be based on queueing theory but any other approach would work provided that the resulting models are accurate. Figure 3 illustrates the accuracy of the component models by showing the "measured" and the model-predicted performance for each system component. We observe that our component models match well the "measured" performance values throughout the range of workload values under consideration.

Having in hand a calibrated model for each of the system components, we can now use Formula (1) to determine the mean response time for the whole system as a function of the mean system throughput. All we need is to know are the throughput ratio of each component, namely x exp k /x exp S , k = 1, . . . , K. These quantities may be smaller or larger than 1 as they represent the relative rate of request arrivals at component k as compared to that at the system level.

In our example, it is easy to compute these ratios from the system topology (see Figure 2). The corresponding values are , and thereby applying Formula (1). We performed this step for many levels of workload, including low and high levels. Figure 4 shows the resulting overall system performance values obtained using this approach. Clearly, and perhaps not surprisingly, we observe that the performance of the composed model {x mod S , r mod S } match very well those measured in the simulation {x exp S , r exp S }, validating the proposed approach for this example.

1 (1-p 11 )(1-p 21 ) = 4.762, p 12 (1-p 11 )(1-p 21 ) = 2.

Cases of failure

As illustrated by examples in this section, considerably inaccurate performance predictions can be expected when the applicability conditions are not met. We now consider a system with 3 components in which, unlike the previous example, the routing probabilities depend on the current state of components. Such state-dependencies may occur in systems with load-balancing policies. Figure 5 illustrates the topology of our example. In this system, the incoming requests, which arrive according to a Poisson process with rate λ, go through two components. They start with Comp-1 and, if the current number of requests waiting or being served in Comp-2 is larger than 10, they are routed to Comp-3. Otherwise, they are equally likely to be dispatched to Comp-2 and Comp-3. Table 2 summarizes the system parameters used in our simulation. Note that the buffers at each component are assumed to be large enough to avoid overflows.

Assuming we have calibrated models to capture the performance of each component, we apply the proposed approach to estimate the mean response time of the whole system as a function of the mean throughput following Formula [START_REF] Allen | Probability, Statistics, and Queueing Theory: With Computer Science Applications[END_REF]. Here, the predicted values do not match well those actually observed ("measured") in the simulation. Figure 6 illustrates this discrepancy.

The reason for the discrepancy shown in Figure 6 is clear: unlike in the previous example, the throughput ratios for components Comp-2 and Comp-3 are not constant. Indeed, as the workload increases, the number of requests waiting or being served in Comp-2 increases, so that requests leaving Comp-1 become more likely to be routed to Comp-3 (up to half of them). In the proposed approach, however, the throughput ratio for each queue was derived at a lower level of workload, and it was applied for other levels of workload considered.

State-dependencies causing failure of the proposed approach can appear in seemingly different examples. Consider a system in which the arrivals and departures of requests may occur at several places in the system. Such behavior may occur in systems exhibiting internal losses of requests (e.g. due to buffer overflow, transmission errors, dynamic routing). Figure 7 shows a system where incoming requests may be routed to Comp-1 or directly to Comp-2 depending on the current number of requests waiting in Comp-1. If the number of queued requests is less than 7, then incom- Table 3: Parameters used for Figure 7. ing requests go to Comp-1. Otherwise, they skip Comp-1 and go directly to Comp-2. Similarly, if the current number of requests at Comp-3 is less than 7, requests completed at Comp-2 are routed to Comp-3. Otherwise, upon completion at Comp-2, they skip Comp-3 and leave the system. Table 3 gives the details of the system parameters used in our simulation. As in our preceding example, request arrivals form a Poisson process and the buffer sizes at each component are assumed to be large enough to avoid overflows.

Again, with accurately calibrated performance models for each component, we apply Formula (1) to predict the mean response time of the whole system for different levels of mean system throughput. Here too, as illustrated in Figure 8, the proposed approach is doomed to failure since the throughput ratios of Comp-1 and Comp-3 are not constant.

As discussed above, the proposed approach would work if the rate of arrivals at Comp-2 and the rate of departures from Comp-2 were known in advance or if they were simply proportional to the overall system workload (as would be the case, for example, if requests departures represented transmission errors in a communication network).

In addition to cases in which the throughput ratios vary with workload levels and their variation is not known in advance, the proposed approach is not applicable for systems in which requests may simultaneously "occupy" two or more resources. For instance, in order to get fully processed by a "primary" component, the requests, while holding the component resource, need to receive service from a "secondary" component. The latter may be shared with other competing Figure 9 illustrates a simple example of a system with simultaneous resource possession. The service time in Comp-1 is represented as a two-stage process where the second stage represents the resource holding time while the request potentially waits for and accesses the shared resource at Comp-2.

Here, any calibrated model of component Comp-1 is in fact a good candidate to predict the mean response time of the whole system since both coincide. Comp-1 and Comp-2 are too strongly coupled (Comp-2 can be seen as being embedded within Comp-1) and cannot be combined as described in Section 3. Similarly, systems with fork and join mechanisms would cause problems.

DISCOVERY OF UNKNOWN SYSTEM COMPONENTS

Our next system of interest is similar to that discussed in Section 4.1 but it includes an additional component, viz. Comp-4. We assume that available measurements points pertain to the overall system performance as well as to components Comp-1, Comp-2 and Comp-3 with the exception of Comp-4. This latter may have been considered unimportant for the overall system performance or simply overlooked by or unknown to the performance analyst. Comp-4 may represent for example access to internal tables or buffers deemed so fast that it is unlikely to be a factor in the overall system performance. Figure 10 illustrates the corresponding system with a gray box around Comp-4. We re-use the same system parameters for components 1 through 3 as in Table 1 and indicate the parameters for Comp-4 in Table 4. The parameters for Comp-4 were chosen so that it can become a bottleneck because of the frequency with which requests visit it while each visit is very short. Having developed a calibrated performance model for each of the components Comp-1, Comp-2 and Comp-3, we applied the proposed method following Formula (1) to derive the performance of the whole system. Figure 11a displays the corresponding results. Clearly, the proposed approach is missing something. Now, assuming this missing something is an additional component that was not measured (and perhaps even not instrumented) and therefore not modeled, we consider the difference in the performance metric between the system measurement points and the performance curve given by Formula (1). Given this residual pattern of performance, we apply a black-box modeling approach [START_REF] Begin | High-level approach to modeling of observed system behavior[END_REF] to find a model that reproduces adequately this behavior. It turns out that a simple M/M/1 queue can fit the data (see Figure 11b).

If the pattern was more chaotic and could not be matched by a reasonable model, it might imply that the residual performance difference is just measurement "noise", or that something else is amiss and that the system does not comply with the set of assumptions required for the proposed approach to work. A possible approach to try to determine whether the residual performance difference is due to "measurement noise" would be to apply simple statistical tests [START_REF] Allen | Probability, Statistics, and Queueing Theory: With Computer Science Applications[END_REF]. Now, having in hand a calibrated model for each of the four system components, we can re-apply the proposed approach to forecast the system performance. The corresponding results are shown in Figure 11c and clearly, including a new component was the right choice in our case.

CONCLUSIONS

In this paper we consider the problem of combining calibrated performance models of individual system components into an accurate system-level performance model. We concentrate on open workload systems and we show that under certain conditions the straightforward application of Little's law allows one to effect this integration. We give examples to illustrate the successful application of the proposed approach, as well as examples that show the extent of inaccuracies if the applicability conditions are not met.

Additionally, we show that by analyzing the discrepancies between the model predictions and the measurements it may be possible to determine if an important system component has not been correctly represented. This can be of help in the design of calibrated system performance models.

As future work, the authors plan to further investigate the important issue of distinguishing "measurement noise" from errors due to missing components. Another area of investigation pertains to the extensions of the proposed framework to closed systems.

Figure 1 :

 1 Figure 1: A system with K = 5 components. components. Our K component models can be viewed as a set of K functions f mod k (x mod k

  fig:system-centralized

Figure 2 :

 2 Figure 2: A centralized system architecture.

857 and p 13 ( 1 -

 131 p 11 )(1-p 31 ) = 0.4762 for component Comp-1, Comp-2 and Comp-3, respectively. As mentioned in Section 3, in other cases, these values can be discovered thanks to synchronized measurements of throughput. Next, in order to obtain r mod S as a function of x mod S , we simply "convert" any given value of x mod S into values of x mod k , k = 1, . . . , K by multiplying it by the respective throughput ratio, and then we call the component models to compute the values of r mod k associated to x mod S

Figure 3 :

 3 Figure 3: Performance measurements and modeling for each of the 3 components of the centralized system.

Figure 4 :

 4 Figure 4: Predictions of system performance against measurements for the centralized system.

Figure 5 :

 5 Figure 5: System with state-dependent routing.

Figure 6 :

 6 Figure6: Predictions of system performance against measurements for the system with state-dependent routing probabilities.

Figure 7 :

 7 Figure 7: System with internal losses and arrivals.

1 1 2 2 2 0 or 1 p 20 3 3

 1122212033 Mean service time 2 cvs Coefficient of variation for service time 1 p 01 Probability for new requests to enter at CompMean service time 1 cvs Coefficient of variation for service time 1 p 02 Probability for new requests to enter at Comp-Probability of leaving the system upon completion of Mean service time 2 cvs Coefficient of variation for service time 1

Figure 8 :

 8 Figure 8: Predictions of system performance against measurements for the system with internal losses and arrivals.

Figure 9 :

 9 Figure 9: System with simultaneous resource possession.

Figure 10 :

 10 Figure 10: System with an "unknown" component.

Table 4 :

 4 Parameters used for Figure10.

cvs 4

 4 Coefficient of variation for service time 0 p 44 Probability of returning to Comp-4 upon request completion 0.96

Figure 11 :

 11 Predictions of system performance against measurements for the centralized system with an unknown component.

Table 1 :

 1 Parameters used for Figure 2.

	Comp-1	C 1	Number of servers	2
		mst 1 Mean service time	1
		cvs 1 Coefficient of variation for service time 3
		p 11 Probability of returning to Comp-1	0.3
			upon request completion
		p 12 Probability of going to Comp-2 upon	0.6
			request completion
		p 13 Probability of going to Comp-3 upon	0.1
			request completion
	Comp-2	C 2	Number of servers	1
		mst 2 Mean service time	2
		cvs 2 Coefficient of variation for service time 2
		p 20 Probability of leaving the system upon	0.3
			request completion
		p 21 Probability of going to Comp-1 upon	0.7
			request completion
	Comp-3	C 3	Number of servers	1
		mst 3 Mean service time	10
		cvs 3 Coefficient of variation for service time 0.5
		p 30 Probability of leaving the system upon	0.3
			request completion
		p 31 Probability of going to Comp-1 upon	0.7
			request completion
	other words, the model of the k-th component (Comp-k)
	provides a function r mod k	(x mod k

Table 2 :

 2 Parameters used for Figure5.

	Comp-1	C 1	Number of servers	1
		mst 1 Mean service time	1
		cvs 1 Coefficient of variation for service time 1
		p 12 Probability of going to Comp-2 upon	1 or .5
			request completion
		p 13 Probability of going to Comp-3 upon	0 or .5
			request completion
	Comp-2	C 2	Number of servers	1
		mst 2 Mean service time	2
		cvs 2 Coefficient of variation for service time 1
	Comp-3	C 3	Number of servers	1
		mst 3 Mean service time	2
		cvs 3 Coefficient of variation for service time 1


Emmanuelle Simon
email: emmanuelle.simon@univ-lorrainebrigitte.simonnot@univ-lorraine

Brigitte Simonnot

Amps Menopur

Fertility and medically assisted procreation: forms of exchange and relationships between patients via forums and blogs in South Africa

Fertility and medically assisted procreation: forms of exchange and relationships between patients via forums and blogs in South Africa

Introduction

In this communication, we will focus on South Africa.

(DIAPO 3) For us, online forums and blogs about Assisted Reproductive Techniques are social spaces for African women, and they build some communities to make sense of their situation. In blogs and forums, women submit personal data and exchange information between them. Identities, considerations about selves and relations (how to live with others) are built up through those technical settings.

To understand how women exchange together in online blogs and forums, we have observed and analyzed in detail "the organization, production and processing of specific sequences of interactions" [START_REF] Licoppe | Formes de la présence et circulations de l'expérience, de Jean-Jacques Rousseau au « quantified self[END_REF], and have tried not to follow only actors but also sequences of interactions, crossed between several websites where they are "expressed, evoked, cited." This double process helps to "grasp something in the production of identities" [START_REF] Licoppe | Formes de la présence et circulations de l'expérience, de Jean-Jacques Rousseau au « quantified self[END_REF]. So, we have carefully analyzed some journeys of infertile women, especially one of them during several years. In social sciences, the internet is often studied as a social space through the notion of network, but we have rather chosen to reconstitute some paths and biographies of online women. We have tried to observe how they gradually build a relation with their bodies, the drugs and assisted reproductive techniques. Utterances in forums and blogs are worthy of analysis as they don't include only a posteriori speeches about the course of their lives: individuals can be followed as they evolve and broadcast their thoughts live. We tried to capture the complexity of their routes (e.g. how women handle failures), with their discrepancies and developments, and the steps to make sense of fertility issues through subjective experience.

On the other end, to better understand how such interactions appear from one place to another, we have undertaken to follow these women in various online spaces. Here, we have followed these South-African women between forums and blogs. Women who blog in English about infertility are not so many, and it's worse for French blogs in Africa. We can identify a very strong tie between writing a blog and being registered in Fertilicare 1 forums: on 26 blogs, 19 ones are linked to Fertilicare, with the logo of the association or links to the website. 16 women have been identified in both supports. Most of them registered on Fertilicare forums first and then have created one blog. 12 of them are very active on forums (from 1500 to 3000 posts). None of them is just a reader (at least 200 1 Fertilicare (http://www.fertilicare.org/) is a website with online forum about fertility. The web site has been created in 2007 by 2 South-African women who coped with infertility. One of them has found a donor centre, Nurture. messages posted in forums) when it is a common practice in French or English speaking forums.

In our biographic perspective, we don't aim to present some women's routes as exemplary ones. Women of our corpus are from a minority in a double way: white people in South Africa and people writing online in blogs and forums. However, the underlining idea is that people, even from a minority, always say something about the whole society.

(DIAPO 5) Usually, blogs of women trying to conceive begin just after they start treatments for IVF, and ends when the project is over. Some women have several blogs, each one being dealing with a specific topic. We have followed one woman we will nickname Rose. We have analyzed her blog throughout, with comments and also her comments on Fertilicare. Even if she writes with her real first name on her blog, we prefer to hide her real identity. Rose, like most of bloggers (not to say all of them) doesn't link her blog to her pseudonym in Fertilicare.

In forums, women use pseudonyms as they speak about very personal issues.

Rose created her blog in February 2009, she was trying to conceive from 2001, has been pregnant 3 times but each time it ends in miscarries. In 2008, she had her first IVF, got pregnant but miscarried at 6 weeks. She explains the reasons why she creates a blog by her need to understand and to get support: "I embarked on my spiritual journey looking for answers and found a wonderful place for my intuition and self-awareness to grow". She writes every Saturday in the afternoon, except when there are special events; for example, she writes almost every day in period where she waits for results, and she stops writing for 15 days or one month after failures. Nevertheless, she tries to be positive and doesn't complain too much about her fertility issues.

2 Kind of sources for information about infertility issues (Diapo 6) In forums and blogs, we have found many tracks of information practices about fertility issues. One dominant topic is uncertainty: outcomes of treatments are unpredictable.

To face uncertainty, women seeks actively for information. They use a large diversity of media. Women read books about infertility. Rose is interested in scientific discoveries, some of them could be described as para-scientific. For instance, Rose, when she changes her strategy and think about egg donation, reads books about genomics and human evolution.

From the books, she concludes that even if she conceives with eggs from another woman, the fact that embryo will be in her "tummy" (as she says) can change many things. (DIAPO 8) Women watch specific TV programs on various channels and notify them to others on forums threads. For example, Rose notifies on her blog a program on BBC Knowledge "A child against all odds", and she says that she appreciated it a lot because each episode talks about 2 cases: one which worked and another one which failed. On TV, women watch also American series, medical dramas like Greys anatomy, Private Practice and Brothers & sisters. Even during leisure time, they keep in touch with fertility issues and medical circle with books and TV programs.

Another common practice women refer to in their blogs and forum is googling. They mainly use web search engines to ask "Dr Google" about their symptoms, to understand the pieces of information for diagnosis, to go further after discussions with their fertility specialists or to understand the meaning of numbers or rates in medical records when they receive results of their biological tests. They search to understand how normal are theirs results, and what they mean. But they also search further on the web after watching a TV program or reading a newspaper to verify and to know more about what has been said.

(DIAPO 9) They turn to forums to ask other women about specific questions and to get advices in order to make some choices. During fertility treatments, they are faced with many choices, and they discuss them with their Fertility Specialist but they also seek advices from women with similar experiences. Rose asks: how many days before egg transfer, 3 or 5? Or what kind of IVF to do, ICSI, PICSI? She talks about drugs used for stimulation and the possible side effects. Other women try to help in the forum answers or in comments of the blog by reporting their own experience, their doctor advices, and so on.

In her interactions with others, women also refer to websites they have found during their googling: often, they find information on websites in USA, Canada or the UK. They mention some fertility practitioners' blogs they read. They also refer to scientific magazines like New Scientist (online), for example about a paper announcing a new treatment against infertility which has been developed by a doctor in the USA, the doctor coming from South Africa.

Their information practices cross-reference facts from other women experiences and information from classical sources.

And last, they share and discuss information they have found during doctor-patient appointments: use ICT both to organize their "plans of action" and as self-reflexive tools. Our blogger, Rose writes a lot in Fertilicare forums first and then she writes a blog post where she is more staid or serene. For example, on the 10 th of December 2009, she posts in the Fertilicare forums about a "prescription for hope" her fertility specialist wrote out during her last appointment; on the 16 th of December, she writes a blog entry with the same title but a rather different content that shows ideas have caught on in her head. This blog entry is a testimony of the work done on herself, to rebuild a unified self and to overcome the risk of fragmentation of her identity, a work that she wants to benefit others. So some blog entries are not only written for expressing oneself at the time, but to give an account she thinks will be useful for other women. That the reason why, when the infertility journey is over, women stop blogging (and often open another blog) but some of them leave their old blog open.

Blog and forums are means to get in touch with a community of people who are concerned with the same topics and who can understand what patients feel during fertility treatments.

(DIAPO 11) In the case of South African bloggers, women use forum and blog to express theirs discomfort and to describe how they feel, physically and much more psychologically.

For instance, some threads are about "The most insensitive comments" those women have been faced to. One thread, beginning in August 2009 on Fertilicare forum, had fifty or so answers from women with their own anecdotes, the last one being posted in November 2010.

In Fertilicare, women expect especially emotional support and we can see an emphasis on their subjective experience. They ask others for news about their IVF and worry when a woman doesn't visit online spaces for a while, which could be a sign that she is discouraged. This unconditional support which always invites them to continue is ambivalent because it implicitly expresses the commonly held idea of impossibility "of being childless" [START_REF] Inhorn | Infertility around the Globe: New thinking on childlessness, gender and reproductive technologies[END_REF]. At the same time, individuals are supported by the community to build her selves and identities, and on the other side, they are watched by the community and encouraged to go on the journey and constrained by the norms.

Forums and blogs as technical settings which promote the appropriation of ART

(DIAPO 12) Mixing emotional support and information seeking about Assisted Reproductive Techniques, digital social spaces are important places for women to incorporate the process of medically assisted procreation.

We first mention their information seeking episodes and biomedical sources they use. Rose has a sharp knowledge about infertility, its causes, the treatments and she puts forward each step protocols with a high precision. The questions she asks for demonstrate a high level of knowledge of the processes of ART but, more generally speaking, of human biology. Is it possible for an immature egg at time X to be fertilized? What are the determiners of nesting? And so on. This level of expertise remains very uncommon and can be linked to the social category of those women who blog, which suppose some level of education. This education allows her to ask the necessary questions in her relations with the staff and the doctor of the fertility clinic.

By the time, many of those women have developed a kind of expertise: they experienced a great number of tries to conceive (6 IVF for Rose, up to 9 IVF for another one), each one being different from the previous one, with, sometimes, slightly different protocols, and each detail is important for them. For Rose, her expertise is also built through a complex relation with her fertility specialist where clinical and experimental relations are mixed up: in a classic case of "therapeutic misconception" [START_REF] Appelbaum | The therapeutic misconception: Informed consent in psychiatric research[END_REF].

(DIAPO 13) Thus, the reports of the progress of Rose's IVF look like a medical file where the patient is reduced to a set of equations. For example, she compares the outcomes of her stimulation on Cycle Day 8 of her current IVF with the previous one. On her blog, she begins to update a comparison, step by step, between protocols.

(DIAPO 14)

July: CD2 -3 x Femara tabs CD3 -3 x Femara tabs / 4 amps Menopur CD4 -3 x Femara tabs / 3 amps Menopur CD5 -3 x Femara tabs (DIAPO 15) Later, when she will use an egg donor, as she will learn the number of follicles of the donor after the stimulation, she will calculate the probabilities to go to the transfer (I let you read the slide):

« I read that a good donor should have 15-25 antral follicles. Also, you can calculate how many eggs you will get with a simple calc: EGGS = 0.8*FA (Antral Follicle Count)+2. So if our donor had 15 antral follicles then hopefully we will get 14 eggs!! That would be great, if one considers only about 50% fertilise. I would be completely thrilled to have 7 embies. They also say that approx 30% make it to blast, so if we get 7 embies, then hopefully hopefully, hopefully we will get 2 healthy blasts to transfer, maybe more ». (blog: 18 February 2010). Profiles and signatures are like identity cards, sometimes displaying a diagnostic but mainly a series of steps in an infertile woman's life, with ART at the center.

Rose biography seems reduced to the different IVF succeeding each other, without or with egg donor, some are simple IVF, some ICSI or PICSI. It can be seen like a process of embodiment of assisted reproductive technologies.

But, in our biographical approach, it's important not to focus on a single step of the trajectory.

The ultimate aim of these women is to have a child and to become a mother. Usually, women inscribe their new born in their signature and then, they change the category of forum where they write: they post in the forum which is dedicated to mothers.

At the same time, we would like to nuance the idea of embodiment of ART because we don't want to join in feminist criticism about ART, when they say ART is a new biomedical mean to constrain women bodies:

(DIAPO 18) (Greil, 2002: p. 113) « The experience of infertility is an experience of failure of body and self, and the experience of infertility treatment is an experience of frustration, loss of control, and mortification. But these women do not present themselves as passive victims content to be treated as objects. Rather they appear as active strategists and negotiators who have learned to work the system in such a way as to maximize the control they do have ».

These women adopt biomedical representations of their bodies, and they enroll themselves in a project which leads to monitor and watch their bodies, putting aside the invasive therapies and treatments. But we may suppose, with Greil, that they are ready to do such effort to satisfy their wish of having a child and to gain, finally, the legitimate status of a mother.

Conclusion

(DIAPO 19) After this online fieldwork, we can say that Information and Communication Technologies (ICT) play a role in the way women deal with their infertile status; through their writings, both in blogs and forums, they try to overcome heavy treatments. Moreover, they build social identities. Online, they find places where they are recognized and can rebuild self-esteem. But, the online community is also normative in the way it gives support. And, for a large part of infertile women, the ultimate aim is to recover a legitimate social role: to be a mother.

To clarify the relationship between subject, procreative norms and ART embodiment, they are several other questions that we want to explore through our corpus, for example:

-When a woman decides to make a break (not stop, a break) during infertility treatments, how are such conflicts handled in forum exchanges? It could be also explored with the question of adoption. Does the community of women just give a normative support? Or new norms could arise from such online interactions?

-One South African woman, who was infertile and finally became a mother, created

Fertilicare website and an Egg Donor center. She writes: "when you have been an

infertile woman, you will be one for your whole life". When women conceive with assisted reproductive technologies, does the embodiment process of biomedical technologies still exist after babies' births?

To conclude, Isabelle Gobatto was briging out, in Les pratiques de santé dans un monde globalisé [Heath practices in a globalized world], that « all the women are not exposed in the same way and with the same degree to the process of globalization" "material and immaterial conditions which determine part of their life and their capacity to subjectivize their experience, to modulate it as they wish, vary from one group of women to another." p. 163.

We could adopt this remark for web tools. The ability to juggle with social logics specific of the internet, its settings, and its tools is not shared equally. Is our corpus representative of infertile women in South Africa? To write a blog, someone needs to be educated and fluent with ICT. Now, in South Africa, there are black women in the upper middle class. But we couldn't identify black women who write a blog. Perhaps black women are less ready to display themselves online. We shouldn't think the issue just in term of equipment, stable connection, but rather to keep in mind the social conditions of existence of people who face infertility in our study and their unequal relation towards the practical sense, specific of the internet.

(

  Diapo 2) This research is part of a multidisciplinary research program in anthropology and information and communication sciences about medically assisted procreation in three African countries: Cameroun, South Africa and France. The research is undergone by four laboratories: CEPED, Centre Population et Développement (UMR 196 Université Paris Descartes -INED -IRD); CEMAf, Centre d'études des mondes africains (UMR 7161 -CNRS-Paris1-EPHE); CEAN Centre d'Etudes d'Afrique Noire (UMR 5115 -IEP Bordeaux); CREM Centre de recherche sur les médiations (CREM -EA3472 Metz).

  During the research project, we analyzed African blogs, written in French or in English. Usually women are from upper middle class with various situations of social vulnerability. We have collected 26 blogs from South African people. Only one is written by a man (his wife has also a blog). Women who blog are between 29 and 42 years old, they are from the white community. They have very good positions, they have jobs as manager; training consultant; national account manager; freelance designer and wedding stationer.These women live in Cape Town, near Johannesburg or near Nelspruit in the east.

DIAPO 7

 7 Figure 1--Blog of Rose, Saturday, December 4, 2010

Figure 2 -

 2 Figure 2--Rose, in Fertilicare forum, May 25th 2010

(DIAPO 16 )

 16 The promise to be pregnant takes the form of the results from biological tests (BETA test) as well (just an extract): « And the number is..... 1985!!! So relieved! » (blog & forum : 14th of March 2010) Putting in numbers the path according to the number of stimulations, of produced follicles, of biological results is pushed to the extreme here. But we can find a similar tendency, more generally, in profiles and signatures in forums. And we can say it is the same for a large majority of African women who are active on forums -either French or English speaking. (DIAPO 17) Here is the way Rose's profile is displayed in the forum: TTC: 13 yrs Me: 39 DH: 52 98-01: Tried... 01 & 04: Lap endo x 2, PID 05: 3 Chlo & 3 AI's -BFN 06&07: Preg: Rupt ectopic & 2nd ectopic 08: IVF#1 BFP, MC 6 wk, July: IVF#2 no ET Nov: IVF#3 no ET, poor embryo qual 2010: Mar: IVF#4 -cancld. May: IVF#5 -no ET, embies stopped. Oct: IVF#6 -BFN 2011: Feb: IVF#7 DE -BFP! (Betas: 10d5dt 264, 14dp5dt 1985, 18dp5dt 9756, 22dp5dt 26356) TWINS!!!!: A boy and a girl! Rebecca (1430g) and Finn (1940g) Hospitalised for severe pre-eclampsia, born at 31 weeks 3 days. 4 Weeks in NICU... (It's difficult to read, because of the online infertility lingo)


Stephan Merz

Hernán Vanzetto

Encoding TLA + into Many-Sorted First-Order Logic

This paper presents an encoding of a non-temporal fragment of the TLA + language, which includes untyped set theory, functions, arithmetic expressions, and Hilbert's ε operator, into many-sorted firstorder logic, the input language of state-of-the-art smt solvers. This translation, based on encoding techniques such as boolification, injection of unsorted expressions into sorted languages, term rewriting, and abstraction, is the core component of a back-end prover based on smt solvers for the TLA + Proof System.

Introduction

The specification language TLA + [START_REF] Lamport | Specifying Systems: The TLA + Language and Tools for Hardware and Software Engineers[END_REF] combines variants of Zermelo-Fraenkel set theory with choice (zfc) and of linear-time temporal logic for modeling, respectively, the data manipulated by an algorithm, and its behavior. The TLA + Proof System (tlaps) provides support for mechanized reasoning about TLA + specifications, integrating back-end provers for making automatic reasoners available to users of tlaps. The work reported here is motivated by the development of an smt backend, through which users of tlaps interact with off-the-shelf smt (satisfiability modulo theories) solvers for non-temporal reasoning. More specifically, tlaps is built around a so-called Proof Manager [START_REF] Cousineau | TLA + Proofs[END_REF] that interprets the TLA + proof language, generates corresponding proof obligations, and passes them to external automated verifiers, which are the back-end provers of tlaps.

Previous to this work, three back-end provers with different capabilities were available for non-temporal reasoning: Isabelle/TLA + , a faithful encoding of TLA + set theory in the Isabelle proof assistant, which provides automated proof methods based on first-order reasoning and rewriting; Zenon, a tableau prover for first-order logic with equality that includes extensions for reasoning about sets and functions; and a decision procedure for Presburger arithmetic called Sim-pleArithmetic (now deprecated). The Isabelle and Zenon backends have very limited support for arithmetic reasoning, while SimpleArithmetic handles only pure arithmetic formulas, requiring the user to manually decompose the proofs until the corresponding proof obligations fall within the respective fragments.

Beyond its integration as a semi-automatic backend, Isabelle/TLA + serves as the most trusted back-end prover. Accordingly, it is also intended for certifying proof scripts produced by other back-end provers. When possible, backends are expected to produce a detailed proof that can be checked by Isabelle/TLA + . Currently, only the Zenon backend has an option for exporting proofs that can be certified in this way.

In this paper we describe the foundations of a back-end prover based on smt solvers for non-temporal proof obligations arising in tlaps. 4 When verifying distributed algorithms, proof obligations are usually "shallow", but they still require many details to be checked: interactive proofs can become quite large without powerful automated back-end provers that can cope with a significant fragment of the language. Sets and functions are at the core of modeling data in the TLA + language. Tuples and records, which occur very often in TLA + specifications, are defined as functions. Assertions mixing first-order logic (fol) with sets, functions, and arithmetic expressions arise frequently in safety proofs of TLA + specifications. Accordingly, we do not aim at proofs of deep theorems of mathematical set theory but at good automation for obligations mixing elementary set expressions, functions, records, and (linear) integer arithmetic. Our main focus is on smt solvers, although we have also used the techniques described here with fol provers. The de-facto standard input language for smt solvers is smt-lib [START_REF] Barrett | The Satisfiability Modulo Theories Library (SMT-LIB)[END_REF], which is based on many-sorted fol (ms-fol [START_REF] Manzano | Extensions of First-Order Logic[END_REF]). 5In Section 3 we present the core of the smt backend: a translation from TLA + to ms-fol. Although some of our encoding techniques can be found in similar tools for other set-theoretic languages, the particularities of TLA + make the translation non-trivial:

-Since TLA + is untyped, "silly" expressions such as 3 ∪ true are legal; they denote some (unspecified) value. TLA + does not even distinguish between Boolean and non-Boolean expressions, hence Boolean values can be stored in data structures just like any other value. -Functions, which are defined axiomatically, are total and have a domain. This means that a function applied to an element of its domain has the expected value but for any other argument, the value of the function application is unspecified. Similarly, the behavior of arithmetic operators is specified only for arguments that denote numbers. -TLA + is equipped with a deterministic choice operator (Hilbert's ε operator), which has to be soundly encoded.

The first item is particularly challenging for our objectives: whereas an untyped language is very expressive and flexible for writing specifications, ms-fol reasoners rely on types for good automation. In order to support TLA + expressions in a many-sorted environment, we introduce a "boolification" step for distinguishing between Boolean and non-Boolean expressions, and use a single sort for encoding non-Boolean TLA + expressions. We therefore call this translation the "untyped" encoding of TLA + ; it essentially delegates type inference of sorted expressions such as arithmetic to the solvers.

The paper is structured as follows: Section 2 describes the underlying logic of TLA + , Section 3 is the core of the paper and explains the encoding, Section 4 provides experimental results, Section 5 discusses related work, and Section 6 concludes and gives directions for future work.

A non-temporal fragment of TLA +

In this section we describe a fragment of the language of proof obligations generated by the TLA + Proof System that is relevant for this paper. This language is a variant of fol with equality, extended in particular by syntax for set, function and arithmetic expressions, and a construct for a deterministic choice operator. For a complete presentation of the TLA + language see [START_REF] Lamport | Specifying Systems: The TLA + Language and Tools for Hardware and Software Engineers[END_REF]Sec. 16].

We assume given two non-empty, infinite, and disjoint collections V of variable symbols, and O of operator symbols, 6 each equipped with its arity. The only syntactical category in the language is the expression, but for presentational purposes we distinguish terms, formulas, set objects, etc. An expression e is inductively defined by the following grammar: A term is a variable symbol v in V or an application of an operator symbol w in O to expressions. Formulas are built from false, implication and universal quantification, and from the binary operators = and ∈. From these formulas, we can define the constant true, the unary ¬ and the binary connectives ∧, ∨, ⇔, and the existential quantifier ∃. Also, ∀x ∈ S : e is defined as ∀x : x ∈ S ⇒ e.

In contrast to standard set theory, TLA + has explicit syntax for set objects (empty set, enumeration, power set, generalized union, and two forms of set comprehension derived from the standard axiom schema of replacement), whose semantics are defined by the following axioms:

(extensionality) (∀x : x ∈ S ⇔ x ∈ T ) ⇒ S = T (2.1) (empty set) x ∈ {} ⇔ false (2.2) (enumeration) x ∈ {e 1 , . . . , e n } ⇔ x = e 1 ∨ . . . ∨ x = e n (2.3) (power set) S ∈ subset T ⇔ ∀x ∈ S : x ∈ T (2.4) (union) x ∈ union S ⇔ ∃T ∈ S : x ∈ T (2.5) (comprehension 1 )
x ∈ {y ∈ S :

P (y)} ⇔ x ∈ S ∧ P (x ) (2.6) (comprehension 2 )
x ∈ {e(y) : y ∈ S } ⇔ ∃y ∈ S : x = e(y) (2.7)

We consider that the free variables in these formulas are universally closed, except for P and e in the comprehension axioms that are schematic variables, meaning that they can be instantiated by countably infinite expressions. 7 Another primitive construct of TLA + is Hilbert's choice operator ε, written choose x : P (x ), that denotes an arbitrary but fixed value x such that P (x ) is true, provided that such a value exists. Otherwise the value of choose x : P (x ) is some fixed, but unspecified value. The semantics of choose is expressed by the following axiom schemas. The first one gives an alternative way of defining quantifiers, and the second one expresses that choose is deterministic. ∃x : P (x ) ⇔ P choose x : P (x )

(2.8)

∀x : P (x ) ⇔ Q(x ) ⇒ choose x : P (x ) = choose x : Q(x ) (2.9)
From axiom (2.9) note that if there is no value satisfying some predicate P , then (choose x : P (x )) = (choose x : false). Consequently, the expression choose x : false and all its equivalent forms represent a unique value.

Certain TLA + values are functions. Unlike standard zfc set theory, TLA + functions are not identified with sets of pairs, but TLA + provides primitive syntax associated with functions. The expression f [e] denotes the result of applying function f to e, domain f denotes the domain of f , and [x ∈ S → e] denotes the function g with domain S such that g[x ] = e, for any x ∈ S . For x / ∈ S , the value of g[x ] is unspecified. A TLA + value f is a function if and only if it satisfies the predicate IsAFcn(f

) defined as f = [x ∈ domain f → f [x ]]. The fundamental law governing TLA + functions is f = [x ∈ S → e] ⇔ IsAFcn(f ) ∧ domain f = S ∧ ∀x ∈ S : f [x ] = e (2.

10)

Natural numbers 0, 1, 2, . . . are primitive symbols of TLA + . Standard modules of TLA + define Int to denote the set of integer numbers, the operators + and < are interpreted in the standard way when their arguments are integers, and the interval a .. b is defined as {n ∈ Int : a ≤ n ∧ n ≤ b}.

As a set theoretic language, every TLA + expression-including formulas, functions, and numbers-denotes a set. ). The replacement axiom says that, given an expression S and a binary predicate φ, such that φ is single-valued for any x in S , that is, ∀x ∈ S : ∀y, z : φ(x , y) ∧ φ(x , z ) ⇒ y = z , then there exists a set object R(S , φ), and that x ∈ R(S , φ) ⇔ ∃y ∈ S : φ(x , y).

The translation from TLA + to ms-fol is as follows: given a TLA + proof obligation, we generate a collection of equi-satisfiable smt-lib formulas (restricted to the auflia logic) whose proof can be attempted by smt solvers.

First, all expressions having a truth value are mapped to the sort Bool, and we declare a new sort U (for TLA + universe) for all non-Boolean expressions, including sets, functions, and numbers ( §3.1). Then we proceed in two main steps. A preprocessing phase applies satisfiability-preserving transformations in order to remove expressions not supported by the target language ( §3.2). The result is an intermediate basic TLA + formula, i.e., a TLA + expression that has an obvious counterpart in smt-lib. We define basic TLA + as a subset of TLA + consisting of terms, formulas, equality and set membership relations, primitive arithmetic operators, and if-then-else expressions. The second step is a shallow embedding of basic expressions into ms-fol ( §3.3). Finally, we explain how the encoding of functions ( §3.4) and choose expressions ( §3.5) fit in the translation.

Boolification

Since TLA + has no syntactic distinction between Boolean and non-Boolean expressions, we first need to determine which expressions are used as propositions. tlaps adopts the so-called liberal interpretation of TLA + Boolean expressions [START_REF] Lamport | Specifying Systems: The TLA + Language and Tools for Hardware and Software Engineers[END_REF]Sec. 16.1.3] where any expression with a top-level connective among logical operators, =, and ∈ has a Boolean value. 8 Moreover, the result of any expression with a top-level logical connective agrees with the result of the expression obtained by replacing every argument e of that connective with e = true.

For example, consider the expression ∀x : (¬¬x ) = x , which is not a theorem. Indeed, x need not be Boolean, whereas ¬¬x is necessarily Boolean, hence we may not conclude that the expression is valid. However, ∀x : (¬¬x ) ⇔ x is valid because it is interpreted as ∀x : (¬¬(x = true)) ⇔ (x = true). Observe that the value of x = true is a Boolean for any x , although the value is unspecified if x is non-Boolean.

In order to identify the expressions used as propositions we use a simple algorithm that recursively traverses an expression searching for sub-expressions that should be treated as formulas. Expressions e that are used as Booleans, i.e., that could equivalently be replaced by e = true, are marked as e b , whose definition can be thought of as e b ∆ = e = true. This only applies if e is a term, a function application, or a choose expression. If an expression which is known to be non-Boolean by its syntax, such as a set or a function, is attempted to be boolified, meaning that a formula is expected in its place, the algorithm aborts with a "type" error. In smt-lib we encode x b as boolify(x ), with boolify : U → Bool. The above examples are translated as ∀x U : (¬¬boolify(x )) = x and ∀x Bool : (¬¬x ) ⇔ x , revealing their (in)validity.

Preprocessing

Though a series of transformations to a boolified TLA + proof obligation, we obtain an equi-satisfiable formula that can be straightforwardly passed to the solvers using the direct encoding of basic expressions described below. The main motivation is to get rid of those TLA + expressions that cannot be expressed in first-order logic. Namely, they are {x ∈ S : P }, {e : x ∈ S }, choose x : P , and [x ∈ S → e], where the predicate P and the expression e, both of which may have x as free variable, become second-order variables when quantified.

Normalization by rewriting.

We define a rewriting process that systematically expands definitions of non-basic operators. Instead of letting the solver find instances of the background axioms introduced in Section 2, it applies the "obvious" instances of those axioms during the translation. In most cases, we can eliminate all non-basic operators. For instance, the axioms (2.5) for the union operator and (2.6) for the first form of comprehension yield, respectively, the rewriting rules x ∈ union S -→ ∃T ∈ S : x ∈ T , and x ∈ {y ∈ S : P } -→ x ∈ S ∧ P .

The other cases not covered by rewriting are left to the abstraction mechanism in the next subsection.

All rewriting rules defined in this paper apply equivalence-preserving transformations. To ensure soundness, we derive each rewriting rule from a theorem already proved in Isabelle/TLA + . This is comparable to how rules are obtained in Isabelle's rewrite system, though in a manual way. More specifically, the theorem corresponding to a rule a -→ b is ∀x : a ⇔ b when a and b are Boolean expressions, and ∀x : a = b otherwise, where x denotes all free variables in the rule. Most of these theorems exist already in Isabelle/TLA + 's library.

The standard zf extensionality axiom for sets (2.1) is unwieldy because it introduces an unbounded quantifier, which can be instantiated by any value of sort U. We therefore decided not to include it in the default background theory. Instead, we instantiate the extensionality property for expressions x = y whenever x or y has a top-level operator that constructs a set. In these cases, we say that we expand equality. For each set expression T we derive rewriting rules for equations x = T and T = x . For instance, the rules x = union S -→ ∀z : z ∈ x ⇔ ∃T ∈ S : z ∈ T , and x = {z ∈ S : P } -→ ∀z : z ∈ x ⇔ z ∈ S ∧ P are derived from set extensionality (2.1) and the axioms of union (2.5) and of bounded set comprehension (2.6).

By not including general extensionality, the translation becomes incomplete. Even if we assume that the automated theorem provers are semantically complete, it may happen that the translation of a semantically valid TLA + formula becomes invalid when encoded. In these cases, the user will need to explicitly add the extensionality axiom as a hypothesis to the TLA + proof.

We also need to include a rule for the contraction of set extensionality:

(∀z : z ∈ x ⇔ z ∈ y) -→ x = y,
which we apply with higher priority than the expansion rules. All rules of the form a -→ b, including those introduced below for functions and choose expressions, define a term rewriting system (TLA + , -→), where -→ is a binary relation over well-formed TLA + expressions.

Theorem 1. (TLA + , -→) terminates and is confluent.

Proof (sketch). Termination is simply proved by embedding (TLA + , -→) into another reduction system that is known to terminate, typically (N, >) [START_REF] Baader | Term rewriting and all that[END_REF]. The embedding is through an ad-hoc monotone mapping µ such that µ(a) > µ(b) for every rule a -→ b. We define it in such a way that every rule instance strictly decreases the number of non-basic and complex expressions such as quantifiers. Confluence is proved by Newman's lemma [START_REF] Baader | Term rewriting and all that[END_REF], thus it suffices to prove that all critical pairs are joinable. By enumerating all combinations of rewriting rules, we can find all critical pairs e 1 , e 2 between them. Then we just need to prove that e 1 and e 2 are joinable for each such pair. In particular, the contraction rule is necessary to obtain a strongly normalizing system.

Abstraction.

Applying rewriting rules does not always suffice for obtaining formulas in basic normal form. As a toy example, consider the valid proof obligation ∀x : P ({x }∪{x }) ⇔ P ({x }). The non-basic sub-expressions {x }∪{x } and {x } do not occur in the form of a left-hand side of any rewriting rule, so they must first be transformed into a form suitable for rewriting.

We call the technique described here abstraction of non-basic expressions. After applying rewriting, some non-basic expression ψ may remain in the proof obligation. For all occurrences of ψ with free variables x 1 , . . . , x n , we introduce in their place a fresh term k (x 1 , . . . , x n ), and add the formula k (x 1 , . . . , x n ) = ψ as an assumption in the appropriate context. The new term acts as an abbreviation for the non-basic expression, and the equality acts as its definition, paving the way for a transformation to a basic expression using normalization. Note that we replace non-basic expressions occurring more than once by the same symbol.

In our example the expressions {x } ∪ {x } and {x } are replaced by fresh constant symbols k 1 (x ) and k 2 (x ). Then, the abstracted formula is

∧ ∀x : k 1 (x ) = {x } ∪ {x } ∧ ∀x : k 2 (x ) = {x } ⇒ ∀x : P (k 1 (x )) ⇔ P (k 2 (x )).
which is now in a form where it is possible to apply the instances of extensionality to the equalities in the newly introduced definitions. In order to preserve satisfiability of the proof obligation, we have to add as hypotheses instances of extensionality contraction for every pair of definitions where extensionality expansion was applied. The final equi-satisfiable formula in basic normal form is

∧ ∀x , z : z ∈ k 1 (x ) ⇔ z = x ∨ z = x ∧ ∀x , z : z ∈ k 2 (x ) ⇔ z = x ∧ ∀x , y : (∀z : z ∈ k 1 (x ) ⇔ z ∈ k 2 (y)) ⇒ k 1 (x ) = k 2 (y) ⇒ ∀x : P (k 1 (x )) ⇔ P (k 2 (x )).

Eliminating definitions.

To improve the encoding, we introduce a procedure that eliminates definitions, having the opposite effect of the abstraction method where definitions are introduced and afterwards expanded to basic expressions. This process collects all definitions of the form x = ψ, and then simply applies the rewriting rules x -→ ψ to substitute every occurrence of the term x by the non-basic expression ψ in the rest of the context. The definitions we want to eliminate typically occur in the original proof obligation, that is, they do not result from the abstraction step.

This transformation produces expressions that can eventually be normalized to their basic form. To avoid rewriting loops and ensure termination, it can only be applied if x does not occur in ψ. For instance, the two equations x = y and y = x + 1 will be transformed into y = y + 1, which cannot further be rewritten. After applying the substitution, we can safely discard from the resulting formula the definition x = ψ, when x is a variable. However, we must keep the definition if x is a complex expression. Suppose we discard an assumption domain f = S , where the conclusion is f ∈ [S → T ]. Only after applying the rewriting rules, the conclusion will be expanded to an expression containing domain f , but the discarded fact required to simplify it to S will be missing.

3.2.4

Preprocessing algorithm. Now we can put together boolification and the encoding techniques described above in a single algorithm called Preprocess.

Preprocess(φ)

∆ = φ Boolify Fix Reduce Reduce(φ) ∆ = φ Fix (Eliminate • Rewrite) Fix (Abstract • Rewrite)
Here, Fix A means that step A is executed until reaching a fixed point, the combinator , used to chain actions on a formula φ, is defined as

φ f ∆ = f (φ), and function composition • is defined as f • g ∆ = λφ. g(f (φ)).
Given a TLA + formula φ, the algorithm boolifies it and then applies repeatedly the step called Reduce to obtain its basic normal form. Only then the resulting formula is ready to be translated to the target language using the embedding of Section 3.3. In turn, Reduce first eliminates the definitions in the given formula (Sect. 3.2.3), applies the rewriting rules (Sect. 3.2.1) repeatedly, and then applies abstraction (Sect. 3.2.2) followed by rewriting repeatedly.

The Preprocess algorithm is sound, because it is composed of sound sub-steps, and terminates, meaning that it will always compute a basic normal formula.

Theorem 2. The Preprocess algorithm terminates.

Proof (idea). Observe that the elimination step is in some sense opposite to the abstraction step: the first one eliminates every definition x = ψ by using it as the rewriting rule x -→ ψ, while the latter introduces a new symbol x in the place of an expression ψ and asserts x = ψ, where ψ is non-basic in both cases. That is why we apply elimination before abstraction, and why each of those is followed by rewriting. We have to be careful that Abstract and Eliminate do not repeatedly act on the same expression. Eliminate does not produce nonbasic expressions, but Abstract generates definitions that can be processed by Eliminate, reducing them again to the original non-basic expression. That is the reason for Rewrite to be applied after every application of Abstract: the new definitions are rewritten, usually by an extensionality expansion rule. In short, termination depends on the existence of extensionality rewriting rules for each kind of non-basic expression that Abstract may catch. Then, for any TLA + expression there exists an equi-satisfiable basic expression in normal form that the algorithm will compute.

Direct embedding

The preprocessing phase outputs a boolified basic TLA + expression that we will encode essentially using fol and uninterpreted functions, without substantially changing its structure. In short, our encoding maps the given basic expression to corresponding formulas in the target language in an (almost) verbatim way.

For first-order TLA + expressions it suffices to apply a shallow embedding into first-order ms-fol formulas. Non-logical TLA + operators are declared as function or predicate symbols with U-sorted arguments. For instance, the primitive relation ∈ is encoded in smt-lib as the function in : U × U → Bool. This is the only set theoretic operator that can appear in a basic formula. Expressions like if c then t else u can be conveniently mapped verbatim using smt-lib's conditional operator to ite(c, t, u), where c is of sort Bool (or boolified), and t and u have the same sort.

In order to reason about the theory of arithmetic, an automated prover requires type information, either generated internally, or provided explicitly in the input language. The operators and formulas that we have presented so far are expressed in FOL over uninterpreted function symbols over the sorts U and Bool. Because we want to benefit from the prover's native capabilities for arithmetic reasoning, we declare an injective function i2u : Int → U that embeds built-in integers into the sort U. 9 Integer literals k are simply encoded as i2u(k ). For example, the formula 3 ∈ Int is translated as in(i2u(3), tla Int), for which we have to declare tla Int : U and add to the translation the axiom for Int ∀x U : in(x , tla Int) ⇔ ∃n Int : x = i2u(n).

Observe that this axiom introduces two quantifiers to the translation. We can avoid the universal quantifier by encoding expressions of the form x ∈ Int directly into ∃n Int : x = i2u(n), but the existential quantifier remains. Arithmetic operators over TLA + values are defined homomorphically over the image of i2u by axioms such as

∀m Int , n Int : plus(i2u(m), i2u(n)) = i2u(m + n),
where + denotes the built-in addition over integers. For other arithmetic operators we define analogous axioms.

As a result, type inference in all these cases is, in some sense, delegated to the back-end prover. The link between built-in operations and their TLA + counterparts is effectively defined only for values in the range of the function i2u.

TLA + strings are encoded using the same technique: for every string literal that occurs in a proof obligation, we declare it as a constant of a newly declared sort Str, and assert that these constants are different from each other. Then, we use an injective function str2u : Str → U to lift string expressions. 10If we call BasicEncode(φ) to the embedding of a basic TLA + formula φ into ms-fol, we can define the whole process of encoding TLA + into ms-fol as:

Tla2MsFol(φ) ∆ = φ
Preprocess BasicEncode

Encoding functions

A TLA + function [x ∈ S → e(x )] is akin to a "bounded" λ-abstraction: the function application [x ∈ S → e(x )][y] reduces to the expected value e(y) if the argument y is an element of S , as stated by the axiom (2.10). As a consequence, e.g., the formula

f = [x ∈ {1, 2, 3} → x * x ] ⇒ f [0] < f [0] + 1, (3.1)
although syntactically well-formed, should not be provable. Indeed, since 0 is not in the domain of f , we cannot even deduce that f [0] is an integer. We represent the application of an expression f to another expression x by two distinct first-order terms depending on whether the domain condition x ∈ domain f holds or not: we introduce binary operators α and ω defined as

x ∈ domain f ⇒ α(f , x ) = f [x ] and x / ∈ domain f ⇒ ω(f , x ) = f [x ].
From these conditional definitions, we can derive the theorem

f [x ] = if x ∈ domain f then α(f , x ) else ω(f , x ) (3.2)
that gives a new defining equation for function application. In this way, functions are just expressions that are conditionally related to their argument by α and ω.

Using theorem (3.2), the expression f [0] in the above example (3.1) is encoded as if 0 ∈ domain f then α(f , 0) else ω(f , 0). The solver would have to use the hypothesis to deduce that domain f = {1, 2, 3}, reducing the condition 0 ∈ domain f to false. The conclusion can then be simplified to the formula ω(f , 0) < ω(f , 0) + 1, which cannot be proved, as expected. Another example is f [x ] = f [y] in a context where x = y holds: the formula is valid irrespective of whether the domain conditions hold or not.

Whenever possible, we try to avoid the encoding of function application as in the definition (3.2). From (2.10) and (3.2), we deduce the rewriting rule

[x ∈ S → e][a] -→ if a ∈ S then e[x ← a] else ω([x ∈ S → e], a)
where e[x ← a] denotes e with a substituted for x . This rule replaces two non-basic operators (function application and the function expression) in the left-hand side by only one non-basic operator in the right-hand side (the first argument of ω), which is required for termination of (TLA + , -→) (Theorem 1).

In sorted languages like ms-fol, functions have no notion of function domain other than the types of their arguments. Because explicit functions [x ∈ S → e] cannot be mapped directly to first-order expressions, we treat them as any other non-basic expression. The following rewriting rule derived from axiom (2.10) replaces the function construct by a formula containing only basic operators:

f = [x ∈ S → e] -→ IsAFcn(f ) ∧ domain f = S ∧ ∀x ∈ S : α(f , x ) = e
Observe that we have simplified f [x ] to α(f , x ), because x ∈ domain f .

In order to prove that two functions are equal, we need to add a background axiom that expresses the extensionality property for functions:

∀f , g : ∧ IsAFcn(f ) ∧ IsAFcn(g) ∧ domain f = domain g ∧ ∀x ∈ domain g : α(f , x ) = α(g, x ) ⇒ f = g
Again, note that f [x ] and g[x ] were simplified using α. Unlike set extensionality, this formula is guarded by IsAFcn, avoiding the instantiation by expressions that are not considered functions. To prove that domain f = domain g, we still need to add to the translation the set extensionality axiom, which we abstain from.

Instead, reasoning about the equality of domains can be solved by adding to the translation an instance of set extensionality for domain expressions only:

∀f , g : ∧ IsAFcn(f ) ∧ IsAFcn(g) ∧ ∀x : x ∈ domain f ⇔ x ∈ domain g ⇒ domain f = domain g
TLA + defines n-tuples as functions with domain 1 .. n and records as functions whose domain is a fixed finite set of strings. By treating them as non-basic expressions, we just need to add suitable rewriting rules to (TLA + , -→), in particular those for extensionality expansion. For instance, a tuple e 1 , e 2 , . . . , e n is defined as the function

[i ∈ 1 .. n → if i = 1 then e 1 else (if i = 2 then e 2 else ( • • • else e n ))],
so that e 1 , . . . , e n [i ] = e i when i ∈ 1 .. n. The following rule is derived from these definitions and from the axioms of extensionality (2.1) and functions (2.10):

t = e 1 , . . . , e n -→ ∧ IsAFcn(t) ∧ domain t = 1 .. n ∧ ei :U α(t, i ) = e i ∧ ei :Bool α(t, i ) b ⇔ e i
In order to preserve the satisfiability of expressions considered as terms from those considered as formulas, we treat differently the tuple elements e i that are Booleans (noted e i : Bool) from those that are not (noted e i : U).

Encoding choose

The choose operator is notoriously difficult for automatic provers to reason about. Nevertheless, we can exploit choose expressions by using the axioms that define them. By introducing a definition for choose x : P (x ), we obtain the theorem y = choose x : P (x ) ⇒ (∃x : P (x )) ⇔ P (y) ,

where y is some fresh symbol. This theorem can be conveniently used as a rewriting rule after abstraction of choose expressions, and for choose expressions that occur negatively, in particular, as hypotheses of proof obligations.

For determinism of choice (axiom (2.9)), suppose an arbitrary pair of choose expressions φ 1 ∆ = choose x : P (x ) and φ 2 ∆ = choose x : Q(x ) where the free variables of φ 1 are x 1 , . . . , x n (noted x) and those of φ 2 are y 1 , . . . , y m (noted y). We need to check whether formulas P and Q are equivalent for every pair of expressions φ 1 and φ 2 occurring in a proof obligation. By abstraction of φ 1 and φ 2 , we obtain the axiomatic definitions ∀x : f 1 (x) = choose x : P (x ) and ∀y : f 2 (y) = choose x : Q(x ), where f 1 and f 2 are fresh operator symbols of suitable arity. Then, we just need to state the extensionality property for the pair f 1 and f 2 as the axiom ∀x, y : ∀x :

P (x ) ⇔ Q(x ) ⇒ f 1 (x) = f 2 (y).

Evaluation

In order to validate our approach we reproved several test cases that had been proved interactively using the previously available tlaps backend provers Zenon, Isabelle/TLA + and the decision procedure for Presburger arithmetic. We will refer to the combination of those three backends as ZIP for short.

For each benchmark, we compare two dimensions of an interactive proof: size and time. We define the size of an interactive proof as the number of non-trivial proof obligations generated by the Proof Manager, which is proportional to the number of interactive steps and therefore represents the user effort for making tlaps check the proof. The time is the number of seconds required by the Proof Manager to verify those proofs on a 2.2GHz Intel Core i7 with 8GB of memory.

Table 1 presents the results for four case studies: type correctness and mutual exclusion of the Peterson and Bakery algorithms, type correctness (T) and refinement proofs (I, A) of the Memoir security architecture [START_REF] Douceur | Memoir-Formal Specs and Correctness Proofs[END_REF], and proofs of theorems about finite sets and cardinalities. We compare how proofs of different sizes are handled by the backends. Each line corresponds to an interactive proof of a given size. Columns correspond to the running times for a given smt solver, where each prover is executed on all generated proof obligations. For our tests we have used off-the-shelf smt solvers CVC4 v1.3 and Z3 v4.3.2.

In all cases, the use of the new smt backend leads to significant reductions in proof sizes and running times compared to the original interactive proofs. In particular, the "shallow" proofs of the first three case studies required only minimal interaction. For instance, in the Peterson case, smt solvers can cope with a proof that generates 3 obligations, while the ZIP backends time out in at least one of them. Instead, ZIP requires a more fine-grained proof of size 10. In the Finite Sets benchmarks, some proof obligations generated from big structural high-level formulas can be proved only by Zenon. Beyond these benchmark problems, the smt backend has become the default backend of tlaps.

In previous publications [START_REF] Merz | Automatic Verification of TLA + Proof Obligations with SMT Solvers[END_REF][START_REF] Merz | Harnessing SMT Solvers for TLA + Proofs[END_REF] we presented a primitive encoding of TLA + into smt-lib where boolification, normalization and abstraction were not made explicit in the translation, and choose expressions were not fully supported. This paper supersedes them. Some of our encoding techniques (Section 3) were already presented before (injection of unsorted expressions [START_REF] Merz | Harnessing SMT Solvers for TLA + Proofs[END_REF]) or are simply folklore (e.g., abstraction), but to our knowledge they have not been combined and studied in this way. Moreover, the idiosyncrasies of TLA + render their applicability non-trivial. For instance, axiomatized TLA + functions with domains, including tuples and records, are deeply rooted in the language.

The B and Z languages are also based on ZF set theory, although in a somewhat weaker version, because terms and functions have (monomorphic) types in the style of ms-fol, thus greatly simplifying the translations to smt languages. Another difference is that functions are defined as binary relations, as is typical in set theory. There are two smt plugins for the Rodin tool set for Event-B. The SMT solvers plugin [START_REF] Déharbe | SMT solvers for Rodin[END_REF] directly encodes simple sets (i.e., excluding set of sets) as polymorphic λ-expressions, which are non-standard and are only handled by the parser of the veriT smt solver. The ppTrans plugin [START_REF] Konrad | Translation from set-theory to predicate calculus[END_REF] generates different smt sorts for each combination of simple sets, power sets and cartesian products found in the proof obligation. Therefore, there is one membership operator for every declared set sort, with the advantage that it further partitions the proof search space, although this requires that the type of every term be known beforehand. (In TLA + , this can only be achieved through type synthesis; see [START_REF] Merz | Refinement Types for TLA +[END_REF].) Additionally, when ppTrans detects the absence of set of sets, the translation is further simplified by encoding sets by their characteristic predicates.

Similarly, Atelier-B discharges proof obligations to different smt solvers based on Why3 [START_REF] Mentré | Discharging Proof Obligations from Atelier B Using Multiple Automated Provers[END_REF], with sets encoded using polymorphic types. ProB includes a translation between TLA + and B [START_REF] Hansen | Translating TLA + to B for Validation with ProB[END_REF], allowing TLA + users to use ProB tools. It relies on Kodkod, the Alloy Analyzer's backend, to do constraint solving over the firstorder fragment of the language, and on the ProB kernel for the rest [START_REF] Plagge | Validating B,Z and TLA + using ProB and Kodkod[END_REF].

More recently, Delahaye et al. [START_REF] Delahaye | Zenon Modulo: When Achilles Outruns the Tortoise Using Deduction Modulo[END_REF] proposed a different approach to reason about set theory, instead of a direct encoding into fol. The theory of deduction modulo is an extension of predicate calculus that includes rewriting of terms and propositions. It is well suited for proof search in axiomatic theories such as Peano arithmetic or Zermelo set thery, as it turns axioms into rewrite rules. mptp [START_REF] Urban | Translating Mizar for first-order theorem provers[END_REF] translates Mizar to the unsorted first-order format tptp/fof [START_REF] Sutcliffe | The TPTP Problem Library and Associated Infrastructure[END_REF]. The Mizar language, targeted at formalized mathematics, provides second-order predicate variables and abstract terms derived from replacement and comprehension, such as the set {n -m where m, n is Integer : n < m}. During preprocessing, mptp replaces them by fresh symbols, with their definitions at the top level. Similar to our abstraction technique, it resembles Skolemization.

We have presented a sound and effective way of discharging TLA + proof obligations using automated theorem provers based on many-sorted first-order logic. This encoding forms the core of a back-end prover that integrates external smt solvers as oracles to the TLA + Proof System (tlaps). The main component of the backend is a generic translation framework that makes available to tlaps any smt solver that supports the de facto standard format smt-lib/auflia. Within the same framework, we have also integrated automated theorem provers based on unsorted fol [START_REF] Sutcliffe | The TPTP Problem Library and Associated Infrastructure[END_REF], such as those based on the superposition calculus.

Our translation enables the backend to successfully handle a useful fragment of the TLA + language. The untyped universe of TLA + is represented as a universal sort in ms-fol. Purely set-theoretic expressions are mapped to formulas over uninterpreted symbols, together with relevant background axioms. The built-in integer sort and arithmetic operators are homomorphically embedded into the universal sort, and type inference is in essence delegated to the solver. Functions, tuples, records, and the choose operator (Hilbert's choice) are encoded using a preprocessing mechanism that combines term rewriting with abstraction. The soundness of the encoding is immediate: all rewriting rules and axioms about sets, functions, records, tuples, etc. are theorems in the background theory of TLA + that exist in the Isabelle encoding.

Encouraging results show that smt solvers significantly reduce the effort of interactive reasoning for verifying "shallow" TLA + proof obligations, as well as some more involved formulas including linear arithmetic expressions. Both the time required to find automatic proofs and, more importantly, the size of the interactive proof, which reflects the number of user interactions, can be remarkably reduced with the new back-end prover.

The translation presented here forms the basis for further optimizations. In [START_REF] Merz | Refinement Types for TLA +[END_REF] we have explored the use of (incomplete) type synthesis for TLA + expressions, based on a type system with dependent and refinement types. Extensions for reasoning about real arithmetic and finite sequences would be useful. What is more important, we rely on the soundness of external provers, temporarily including them as part of tlaps's trusted base. In future work we intend to reconstruct within Isabelle/TLA + (along the lines presented in [START_REF] Blanchette | Extending Sledgehammer with SMT solvers[END_REF]) the proof objects that many smt solvers can produce. Such a reconstruction would have to take into account not only the proofs generated by the solvers, but also all the steps performed during the translation, including rewriting and abstraction.

  e ::= v | w (e, . . . , e) (terms) | false | e ⇒ e | ∀v : e | e = e | e ∈ e (formulas) | {} | {e, . . . , e} | subset e | union e | {v ∈ e : e} | {e : v ∈ e} (sets) | choose x : e (choice) | e[e] | domain e | [v ∈ e → e] | [e → e] (functions) | 0 | 1 | 2 | . . . | Int | -e | e + e | e < e | e .. e (arithmetic) | if e then e else e (conditional)

7

  Both axioms (2.6) and (2.7) for set comprehension objects are instances of the standard axiom schema of replacement: taking the two single-valued predicates φ1(x , y) ∆ = x = y ∧ P (y) and φ2(x , y) ∆ = x = e(y), we can define {y ∈ S : P (y)} ∆ = R(S , φ1) and {e(y) : y ∈ S } ∆ = R(S , φ2

Table 1 .

 1 Evaluation benchmarks results. An entry with the symbol "-" means that the solver has reached the timeout without finding the proof for at least one of the proof obligations. The backends were executed with a timeout of 300 seconds.

	size ZIP CVC4	Z3
	Peterson Peterson Bakery Bakery Memoir-T Memoir-T Memoir-T 424 7.31 3 -0.41 0.34 10 5.69 0.78 0.80 19 -36.86 15.20 223 52.74 1 --1.99 12 -3.11 3.21 Memoir-I 8 -3.84 9.35 Memoir-I 61 8.20 Memoir-A 27 -11.31 11.46	Finite Sets CardZero CardPlusOne CardOne CardOneConv FiniteSubset PigeonHole CardMinusOne 11 5.44 ZIP size time size Zenon+SMT time 11 5.42 5 0.48 39 5.35 3 0.49 6 5.36 1 0.35 9 0.63 2 0.35 62 7.16 21 5.94 42 7.07 20 7.01 5 0.75
	Memoir-A 126 19.10

Non-temporal reasoning is enough for proving safety properties and makes up the vast majority of proof steps in liveness proofs.

In this paper we use the terms type and sort interchangeably.

TLA + operator symbols correspond to the standard function and predicate symbols of first-order logic but we reserve the term "function" for TLA + functional values.

The standard semantics of TLA + offers three alternatives to interpret expressions[START_REF] Lamport | Specifying Systems: The TLA + Language and Tools for Hardware and Software Engineers[END_REF] Sec. 16.1.3]. In the liberal interpretation, an expression like 42 ⇒ {} always has a truth value, but it is not specified if that value is true or false. In the conservative and moderate interpretations, the value of 42 ⇒ {} is completely unspecified. Only in the moderate and liberal interpretation, the expression false ⇒ {} has a Boolean value, and that value is true. In the liberal interpretation, all the ordinary laws of logic, such as commutativity of ∧, are valid, even for non-Boolean arguments.

The typical injectivity axiom ∀m Int , n Int : i2u(m) = i2u(n) ⇒ m = n generates instantiation patterns for every pair of occurrences of i2u. Noting that i2u is injective iff it has a partial inverse u2i, we use instead the axiom ∀n Int : u2i(i2u(n)) = n, which generates a linear number of i2u(n) instances, where u2i : U → Int is unspecified.

This encoding does not allow us to implement the standard TLA + interpretation of strings, which are considered as tuples of characters. Fortunately, characters are hardly used in practice.