B Marchi
email: b.marchi@unibs.it-simone.zanoni@unibs.it

S Zanoni

Investments in energy efficiency with variable demand: SEC's shifting or flattening?

Keywords: Energy efficiency, Investment, SEC, Uncertainty, NPV

In order to support energy efficiency improvement, it is essential to monitor the energy performance and to make benchmarking with similar process or related Best Available Techniques. Among different key performance indicators that compare similar processes, the most relevant for the industrial sector is the specific energy consumption (SEC). With regard to the energy demand in an industrial process, a variable and fixed portion can generally be distinguished: as a direct consequence the amount of energy used per unit of product (SEC) usually decreases while the production rate increases. It should be noted that often production processes face variable demand over their utilization. Aim of this work is to propose a novel decision model to support the identification of the more suitable investment in energy efficiency given the variable demand expected, explicitly considering that the effect of investments in energy efficiency can be categorized in two main categories: those shifting the SEC curve and those flattening the SEC curve.

Introduction

Energy efficiency is an essential part of a sustainable energy future as it helps reducing the energy consumption. In addition, energy efficiency leads to many other benefits, such as: it drives economic growth creating jobs and investment opportunities, it reduces greenhouse-gas emissions and air pollutants, it lowers fuel expenditures and it enhances energy security [START_REF]World energy investment outlook[END_REF]. As it is shown in Figure 1, the industrial sector is the greater energy consumer than any other end-use sectors, currently consuming about 50% of the world's total delivered energy [START_REF]How much energy is consumed in the world by each sector? Retrieved from[END_REF], [START_REF] Zhao | A comparative study of energy consumption and efficiency of Japanese and Chinese manufacturing industry[END_REF]. Moreover, in Figure 2 it is possible to observe that, over the next 20 years, the worldwide industrial energy consumption is expected to grow from 3,900 Mtoe in 2014 to 5,000 Mtoe in 2035 by an average of about 6% per year [START_REF] Bp P.L.C | Energy Outlook 2035[END_REF]. Figure 2. Industrial sector energy consumption from 1990 to 2035 (Mtoe) [START_REF] Bp P.L.C | Energy Outlook 2035[END_REF] Recently, energy efficiency in the industrial sector has emerged as one of the most significant manufacturing decision option and it is gaining an increasingly relevance [START_REF] Hoque | A heuristic solution procedure for an integrated inventory system under controllable lead-time with equal or unequal sized batch shipments between a vendor and a buyer[END_REF], [START_REF] Fysikopoulos | Energy Efficiency of Manufacturing Processes: A Critical Review[END_REF]. The key drivers for a gradual process of rethinking towards a more energyefficient acting are: the energy turnaround in Europe including the "20-20-20" targets, the great impact of energy issue on the strategic objectives of industrial companies, which are costs, time and quality and, finally, the customers' increasing ecological awareness [START_REF] Müller | Enabling Energy Management for Planning Energy-efficient Factories[END_REF]- [START_REF] Wang | DEA environmental assessment on U . S . Industrial sectors : Investment for improvement in operational and environmental performance to attain corporate sustainability[END_REF]. However, industry often views energy as an operational cost instead of a competitive advantage: energy savings are perceived as incidental benefits of other actions rather than as a central value-generating proposition.

In order to reach higher levels of energy efficiency, it is important to monitor the progress of the energy performance of the company and to make comparisons with the performances of other firms (benchmarking). For that reason, key energy performance indicators (KPIs) have been introduced, such as the Specific Energy Consumption (SEC): i.e. the ratio between the total energy consumption and the physical/economic output value. Some of the advantages of this indicator are that it is not influenced by price fluctuations and can be directly related to process operations and technology choice. However, a comparison of energy use in different units and aggregate efficiency is effectively impossible without the conversion of the physical units' value into a common economic value. [START_REF]Assessing Measures of Energy Efficiency Performance and their Application in Industry[END_REF] Generally, the energy consumption profile of an industrial plant is given by two contributions: one is fixed, given the production plant, and the other is variable depending on the production rate. Thus, the amount of energy consumed per unit of product, and so the value of the specific energy consumption, decreases with the increase of the production rate, as the incidence of the fixed share decreases (Figure 3). In many cases, industrial plants have to face variable, uncertain and discontinuous demands, e.g. days with high production and days with no production, working times alternate with idle times. For that reason, a wide range of production rate interests the production and the required flexibility results in reduced energy efficiency and increasing costs [START_REF] Faccio | Energy saving in case of intermittent production by retrofitting service plant systems through inverter technology: a feasibility study[END_REF]. Even the specific energy consumption is subject to uncertainty, as it is a function of the production rate. Consequently, investments in energy efficiency can be divided in two subcategories: investments that reduce the specific energy con- sumption equally for all the production ("SEC vertical shifting") and investments that reduce the specific energy consumption differently for different production rate, i.e. flattening the curve of energy consumption ("SEC flattening"). See Figure 3. The approach followed to evaluate the investments is the NPV (Net Present Value) method, in addition to the easier Payback period (PB), because, even if it is quite complex to apply, it gives better results and it allows comparing investments with different characteristics [START_REF] Bunse | Integrating energy efficiency performance in production management -gap analysis between industrial needs and scientific literature[END_REF], [START_REF] Jackson | Promoting energy efficiency investments with risk management decision tools[END_REF]. This work analyses the most suitable investment in energy efficiency for a given industrial plant under constant and uncertain demand profile. The remainder of the paper is organized as follows: Section 2 introduces the notations and assumptions, Section 3 presents the mathematical models of the different scenarios considered, Section 4 provides numerical examples to illustrate the proposed models and, finally, Section 5 concludes the paper summarizing main findings and providing suggestions for future research.

Assumptions and Notations

This paper considers the problem of identifying the most suitable investment in energy efficiency for a given industrial plant and a given demand profile.

The notation of the model is: The main assumptions of the model are the following:

--The demand rate D i is constant in Scenario 1, while in Scenario 2 it is uncertain and modelled with a stochastic distribution with parameters (α, β). --The nominal production rate is P max but the working one P is lower. Thus, due to the underuse, the performance of the plant is lower than the nominal one and inefficiencies are introduced. --The effective production rate corresponds to the demand rate (L4L assumption).

--The SEC is usually represented by a power function of the production rate P.

However, for simplicity, it has been considered an interval of production rate in which it is possible to approximate the SEC with a linear function (Figure 4) of P, as following:

SEC = a -b ⋅ P (1)
--The energy price per kWh p e [€/kWh] is assumed to be constant.

--The investment in vertical shifting, I shift , has effect on the constant of the curve, a. While the investment in flattening, I flat , has effect both on the constant, a, and on the slope, b, of the SEC's curve. --Considering the diminishing marginal contribution of investments [START_REF] Beaumont | Abatement cost curves: a viable management tool for enabling the achievement of win-win waste reduction strategies[END_REF]- [START_REF] Zanoni | A joint economic lot size model with price and environmentally sensitive demand[END_REF], a logarithmic investment function of the following form is used to describe the effect of the investments on the parameters of the specific energy consumption:

( )

x x I x x ln 0 ⋅ - = δ (2)
where x identifies the SEC's parameter affected by the investment (i.e. a or b).

Model's Formulation

In the present work, it is considered a firm that has to select the amount of investment in vertical shifting or in flattening the specific energy consumption curve maximizing the NPV. Often the demand is uncertain, random and fluctuating; for that reason, the company has to face a wide interval of possible production rate. In this case, investment in flattening the specific energy consumption acquires greater relevance. Traditional capital budgeting investment decisions identify a profitable energy efficiency investment when the discounted sum of savings, S, is greater than the total investment cost, I. This net present value (NPV) provides an estimate of the net financial benefit provided to the organization if this investment is undertaken [START_REF] Jackson | Promoting energy efficiency investments with risk management decision tools[END_REF].

max NPV = S i 1+ ρ ( ) i -I shift + I flat ( ) i=1 n ∑ = c 0,en -c en ( ) ⋅ D i ( ) 1+ ρ ( ) i -I shift + I flat ( ) i=1 n ∑ (3)
where

e en p SEC c ⋅ = (4) a = a 0 -δ a,shift ln I shift ( ) -δ a, flat ln I flat ( ) (5) b = b 0 -δ b, flat ⋅ ln I flat ( ) (6)
Savings, S i , are introduced by the reduction of the specific energy consumption and thus by the reduction of the energy cost of the production (Eq. 3). The subscript i identifies the year considered and it varies from 1 to n, which is the lifetime of the investment. In a first step, it has been considered the scenario where demand rate is constant (Scenario 1) evaluating the optimal investment decision for a given input value of the production rate. Then, in a second step, it has been modelled the demand rate and, thus, the production rate with a probability distribution (Scenario 2), defined in the assumption. Table 1 summarizes the demand modelling and the investment decisions of each considered scenario: Stochastic Distribution Flattening

Scenario 1.1

In Scenario 1.1, the demand is constant and the only investment considered is the vertical shifting of the specific energy consumption (I shift ). It is possible to study the function and its derivatives in order to evaluate the convexity of the NPV function in I shift and to find the optimal value of I shift * , that is:

∂NPV ∂I shift = 0 ⇒ I shift * = Dp e δ a,shift 1 1+ ρ ( ) i i=1 n ∑ (7)

Scenario 1.2

In Scenario 1.2, the demand is still constant as the previous scenario; however, the only investment considered is the flattening of the specific energy consumption (I flat ) and the optimal value of I flat * is:

∂NPV ∂I flat = 0 ⇒ I flat * = Dp e δ a, flat -δ b, flat P ( ) 1 1+ ρ ( ) i i=1 n ∑ (8)

Numerical Study

In the present section two examples are presented: in the first, general investment alternatives which impact the entire production plant are considered; while, in the second, the subject of the study is related to a particular sub-system. Example 1 illustrates the results of the models in a specific sector and compares the behaviour of the different scenarios. The parameters used in Scenario 1 are the following: D = 1500 units/year, P max = 2000 units/year, n = 10 year, ρ = 4%, p e = 0.25 €/kWh, a 0 = 10, b 0 = 0.001, δ a,shift = 0.04, δ a,flat = 0.2, δ b,flat = 0.0001. After a first insight in Scenario 1, in Scenario 2 we assumed that the demand is modelled with a uniform distribution with parameters (750, 1750); while the other parameters are the same. The numerical example, for a given production rate (Scenario 1) and for the uniform distribution (Scenario 2), leads to the following results (Table 2): As can be observed in Table 2, both the investments result convenient (NPV > 0) and generates energy cost savings. In particular, Scenario 1.2 (i.e. the scenario in which the investment in flattening is considered) leads to a better result reducing the specific energy consumption of about 3 % with respect to the as -is scenario, i.e. without any kind of investment, in which the SEC was 8.5 kWh/unit, and leading to a NPV greater than the one with investment in vertical shifting; while the payback period is almost equal. An interesting value of the production rate is the one in which both the optimal investments leads to the same specific energy consumption (P ° = 1617 units): at that value, the investments are equally affordable. If the production rate is lower, the investment in flattening the SEC curve is advantageous; on the contrary, if the production rate is greater, the more convenient investment is the one in vertical shifting (Figure 4).

As it has been previously said, in real context demand is subject to variability and uncertainty (Scenario 2). Thus, the value of D is not a fixed value but it is better defined with a stochastic distribution. It is interesting to observe how the optimal investment's amounts change whereas the demand rate can uniformly vary in a range of value. Every demand rate has a particular probability of occurrence and that probability is used as the weight in the determination of the total savings and, consequently, in the determination of the NPV. The uncertainty in the demand rate still leads to attractive NPV in both the scenario and the payback is still in-between 2-3 years; however, the invested amount, the reduction of the specific energy consumption and the impact on the savings change because of the introduction of a probability distribution. In Example 2, it has been performed a study on two specific investment options. In order to reach an higher global energy efficiency and, consequently, a lower SEC, several alternatives exist: e.g. if we consider the energy consumption of a fan, it is possible to replace the motor with a more efficient one (IE 3 against IE 1) leading to a vertical shift to lower SEC, or to manage the intermittent production introducing an inverter technology which flats the SEC curve. These two options are characterized by a given cost for the investment: i.e., for a nominal power of 110 kW (400V -3ph), the cost of the investments can be estimated as € 8,000 and € 6,500, respectively (source: www.inverterdrive.com). A simulation has been performed in order to understand which of the different solution fits better with different load factor profiles, LF (Figure 5).

The results of the simulation conducted are represented in Figure 6. It is possible to observe that the return of both investments strongly depend on the specific load factor corresponding to the variable production rate, which follows the market demand. In particular, to higher load factor (LF3) correspond higher success of the replacement of the motor, while the result of the installation of the inverter alone shows lower NPV that the former, but for LF1 and LF2 the latter shows quicker PB.

Conclusions

Energy efficiency in the industrial sector has emerged as one of the most significant manufacturing decision option and is gaining increasingly relevance because of the great energy consumption and, consequently, of the related energy costs. In order to reach higher levels of energy efficiency, it is important to monitor the progress of the energy performance of the company and to make comparisons with performances of other firms (benchmarking). For that reason, the Specific Energy Consumption (SEC) indicator has been introduced. In many cases, industrial plants have to face variable and uncertain demands and, thus, a wide range of production rate interests their production. Consequently, two different effect of the investment can be pursued: vertical shifting of the SEC and flattening of the curve of energy consumption. It is important to take into account that, the first effect (vertical shifting) can be reached only with an expensive change of technologies while the other one (flattening) can be usually obtained with a less expensive effort on technologies or with an organizational improvement, therefore its investment cost may be negligible with respect to the other options. In the present work, the aim was to identify the more suitable investment in energy efficiency for different profile and variability of the demand and, thus, for different range of interest of the production rate. From the analyses carried out, it is possible to observe that, in the lifetime considered, both the subcategories of investment (vertical shifting and flattening) result convenient (positive NPV) and generate energy cost savings. In particular, in the first exam-

NPV PB

Motor IE3

Motor IE1+Inverter Motor IE3+Inverter

High Long Short Low ple proposed, the scenario in which the investment in flattening is considered leads to the best results leading to a NPV greater than the one with investment in flattening.

As it has been previously said, in real context demand is subject to variability and uncertainty (Scenario 2). Thus, the value of D is not a fixed value but it is better defined with a stochastic distribution and, for that reason, it has been also evaluate the optimal investments' amount considering that every demand rate has a certain probability of occurrence. Finally, another example has been performed analyzing a specific application in a variable load factor context.

Figure 1 .

 1 Figure 1. World shares of total energy use by end-use sector, 2011 [2]

Figure 3 .

 3 Figure 3. Effects on the specific energy consumption of different energy efficient investment

D

  Annual demand rate [unit] P Real production rate [unit/year] P max Nominal production rate [unit/year] n Investment's lifespan [years] a 0 Initial sensitivity coefficient on the constant of the SEC's curve b 0 Initial sensitivity coefficient on the slope of the SEC's curve a Sensitivity coefficient on the constant of the SEC's curve b Sensitivity coefficient on the slope of the SEC's curve a min Minimum value of the coefficient a b max Maximum value of the coefficient b c 0,en Energy cost per unit of production before investment [€/unit] c en Energy cost per unit of production after investment [€/unit] kWh [€/kWh] SEC 0 Specific energy consumption before investment [kWh/unit] SEC Specific energy consumption after investment [kWh/unit] S Savings introduced with investments [€] ρ Discount rate δ a,shift Decrease coefficient in the constant of the SEC per € increase in I shift δ a,flat Decrease coefficient in the constant of the SEC per € increase in I flat δ b,flat Decrease coefficient in the slope of the SEC per € increase in I flat I shift Investment made to shift the SEC (decision variable) [€] I flat Investment made to flat the SEC (decision variable) [€]

Figure 4 .

 4 Figure 4. Specific energy consumption function with respect to the production rate

Figure 5 .

 5 Figure 5. Different load factors considered in the simulation

Figure 6 .

 6 Figure 6. Comparison between different investment solutions

Table 1 .

 1 Scenarios

	Name	Demand	Investment Decisions
	Scenario 1.1	Constant	Vertical shifting
	Scenario 1.2	Constant	Flattening
	Scenario 2.1	Stochastic Distribution	Vertical shifting
	Scenario 2.2

Table 2 .

 2 Results of the numerical example

			Scenario 1.1	Scenario 1.2	Scenario 2.1	Scenario 2.2
	I shift	[€]	121.66	-	101.49	-
	I flat	[€]	-	152.08	-	189.97
	SEC	[kWh/unit]	8.31	8.25	8.56	8.36
	NPV	[€]	462.47	612.03	367.38	719.53
	PB	[year]	2.79	2.71	2.86	2.79


Siqi Li

Eric Madelaine

A Denotational Semantics for Parameterised Networks of Synchronised Automata

Parameterised Networks of Synchronised Automata (pNets) is a machine-oriented semantic formalism used for specifying and verifying the behaviour of distributed components or systems. In addition, it can be used to define the semantics of languages in the parallel and distributed computation area. Unlike other traditional process calculi, p-Nets only own one pNet node as an operator which composes all subnets running in parallel. Using this single synchronisation artifact, it is capable of expressing many operators or synchronisation mechanisms. In this paper, we explore a denotational semantics for parameterised networks. The denotational semantics of parameterised networks we investigate is based on the behaviours of their subnets. The behaviour of a subnet is determined by both its state and the actions it executes. Based on the traces of a set of subnets, the behaviour of a pNet consisting of those subnets can be deduced. A set of algebraic laws is also explored based on the denotational semantics.

Introduction

With the rapid development of network technology, a number of software environments or middlewares emerge for facilitating the development of applications distributed over networks. These tools can be used in a variety of contexts, ranging from multiprocessors or clusters of machines, to local or wide area networks, to pervasive and mobile computing. In order to describe the behaviour of distributed systems and to verify properties of such systems, several formal languages and process calculi have been proposed in [START_REF] Baude | GCM: a grid extension to fractal for autonomous distributed components[END_REF][START_REF] Nierstrasz | Piccola -A small composition language[END_REF][START_REF] Schmitt | The kell calculus: A family of higher-order distributed process calculi[END_REF].

Parameterised Networks of Synchronised Automata, abbreviated as pNets, is an element of a pragmatic approach based on graphical specifications for communicating and synchronised distributed objects, in which both events (messages) and agents (distributed objects) can be parameterised. In this framework, pNets is a low level semantic model used for expressing the operational semantics of dedicated programming languages or high-level formalisms for distributed systems. The pNet model is based on the general notion of labelled transition systems, and on hierarchical networks of communicating systems (synchronisation networks), with explicit handling of data parameters in communication events and in the topology of processes. The agents in pNets can also be parameterised to encode sets of equivalent agents running in parallel. In order to realize communications and synchronisation among the agents in the networks, we use a notion of synchronisation vectors inherited from Arnold [START_REF] Arnold | Finite transition systems -semantics of communicating systems[END_REF], but augmented with explicit data values. It provides a general and flexible way to compose any number of components, which matches the expressiveness of many different usual process algebras [START_REF] Barros | Behavioural models for distributed fractal components[END_REF]. Recently we have extended the model towards open pNets, that contain Holes playing the role of process variables. Open pNets are able to express operators of process algebras or distributed systems, and provides us with a methodology to prove properties of program skeletons, or generic algorithms where we don't care about the details of some parts of the system. They are endowed with an operational semantics and a bisimulation based symbolic equivalence [START_REF] Henrio | A theory for the composition of concurrent processes[END_REF].

The concept of pNets was targeted towards the behavioural specification of distributed systems. In the last decade, (closed) pNets have been used to model the behaviours of a number of distributed systems featuring queues, futures, component systems, one-to-many communications, or fault-tolerance protocols Also, the pNets model offers good properties as a formalism for defining the semantics of distributed and heterogeneous systems: it provides a compact hierarchical format, easy to produce from source code. It can also be transformed using abstract interpretation of data domains, and the authors use this approach to construct finite pNets that can be analysed by model-checking [START_REF] Barros | Behavioural models for distributed fractal components[END_REF]. Some research has been done on the formal semantics for distributed computing in order to provide a strong theoretical foundation for those languages or frameworks used in this area. R. Koymans proposed a denotational semantics for a real-time distributed language called Mini CSP-R in [START_REF] Koymans | Compositional semantics for real-time distributed computing[END_REF]. A formal semantics was developed for a distributed programming language named LIPS using Dijkstra's weakest preconditions [START_REF] Rajan | Semantics for a distributed programming language using sacs and weakest pre-conditions[END_REF] . Both of the works focus on the parallel execution of the processes but put little emphasis on the hierarchy. As for the pNets model, the study on formalism has just started. An operational semantics and a bisimulation theory for closed pNets are proposed in [START_REF] Henrio | pnets: An expressive model for parameterised networks of processes[END_REF]. Their work also employs some examples to illustrate the expressiveness of pNets. Based on these discussions on formal semantics for pNets, the model checking technology that has been applied to verify the correctness of distributed applications or systems can be improved. Also, it becomes more persuasive and reasonable to be used on safety-critical systems. This paper proposes a denotational semantics for pNets using UTP theory [START_REF] Hoare | Unifying Theories of Programming[END_REF], which can provide another understanding of the formalism complementing the operational approach, and help deduce interesting algebraic properties of parameterised networks. A process (a subnet) in pNets is formalized by a predicate with structured traces and process states. Similar to traditional programming languages, the execution state of a pNet has completed state, waiting state and divergent state to represent the current status and control of the behaviour. A trace is introduced to record the interactions among subnets in the pNets system. The behaviour of a pNets system can be deduced by merging the behaviours of all subnets together. Besides, we investigate the behaviours of pNets composition with sub-pNets filling some holes by merging the traces of the sub-pNet into the upper-level pNet. Based on the formalized denotational semantics, a set of algebraic laws is obtained.

The rest of this paper is organized as follows. Section 2 recalls the formal definition of pNets with the explanation on the notations and term algebra. Section 3 presents the semantic model of parameterised networks. Section 4 explores a denotational semantics defined structurally on the different elements of the pNet model. Section 5 investigates a set of algebraic laws, including a set of laws concerning parallel composition and pNets composition. Also, we show how we prove properties of various constructs from other languages that we encode using pNets.

Parameterised Networks (pNets)

In this section, we recall the formal definition of pNets and the notations that are used in the definition. pNets are tree-like structures. Nodes of the tree (p-Net nodes) are synchronising artifacts, using a set of synchronisation vectors that express the possible synchronisation between the parameterised actions of a subset of the sub-trees. The leaves of the tree are either pLTSs or Holes. pLTSs (parameterised labelled transition systems), are transition graphs with explicite data values and assignments. Holes are placeholders for unknown processes, only specified by their set of possible actions, named the sort. A pNet tree with at least one hole is called an open pNet. Notations In the following definitions, indexed structures are extensively used over some countable sets, which are equivalent to mapping over the countable set. We use a i∈I i to denote a family of elements a i indexed over the set I. a i∈I i defines both I the set over which the family is indexed (called range), and a i the elements of the family. An empty family is denoted ∅. is the disjoint union on indexed sets (meaning both indices and elements should be distinct).

Term algebra The pNets model relies on the notion of parameterised actions, that are symbolic expressions using data types and variables. We leave unspecified the constructors of the algebra that will allow building actions and expressions. Moreover, we use a generic action interaction mechanism, based on (some sort of) unification between two or more action expressions, to express various kinds of communication or synchronisation mechanisms. We denote P the set of variables and T P the term algebra over the set of variables P. Within T P , we distinguish a set of action terms (parameterised actions) A P and a set of expression terms E P including a set of Boolean expressions (guards) denoted as B P (with: E P ∩ A P = ∅ ∧ B P ⊆ E P ∧ A P ∪ E P = T P ). Naturally action terms will use data expressions as subterms. To be able to reason about the data flow between pLTSs, we distinguish input variables of the form ?x within terms. The function vars(t) identifies the set of variables in a term t ∈ T , and iv(t) returns its input variables. pNets can encode naturally the notion of input actions in value-passing CCS [START_REF] Milner | Communication and Concurrency[END_REF] or of usual point-to-point message passing calculi, but it also allows for more general mechanisms, like gate negotiation in Lotos, or broadcast communications. Using our notations, value-passing actions à la CCS would be encoded as a(?x 1 , ..., ?x n ) for inputs, a(v 1 , .., v n ) for outputs (in which v i are action terms containing no input variables). Our action algebras also include a notion of local actions, that cannot be further synchronised; to simplify the notations in this paper we shall simply denote them as τ as in CCS.

0 1 l r P Q δ <δ(x 2 ), acc(x 2 ), δ> -> τ {<-, a 2 , r> -> a 2 } a2∈Sort(Q) C1 {<a 1 , -, l> -> a 1 } a1∈Sort(P ),a1 =δ(x1) Enable1 0 P Q <δ(y 2 ), acc(y 2 ), δ> -> τ {<-, b 2 , r> -> b 2 } b2∈Sort(Q) C2 {<b 1 , -, l> -> b 1 } b1∈Sort(P ),b1 =δ(y1) l [s 0 =0] δ [s 0 =0] s 0 :=1 r [s 0 =1] Enable2 s 0 :=0
Example 1. As a running example, we use pNets representing the Enable operator of the Lotos specification language. In the Lotos expression "P»Q", an exit(x) statement within process P terminates P, carrying a value x that is captured by the accept(x) statement of Q. In Fig. 1 we show two possible pNet encodings for the Lotos operator in a graphical format. Fig. 2 show a hierarchical pNet representing the expression "P»(Q»R)". A pNet is graphically represented by a box, containing circles with a process name, empty circles connected to a subnet and triangles with a line pointing to a box containing a pLTS.

We use a simple action algebra, containing two constructors δ(x) and acc(x), for any possible value of the variable x, corresponding to the statements exit(x) and accept(x). Both δ(x) and acc(x) actions are implicitely included in the sorts of all processes. The rest of the graphical elements will be explained below.

To begin with, we present the definition of pLTS: a pLTS is a labelled transition system with variables; variables can be manipulated, defined, or accessed inside states, actions, guards, and assignments. Without loss of generality and to simplify the formalisation, we suppose here that variables are local to each state: each state has its set of variables disjoint from the others, denoted vars(s).

Transmitting variable values from one state to the other is done by explicit assignment. Note that we make no assumption on finiteness of the set of states nor on finite branching of the transition relation.

We first define the set of actions a pLTS can use, let a range over action labels, op are operators, and x i range over variable names. Action terms are: α ∈ A ::= a(p 1 , . . . , p n ) action terms p i ::= ?x | Exp parameters (input variable or expression)

Exp ::= Value | x | op(Exp * ) Expressions
We suppose that each input variable does not appear somewhere else in the same action term: p i =?x ⇒ ∀j = i. x / ∈ vars(p j ). Input variables are only used as binders local to a pLTS, capturing data values coming from synchronisation with other pNets. They will not appear in the action alphabets of pLTSs and pNets, nor in the synchronisation mechanism.

Definition 1 (pLTS).

A pLTS is a tuple pLT S S, s 0 , → where:

• S is a set of states.

• s 0 ∈ S is the initial state.

• →⊆ S × L × S is the transition relation and L is the set of labels of the form α, e b , (x j := e j ) j∈J , where α ∈ A is a parameterised action, e b ∈ B is a guard, and the variables x j ∈ P are assigned the expressions e j ∈ E.

If s

α, e b , (xj:=ej ) j∈J -------------→ s ∈→ then iv(α) ⊆ vars(s ), vars(α)\iv(α) ⊆ vars(s), vars(e b ) ⊆ vars(s), and ∀j ∈ J. vars(e j ) ⊆ vars(s) ∧ x j ∈ vars(s ).

Example 2. Both pNets in Fig. 1 have a pLTS acting as a controller, in a stateoriented style at the top, and a data-oriented style at the bottom. In a pLTS, states have names, and transitions have labels, written as "action [guard] assignment * ". The initial state can also have an initial assignment, marked with an arrow. Variables assigned are those of the target state, while variables used in guards or expressions are those of the source state, and input variables of the action. For example the pLTS C 2 has a single state, with a state variable s 0 , its transitions include guards (e.g. [s 0 = 0]) and assignments (e.g. s 0 := 1).

Remark that the conditions on variable sets imply that the local variables of a state s include all input variables received in incoming transitions of s, as well as all local variables explicitely assigned in incoming transitions of s. We denote Trans(s) the set of outgoing transitions of s and tgt(t) the target state of t.

Hierarchy and Synchronisation : Now we define the hierarchical operator, called pNet node that is the only constructor required for building complex pNets. A pNet node has a set of sub-pNets that can be either pNets or pLTSs, and a set of Holes, playing the role of process parameters. The synchronisation between action of sub-nets is given by a set of synchronisation vectors: a synchronisation vector synchronises one or several internal actions, and exposes a single resulting global action. Communication of data between the partners of a synchronisation is done by unification. This synchronisation method is very flexible and generic. It allows to model classical synchronous communication The selection of specific vectors in the set (depending on the actions offered by subnets) models nondeterminism and interleaving. Channels or queues are not handled directly, they have to be modelled using a pLTS, that will be synchronised with the subnets involved. This is a very versatile and expressive schema, as shown in [START_REF] Henrio | pnets: An expressive model for parameterised networks of processes[END_REF].

Action terms for pNets are simpler than for pLTSs, and defined as follows: is the family of sub-pNets. • J ∈ I P is the set over which holes are indexed. I and J are disjoint:

α ∈ A S ::= a(
I∩J = ∅, I ∪ J = ∅ • S j ⊆ A S is a set of action terms, denoting the Sort of hole j. • SV k∈K k is a set of synchronisation vectors (K ∈ I P ). ∀k ∈ K, SV k = α l∈I k J k l → α k where α k ∈ A P , I k ⊆ I, J k ⊆ J, ∀i ∈ I k . α i ∈ Sort(pNet i ), and ∀j ∈ J k . α j ∈ S j . The global action of a vector SV k is Label(SV k ) = α k .
Definition 3 (Sorts and Holes of pNets).

-The sort of a pNet is its signature: the set of actions it can perform. For a pLTS we do not need to distinguish input variables. More formally 1 :

Sort( S, s 0 , → ) = {α{ {x ←?x|x ∈ iv(α)} }|s α, e b , (xj:=ej ) j∈J -------------→ s ∈→} Sort( pNet, S, SV ) = {α k | α j∈J k j → α k ∈ SV}
-The set of holes of a pNet is defined inductively; the sets of holes in a pNet node and its subnets are all disjoint:

Holes( S, s 0 , → ) = ∅ Holes( pNet i∈I i , S j∈J j , SV ) = J ∪ i∈I Holes(pNet i ) ∀i ∈ I. Holes(pNet i ) ∩ J = ∅ ∀i 1 , i 2 ∈ I. i 1 = i 2 ⇒ Holes(pNet i1 ) ∩ Holes(pNet i2 ) = ∅ A pNet Q is closed if it has no hole: Holes(Q) = ∅; else it is said to be open. 1 { {x k ← e k } } k∈K is the parallel substitution operation.
Graphical syntax: When describing examples, we usually deal with pNets with finitely many sub-pNets and holes, and it is convenient to have a more concrete syntax for synchronisation vectors. When I ∪J =[0.

.n] we denote synchronisation vectors as < α 1 , .., α n >→ α, and elements not taking part in the synchronisation are denotedas in: < -, -, α, -, ->→ α.

Example 3. Back to Fig. 1, the first synchronisation vector of pNet Enable1 means: for every action a 1 in the sort of P with a 1 = δ(x 1 ) for some x 1 , this a 1 action can synchronise with the l action of the controller, and this synchronisation is seen as a global action a 1 of Enable1. Vectors are defined in a parameterised manner, using variables universally quantified, and local to each vector. More examples can be found in [START_REF] Henrio | pnets: An expressive model for parameterised networks of processes[END_REF].

Composition operator: Open pNets can be composed by replacing one hole (at some arbitrary position in the tree) by a pNet with a compatible sort:

Definition 4 (pNet Composition). Let N 1 = pN et i∈I i , S j∈J j , SV and N 2 be two pNets, ho a hole of N 1 such that Sort(N 2) ⊆ S h0 , their composition denoted N 1[N 2] ho is: if ho ∈ J then N 1[N 2] ho = (pN et i ) i∈I N 2, S j∈J\{ho} j , SV else ∃i0 ∈ I.ho ∈ Holes(pN et i0 ) and N 1[N 2] ho = (pN et i ) i∈I [pN et i0 ← pN et i0 [N 2] ho ] , S j∈J j , SV
Remark that the composition operation does not change synchronisation vectors at any level in the pNet structure: only the hole involved is replaced by a subnet, and the sort inclusion condition ensures the actions of the subnets are properly taken into account by the synchronisation vectors. This is essential for keeping the compositional features of the model. Example 4. Figure 2 shows that the hole Q in the pNet Enable1 in Figure 1 is instantiated by another instance of Enable1 where Sort(Enable1) ⊆ Sort(Q). The composed pNet represents the Lotos process expression "P (Q R)", denoted as Enable(P,P')[Enable(Q,R)] P . Both C 3 and C 4 contain instances of the controller pLTS. Here a 3 , a 4 , b 3 and b 4 in the synchronisation vectors are variables that can take any value in the sort of their corresponding holes.

The Semantic Model

Now we define the denotational semantic model for pNets based on the UTP theory [START_REF] Hoare | Unifying Theories of Programming[END_REF] in this section. UTP uses relational calculus as a unifying basis to define denotational semantics for programs across different programming paradigms. In the semantic models, different programming paradigms are equipped with different alphabets and a selection of laws called healthiness conditions. An alphabet is a set of observational variables recording external observations of the program behaviour. The healthiness conditions are kind of invariants, imposing constraints on the values and evolution of variables. The observational variables are defined in a structural manner, using relational predicates relating the possible values of the variables of a given program construct with those of its parts.

In our semantic model, we use the notion of process, which is widely used in a number of process algebra and calculus, to denote the various forms of processes in the pNet formalism, namely pLTS, sub-pNets, holes and even a whole pNet system. We say that a process fires a transition, that means a transtion of a pLTS, an action of a hole, or a "global action" generated by the execution of a synchronisation vector in the case of a pNet node.

The predecessor of a pNet process is a process executed just before the current execution step. This process may either have terminated successfully so that the current process can start, or it may have not terminated and its final values are unobservable.

With the understanding of the specific meaning of these notions, we introduce the following variables defined for the alphabet to observe the behaviours of pNets processes.

-Status st, st : express the execution state of a process before and after a transition is fired, with values in {comp, wait, div}.

• completed state: A process may complete all its execution and terminate successfully. "st = comp" means that the predecessor of the process has terminated successfully and the control passes into the process for activation. "st = comp" means that the process itself terminates successfully. • waiting state: A process may wait for receiving messages from its environment. "st = wait" indicates that the predecessor of the process is at waiting state. Hence the considered process itself cannot be scheduled. "st = wait" indicates that the current process is at waiting state. • divergent state: A process may perform an infinite computation and enter into a divergent state. "st = div" indicates that the predecessor of the process has entered into a divergent state, whereas "st = div" indicates that the process itself has entered into a divergent state. -Current state cs, cs : denote the state (corresponding to the set of states in pLTS) where the current execution begins and terminates. This is used to help relate all the transitions and figure out which transition should be fired. -Data store ds(s) s∈S , ds(s) s∈S : record the values of the local variables of the state s in the set S before and after an observation. We will use the notations ds and ds to denote the full set of Stores for simplicity. -Trace tr, tr : record a sequence of observations on the interaction among the subnets. The elements in the trace variable are in the form of α(v 1 , . . . , v n ) where n ≥ 1 or just a value v. Here, v 1 , . . . , v n can be values either recorded directly from the message transmission or computed from the expressions.

Notations for traces. In the following, t[i] is the i th element in the trace t; t 1 t 2 denotes that sequence t 1 is a prefix of sequence t 2 ; l k is the trace where the element l is repeated k times; l * the trace where l is repeated in any finite number of times; t t the concatenation of traces t and t ; and s A means trace s is restricted to the elements in set A.

Before we present the denotational semantics of each process in pNets, we will define some healthiness conditions that a pNet process should satisfy. The first point is that the trace variable introduced to our semantics cannot be shortened: an execution step can only add an event to the trace. This is encoded as the H1 law below: a predicate P defining the semantics of any pNet process must satisfy :

(H1) P = P ∧ Inv(tr) where Inv(tr) = df tr tr .

The next point deals with divergent processes: "st = div" means that the predecessor process has entered the divergent state and the current process will never start. Therefore, a pNets process P has to meet the healthiness condition below:

(H2) P = P ∨ (st = div ∧ Inv(tr))
A process may wait for receiving message from other subnets or the environment. If the subsequent process is asked to start in a waiting state of its predecessor, it leaves all the states unchanged, including the trace and all its other observational variables. It should satisfy the following healthiness condition: From the definition of H-function, we know that H(X) satisfies all the healthiness conditions. This function can be used in defining the denotational semantics for pNets model.

The definitions here are similar to the one in [START_REF] Hoare | Unifying Theories of Programming[END_REF], with the following correspondance with the variables ok and wait from the original UTP theory: st = comp corresponding to the situation that ok ∧ ¬wait, st = wait corresponding to ok ∧ wait and st = div corresponding ¬ok.

Denotational Semantics

In this section, we present the denotational semantics for the four constructs of pNets: pLTSs, Holes, pNet nodes and pNet composition. We use beh(P ) to describe the behaviour of a pNet process after it is activated. Here P can be any type of pNet or a transition of a pLTS.

Parameterised Labelled Transition System

The order of execution in a pLTS relies on the relations between states and transitions, encoded in its transition relation. The variable cs is used to keep tracking the execution of the pNets processes so that we know at which step the execution will continue. The denotational semantics of a pLTS is given below. beh( S, s 0 , → ) = df beh(Init((x j := e j ) j∈J ), s 0 ) beh( S, s 0 , → s0 ) beh( S, s 0 , → cs ) = df t∈Trans(cs) beh(t) beh( S, s 0 , → tgt(t) )

where P Q denotes the sequential composition in the form of relational calculus, meaning that P Q = ∃obs 0 .P [obs 0 /obs ]∧Q[obs 0 /obs]. The term obs (resp. obs 0 , obs ) represents the set of variables st, cs, ds and tr.

The behaviour of a pLTS is the set of traces computed from its initial state. The set of traces computed from an arbitrary state cs is the union of all traces obtained using its set of outgoing transitions Trans(cs), followed by the traces of their target states.

beh(Init((x

j := e j ) j∈J ), s 0 ) = df H st = comp ∧ ds(s 0 ) = {x j := e j } j∈J ) ∧ tr = ∧ cs = s 0
The above semantics deals with the initialisation on the local variables of the initial state as well as other observational variables. Now we look into the details of the execution of a transition. For the actions, as we defined in the action terms, we will mainly use action algebras in this form: α(?x 1 , . . . , ?x n1 , e 1 , . . . , e n2 ). For simplicity, we will use the notation α(?x, e) instead when giving our semantics. Note that the forms of the actions are not limited to this, but are out of the scope of this paper. The execution of one single transition is atomic without interruption by the other processes. If the guard evaluates to false, then the trace remains unchanged and the variables stay in the initial state. Otherwise there will be two stages. One stage is the waiting state, at which the process is waiting for input values and all other observational variables stay unchanged. The other stage is the terminating state. If there are input variables in the action, they will be assigned input values. Then, the values of the local variables in the assignments will be updated accordingly. beh(t)=beh(s α(?x,e),e b ,(xj

:=ej ) j∈J ----------------→ s ) = df H                 st = wait ∧ tr = tr ∧ cs = cs ∧ ds(s ) = ds(s ) ∨ st = comp ∧ ∃m ∈ Value . tr = tr α(m, e) ∧ cs = s ∧ ds(s ) = ds(s )[m/x, (e j /x j ) j∈J ]       e b st = comp ∧ tr = tr ∧ cs = cs ∧ ds(s ) = ds(s )          
Here, Value stands for all possible values which can be transmitted by subnets in the whole pNet. In the action α(?x, e), there is an input variable x, an expression e whose value will be sent. It is obvious that a value (denoted m here) is assigned to x, thus we have α(m, e) recorded in the trace and the value of x changed in the local variables of the target state s . Each transition produces a single action, and a single step in the relational semantics. After the execution of the transition, the pLTS moves to the target state at which the next execution will start. Example 7. Finally we give an example of a pLTS with value-passing, that is using an input variable.

The set of solutions is {tr, ds, cs}, where traces a formed by a sequence of i/o actions a finite number of times, eventually followed by a single i action (when moving to state 1). Naturally in each cycle the value carried can be different:

i(?x) o(x) 0 1
A pLTS with a data store tr = Cycles(l), ds = ∅, cs = 0

∨ tr = Cycles(l) i(v l+1 ) , ds = {x := v l+1 }, cs = 1, ∀v l+1 ∈ Value. in which Cycles(l) = (i(v k ), o(v k )) * with ∀k ∈ [1..l].v k ∈ Value 4.

Holes

Now we investigate the semantics for the holes, where we benefit from the semantics of transitions in pLTSs. For a hole H with sort Sort(H), we define the maximum behaviour of H by building a single state pLTS, being able to perform any sequence of actions of the sort.

M axLT S(H) = {s 0 }, s 0 , → , with ∀a ∈ Sort(H).s 0 a --→ s 0 beh(H) = df beh(M axLT S(H))

Parallel Composition

This section investigates the behaviour of a pNets system composed of a set of subnets running in parallel. Let pN et = pN et i∈I i , S j∈J j , SV . Its behaviour is the composition of the behaviours of all the subnets by merging the traces together.

We do not put any constraint on the finiteness of the pNets model -a pNets system is able to compose an unbounded number of subnets. But for readability we assume here I ∪ J = [1, n], thus n pairs of (st, tr) are used to observe each subnet, working concurrently to contribute to the composition result. Also remark that the internal states and stores (cs, ds) of subnets are not observed. The composition is described by the following definition:

beh( pN et i∈I i , S j∈J j , SV ) = df          ∃ st 1 ,
        
in which the M erge predicate captures the behaviours of a parallel composition:

M erge = df         (∀i ∈ [1, n]. st i = comp) ⇒ st = comp ∧ (∃i ∈ [1, n]. st i = div) ⇒ st = div ∧ ∃i ∈ [1, n] • st i = wait∧ ∀j ∈ [1, n] • st j = div ⇒ st = wait∧ ds = i∈[1,n] ds i ∧ ∃u ∈ (tr 1 -tr 1 . . . tr n -tr n ). tr = tr u        
The status of the composed behaviour is determined by the n parallel components together. The composition terminates if all the processes terminate and diverges as long as one of the processes diverges. Then the composition stays at waiting state if one of the processes waits and none of the others diverges. Finally, the composition of these n traces is produced by the trace synchronisation operator :

Trace synchronisation. This operator takes n arguments tr itr i , each being a subsequence of arbitrary length of actions of the corresponding subnet. It computes a set of subtraces that M erge will append to the traces of the composed pNet.

case-1 If all the input traces are empty, the result is a set of an empty sequence:

|| . . . || = { } case-2
If there is a synchronised action (τ in this paper) in the head of one of the input traces, it is automatically visible at the upper level of the pNet, so we directly record this action in the merged traces. case-3 In all other situations, we need to select one synchronisation vector matching an event group within the set of the first observations of all the n input traces (Definition 5) and then figure out a synchronised event. Remember that a synchronisation vector concerns any (non-empty) subset of the subnets of the current pNet node. Let us denote as Value the set of all possible values which can be transmitted by subnets in the whole pNet and vars(SV ) the variables of a synchronisation vector SV .

= ∃k ∈ [1..n]. e k = τ

Definition 5 (Events Match).

Given a set of events {e o , e p , ..., e q } ⊆ {e 1 , e 2 , ..., e n }, we say that they match if there exists a synchronisation vector SV = α l∈L l → α ∈ SV and a valuation function φ = {x → Value|x ∈ var(SV )} that lets both (α l ) l∈L φ = {e o , e p , . . . e q } and L = {o, p, . . . , q} satisfied. We write EMatch(SV, α , φ, e o , e p , . . . , e q ).

With this definition, we can complete the definition of trace synchronisation: EMatch(SV, α , φ, e o , e p , . . . , e q ) =⇒ e 1 t 1 || . . . e n t n = α φ l | l ∈ e 1 t 1 . . . t o e o+1 t o+1 . . . t p e p+1 t p+1 . . . t q e q+1 t q+1 . . . e n t n Example 8. Now we use the pNets example in Fig. 3 with explicit data transmission to present how its denotational semantics is computed by using our definition. In this 2-places buffer, you can see two pLTSs with identical transitions. It is easy to obtain one possible trace for P1, with an arbitrary number of i/o cycles:

t P 1 = i(e 1 ), o(e 1 ), i(e 2 ), o(e 2 ), i(e 3 ) .
And below is a corresponding trace of P2.

t P 2 = i(e 1 ), o(e 1 ), i(e 2 ) .
From the set of synchronisation vectors defined, we can figure out that on the first execution step, P1 receives some value e 1 assigned to its input variable x 1 . This uses the first synchronisation vector of the Buffer pNet, and generates the global action gi(e 1 ). In the next step, P1 emits e 1 of x 1 , synchronised with action i(x 2 ) of P2, thus the x 2 in P2 is assigned the value e 1 , using the second vector, and generating action τ (e 1 ).

Then we can obtain one trace for the whole pNets by using the trace synchronisation operator. We have omitted the values of variables st and ds, that the reader will easily guess.

t P 1 || t P 2 = gi(e 1 ) l 1 .
where l 1 ∈ o(e 1 ), i(e 2 ), o(e 2 ), i(e 3 ) || i(e 1 ), o(e 1 ), i(e 2 ) .

There is only one choice in l 1 , matching the 2 nd vector of the Buffer pNet:

t P 1 ||t P 2 = gi(e 1 ), τ (e 1 ) l 2 .
where l 2 ∈ i(e 2 ), o(e 2 ), i(e 3 ) || o(e 1 ), i(e 2 ) . Now there are two possible choices, either use the first vector with event i(e 2 ) (yielding gi(e 2 )), or the third one with o(e 1 ) (yielding go(e 1 )).

Finally the full composition is given by the following regular expression:

t P 1 || t P 2 = gi(e 1 ), τ (e 1 ), gi(e 2 ), go(e 1 ), τ (e 2 ), gi(e 3 )
∨ gi(e 1 ), τ (e 1 ), go(e 1 ), gi(e 2 ), τ (e 2 ), gi(e 3 ) , after which both traces t P 1 and t P 2 are exhausted.

Composition operator

This section explores the behaviour of the composition of two pNets. In order to simplify the notation, we only consider here a composition operator that replaces a hole at the first (top) level of a pNet tree, that is less general than the composition operator in Definition 4.

Let

N 1 = pN et i∈I1 i , S j∈J1 j , SV 1 , N 2 = pN et i∈I2 i , S j∈J2 j , SV 2 . The pNet composition N 1 [N 2 ] ho indicates that a pNet N 2 fills a hole indexed ho in N 1 . Now we describe the behaviour of N 1 [N 2 ] ho : beh(N 1 [N 2 ] ho ) = df        ∃st 1 , st 1 , st 2 , st 2 , tr 1 , tr 1 , tr 2 , tr 2 , ds 1 , ds 1 , ds 2 , ds 2 . st 1 = st 2 = st ∧ tr 1 = tr 2 = tr ∧ beh(N 1 )[st 1 , st
      
The first four predicates describe the two independent behaviours of pNets N 1 and N 2 being composed (running in parallel in essence). The last predicate N M (ho) mainly does the merging of the contributed traces of the two behaviour branches for recording the communication, which is defined below.

N M (ho) = df            st 1 = comp ∧ st 2 = comp ⇒ st = comp ∧ st 1 = div ∨ st 2 = div ⇒ st = div ∧ st 1 = wait ∧ st 2 = div ⇒ st = wait ∧ st 2 = wait ∧ st 1 = div ⇒ st = wait ∧ ds = ds 1 ∪ ds 2 ∧ ∃u ∈ (tr 1 -tr 1 )[tr 2 -tr 2 ] ho . tr = tr u           
The control state of the composed behaviour of the pNet is determined by the combination of the status of the two pNets, which is similar to parallel composition. The trace of the composition is a member of the set of traces produced by trace composition operator [ ] ho . In the situation where the inner input trace is not empty, we need to check first whether these two traces match (see Definition 7). Only two matching traces can be merged. Then we find out the first pair of matching events (see Definition 6) from the matched traces respectively and compute the corresponding action for the merged trace.

Trace composition. Operator

Let t 1 and t 2 be two traces of N 1 and N 2 respectively.

Definition 6 (Events Match for pNets Composition). Given a pair of events e 1 and e 2 , we say that they are matched for pNets composition if there exists a synchronisation vector SV = α l∈L l → α ∈ SV 1 , with ho ∈ L, and a valuation function that lets α ho φ ho = e 2 . We have α φ = e 1 and we define an updated valuation function φ = φ+φ ho which replaces some of the values defined in φ by the ones in φ ho . We write < α , φ >= CEMatch(e 1 , e 2 , ho). Definition 7 (Traces Match). We say that the two traces t 1 and t 2 are matched (denoted as TMatch(t 1 , t 2 , ho)() if they satisfy such conditions: 1) For each element e 2 except synchronised action τ in t 2 , there exists an element e 1 in t 1 (where e 1 can be τ ) that satisfies CEMatch(e 1 , e 2 , ho); 2) Matching pairs of events are ordered consistently: given two such pairs (t 1 [i] = e 1 , t 2 [i ] = e 2 ) and (t 1 [j] = e 3 , t 2 [j ] = e 4 ) such that CEMatch(e 1 , e 2 , ho) and CEMatch(e 3 , e 4 , ho) are satisfied, then i < j =⇒ i < j . Now we present how the [ ] ho operator works under the third case. Let t 1 = s 1 e 1 r 1 and t 2 = s 2 e 2 r 2 , where we have TMatch(t 1 , t 2 ), ¬TMatch(s 1 , s 2 ) and < α , φ >= CEMatch(e 1 , e 2 ) all satisfied. Then:

s 1 e 1 r 1 [s 2 e 2 r 2 ] ho = {l 1 α φ l 2 | l 1 ∈ s 1 ||| s 2 ∧ l 2 ∈ r 1 [r 2 ] ho }
where the shuffle operator ||| is defined as:

||| = { }; ||| e 2 t 2 = { e 2 l | l ∈ ||| t 2 } e 1 t 1 ||| e 2 t 2 = { e 1 l | l ∈ t 1 ||| e 2 t 2 } ∪ { e 2 l | l ∈ e 1 t 1 ||| t 2 }
Example 9. Now we consider the semantics for Enable(P,P')[Enable(Q,R)] P expressing P (Q R) that we mentioned in Example 4. The behaviours of the composed pNet is computed from the behaviours of two pNets, which may contain a large number of observations. In order to make the illustration more readable, we select single traces from the sets to show the merging of the traces.

Let t 1 and t 2 be two traces of Enable(P,P') and Enable(Q,R) respectively where t 1 = α 1 , τ, α 2 , α 3 , t 2 = α 2 , τ, α 3 . We have here α 1 ∈ Sort(P ), α 2 ∈ Sort(Q) and α 3 ∈ Sort(R).

According to Definition 6, < α 2 , {a 4 →α 2 } >= CEMatch(α 2 , α 2 , P ) and < α 3 , {a 4 →α 3 } >= CEMatch(α 3 , α 3 , P ) are satisfied, both firing the synchronisation vector {< -, a 4 , r >→ a 4 } in Figure 2. Also, a 2 and a 3 are well ordered in t 1 and t 2 conforming with Definition 7. Then we can obtain one trace of the newly constructed pNet by merging the two traces above:

t 1 [t 2 ] P = α 1 , τ, α 2 , α 3 [ α 2 , τ, α 3 ] P = α 1 , τ α 2 α 3 [ α 2 τ, α 3 ] P = l 1 , α 2 , l 2
where l 1 ∈ α 1 , τ ||| and l 2 ∈ α 3 [ τ, α 3 ] P = τ, α 3 .

So we get one trace for Enable(P,P')[Enable(Q,R)] P : α 1 , τ, α 2 , τ, α 3 .

Algebraic Properties

The main purpose of the formalisation of a programming language is to prove its interesting properties. Most of them are elegantly expressed in the form of algebraic laws and equations. In this section, we explore a set of basic algebraic laws for pNets, based on standard trace semantics: 2 pNets are equivalent if they have same (potentially infinite) set of (finite) traces. pNets being a low level model used to express the semantics of high level languages, we have two categories of properties: general properties about pNets themselves, and specific properties about operators encoded using pNets. We start with a property of the Enable operator of Lotos encoded in Fig. 1. ), built as Enable(P,P')[Enable(Q,R)] P respectively. We would like to prove the associativity law:

Associativity of Enable

(P Q) R = P (Q R). P Q C4 C3 R SV>> SV>> EnableCompL1 (a) (P Q) R P Q R C6 C5 SV>> SV>> EnableCompL2 (b) P (Q R)
Fig. 4. Two pNets expressing Enable operators Sketch of the proof: On the left we have traces of Enable(P,Q) and Enable(P',R) whose traces are given below, denoted as t 1 and t 2 respectively.

t 1 = a n1 1 ∨ t 1 = a n1 1 τ a n2 2 , ∀n 1 , n 2 ∈ N t 2 = a n2 2 ∨ t 2 = a n2 2 τ a n3 3 , ∀n 2 , n 3 ∈ N.
Here, we can see that the traces from each set to be merged complying with the form s 1 a 2 t 1 [ a 2 t 2 ], where < α 2 , {a 4 →α 2 } >= CEMatch(α 2 , α 2 , P ) is satisfied. Also, TMatch(t 1 , t 2 , P ) is satisfied if n 2 = n 3 . Then we deduce the traces for Enable(P',R)[Enable(P,Q)] P :

tP Q-R = a n 1 1 ∨ tP Q-R = a n 1 1 τ a n 2 2 ∨ tP Q-R = a n 1 1 τ a n 2 2 τ a n 3 3
and symmetrically for Enable(P,P')[Enable(Q,R)] P :

tP -QR = a n 1 1 ∨ tP -QR = a n 1 1 τ a n 2 2 ∨ tP -QR = a n 1 1 τ a n 2 2 τ a n 3 3
Thus, we can say that the behaviours of (P Q) R) and (P (Q R)) are equivalent based on traces, and conclude that (P

Q) R = P (Q R) is satisfied.
Now we list a small number of typical laws that can be proved in a similar manner. For most of them, the proofs are straightforward, but long and tedious. Writing them formally requires a lot of notations that we have not introduced in the paper, and we will not do it here.

Symmetry/permutation of pNet nodes. The pNet node as a general parallel operator is symmetric.

For a pNet pN et i∈I i , S j∈J j , SV k∈K k , we assume that I ∪ J = [1, n] and we abstract each subnet as a process P . Then we alter the pNet node as: P 1 , . . . , P n , SV k∈K k . It is easy to get P 1 , . . . , P n , SV k∈K k = P π(1) , . . . , P π(n) , SV k k∈K where the structure for each SV k is < P 1 , . . . , P n >, the structure for each SV k is < P π(1) , . . . , P π(n) >, and π is a permutation on [1, n].

Guarded Choice. We introduce a concept of guarded choice, which enriches the language to support the algebraic laws. The guarded choice is expressed in the form:

{h 1 → P 1 }[] . . . []{h n → P n }.
Each element h → P of the guarded choice is a guarded component, where h can be a guard in the form of either α(?x, e) or τ . After one of the h i is performed or fired, the subsequent process is P i .

(par-2) Let P g = {a g → P

g }[][] i∈Ig {τ → P ig },
where g ∈ [1, n] and a g is the action that will be synchronised with others according to the synchronisation vectors while τ ig cannot be further synchronised.

We here put an index to τ to make it easy to be extended to be in a more flexible form. Then we have: where Card({x1, y1, ..., z1})2 +...+Card({xm, ym, ..., zm}) = n and {x 1 , y 1 , . . . , z 1 }∩ . . . ∩ {x m , y m , . . . , z m } = ∅. The notation (a x , a y , . . . , a z ) SV is used to indicate that the parallel execution of all the actions a x , a y , . . . , a z can trigger a synchronisation presented by SV , of which the result can be either an action to be synchronised or one that cannot be further synchronised.

(ncomp-2) (N 1 [N 2 ] ho1 )[N 3 ] ho2 = (N 1 [N 3 ] ho2 )[N 2 ] ho1
Proof. Sketch: expanding the definition of beh((N 1 [N 2 ] h0 ), and removing parts that are trivialy equal, the equation boils down to (here, obs stands for the set of observational variables we defined for our semantics: {st, tr, ds}): We suppose that any two traces we select to merge are matched according to Definition 7, thus we can always find pairs of events that are matched. If the two pairs of matched events (e, e 2 ) and (e , e 3 ) (e 2 and e 3 are events in the trace of N 2 and N 3 respectively, and e and e are events in the trace they are to be merged.) does not fire the same synchronisation vector, it does not matter which trace merge with the trace of N 1 first. Otherwise, the event α φ recorded in the composed the trace is determined by both e 2 and e 3 . Then we have the variables commuted:

LHS = ∃obs 1 ,
(ncomp-3) N 1 [N 2 [N 3 ] ho2 ] ho1 = (N 1 [N 2 ] ho1 )[N 3 ] ho2

Conclusions

In this paper we have formalized a denotational semantics for Parameterised Networks of Processes. A pNet node is considered as an operator composing a number of subnets running in parallel, which ensures the model's flexibility in expressing various operators, and we do not introduce any specific parallel operator to weaken this feature in pNets model. In our semantics, the subnets in the pNets are viewed as processes and the behaviours of each process are investigated by the execution of a subnet. A trace has been introduced to record the interactions among all the subnets in a pNets system. We have investigated the behaviours of subnets including holes. Then the behaviour of a pNet system can be achieved by merging the behaviours of a set of subnets. A set of algebraic laws on both parallel composition and pNet composition has been achieved based on the denotational semantics.

For the future, we plan to continue our formalisation of pNet systems. One aspect of our future work is to explore the algebraic semantics of the pNets model and study the relations among the three semantics: denotational semantics, operational semantics and algebraic semantics. Moreover, the pNets model can be extended by adding other features such as time issues or probabilities. And it is challenging to explore the semantics with these features.

Fig. 1 .EnableCompLFig. 2 .

 12 Fig. 1. Two pNets encodings for Enable

1 SVFig. 3 .

 13 Fig. 3. A pNet showing data flow

(

  H3) P = II (st = wait) P where we denote the logical choice: P b Q = df b ∧ P ∨ ¬b ∧ Q, the II relation: II = df Inv(tr) st = div Id. and the identity relation: Id = df (st = st) ∧ (tr = tr) ∧ (cs = cs) ∧ (ds = ds). Now we give the definition for H-function: H(X) = df (X ∧ Inv(tr)) st = comp (Inv(tr) st = div II)

Example 5 .δ-→ 1 ) 1 r-→ 1 ) 1 . 6 .

 511116 Recall the pLTS C 1 from Figure1. There are three transitions in the pLTS and we would like to show how its semantics is obtained. We start unfolding the definitions for Initialization, beh(C 1 ) = H (st = comp ∧ ∅ ∧ tr = ∧ cs = 0) beh((C 1 ) 0 ) Then the definition for states: beh((C 1 ) 0 ) = beh(0 l -→ 0) beh((C 1 ) 0 ) ∨ beh(0 beh((C 1 ) 1 ) beh((C 1 ) 1 ) = beh(beh((C 1 ) 1 )and for each transition, e.g.:beh(0l -→ 0) = H(st = comp ∧ tr = tr l ∧ cs = 0)Now we apply the semantics of the sequence ( ) operator, producing recursive equations on the value of the observational variables: beh((C1 ) 0 ) = H(B) such that B = ∃st 1 , tr 1 , cs 1 .(st 1 = comp∧tr 1 = tr l ∧cs 1 = 0)∧B[st 1 /st,tr 1 /tr, cs 1 /cs] Unfolding this equation k times, eliminating intermediate variables, and adding the initialisation step finally gives us:B = ∃st 0 , st 1 , ..., st k , tr k , cs k . ∨ (st k = comp ∧ tr k = tr l k ∧ cs k = 0) ∧ B[st k /st, tr k /tr, cs k /cs].Building now the semantics of the fullC 1 pLTS yields to a set of mutually recursive equations on predicate variables, with one such variable for each state of the pLTS. Here the solution is {tr, cs}, where: tr = l * , cs = s 0 ∨ tr = l * δ , cs = s 1 ∨ tr = l * δ r * , cs = s Example Consider now the pLTS C 2 in Fig. 1, who has a state variable s 0 . The initialization gives: beh(C 2 ) = H (st = comp ∧ ds = {s 0 := 0} ∧ tr = ∧ cs = 0) beh((C 2 ) 0 ) Its semantics is {tr, ds, cs}, where: tr = l * , ds = {s 0 := 0}, cs = 0. ∨ tr = l * δ , ds = {s 0 := 1}, cs = 0 ∨ tr = l * δ r * , ds = {s 0 := 1}, cs = 0.

  [ ] ho models how to merge two individual traces (under some constraints) of pNets N 1 and N 2 into a set of traces of N 1 [N 2 ] ho . case-1 If both input traces are empty, the result is a set of an empty sequence: [ ] ho = { } case-2 If the trace of the subnet is empty, the result is determined by the first observation of the non-empty trace: e t[ ] ho = { e l | l ∈ { }} = { e } case-3

.

  Consider the two pNets expressing (P Q) R (in Fig 4(a)), built as Enable(P',R)[Enable(P,Q)] P , and P (Q R) (in Fig 4(b)

  Identity operator. A pNet with only one hole indexed 0 of sort S is the identity of pNet composition:(ncomp-1) I s [N ] 0 = N where I s := ∅, (0 →S), {(0 →a) → a|a ∈ S} Composition operator. If N 2 and N 3 instantiate two holes in N 1 respectively meaning that Sort(N 2 ) ⊆ Sort(S ho1 ) and Sort(N 3 ) ⊆ Sort(S ho2 ) are satisfied, then we have:

= ∃obs 1

 1 , obs 1 , obs 2 , obs 2 . obs 1 = obs 2 = obs ∧     ∃obs 1 , obs 1 , obs 2 , obs 2 . beh(N 1 )[obs 1 , obs 1 /obs, obs ] ∧ beh(N 3 )[obs 2 , obs 2 /obs, obs ] ∧ ∃u ∈ (tr 1tr 1 )[tr 2tr 2 ] ho2 . tr = tr u     [obs 1 , obs 1 /obs, obs ] ∧ beh(N 2 )[obs 2 , obs 2 /obs, obs ] ∧ ∃u ∈ (tr 1tr 1 )[tr 2tr 2 ] ho1 . tr = tr u = RHS In a similar way, if N 2 instantiates one hole in N 1 and one of the holes in N 2 is instantiated by N 3 indicating that Sort(N 3 ) ⊆ Sort(S ho2 ) ⊆ Sort(S ho1 ) is satisfied, then:

  =⇒ e 1 t 1 || . . . e n t n = e k l | l ∈ e 1 t 1 || . . . t k e k+1 t k+1 . . . e n t n

  1 , tr 1 , tr 1 , ds 1 , ds 1 /st, st , tr, tr , ds, ds ] ∧ beh(N 2 )[st 2 , st 2 , tr 2 , tr 2 , ds 2 , ds 2 /st, st , tr, tr , ds, ds ] ∧ N M (ho)

  P1, . . . , Pg, Pg+1, . . . , Pn, SV = { (ax 1 , ay 1 , ..., az 1 ) SV 1 → P1, ..., P x 1 , ..., P y 1 , . . . , P z 1 , ..., Pn, SV } . . . []{ (ax m , ay m , ..., az m ) SVm → P1, ..., P xm , ..., P ym , ..., P zm , ..., Pn, SV } [][]i∈I 1 {τi1 → P i1 , P2..., Pn, SV }

	. . .

[][]i∈I n {τin → P1, ..., P i(n-1) , P in , SV }

  obs 1 , obs 2 , obs 2 . obs 1 = obs 2 = obs ∧     ∃obs 1 , obs 1 , obs 2 , obs 2 . beh(N 1 )[obs 1 , obs 1 /obs, obs ] ∧ beh(N 2 )[obs 2 , obs 2 /obs, obs ] ∧ ∃u ∈ (tr 1tr 1 )[tr 2tr 2 ] ho1 . tr = tr u , obs 1 /obs, obs ] ∧ beh(N 3 )[obs 2 , obs 2 /obs, obs ] ∧ ∃u ∈ (tr 1tr 1 )[tr 2tr 2 ] ho2 . tr = tr u

	
	   [obs 1

Card(A) returns the number of elements in the set A

Acknowledgment

This work was partially funded by the Associated Team FM4CPS between IN-RIA and ECNU, Shanghai. It was also supported by the Danish National Research Foundation and the National Natural Science Foundation of China (No. 61361136002) for the Danish-Chinese Center for Cyber Physical Systems, National Natural Science Foundation of China (Grant No. 61321064) and Shanghai Collaborative Innovation Center of Trustworthy Software for Internet of Things (No. ZF1213).


Xavier Hinaut

Johannes Twiefel

Recurrent Neural Network Sentence Parser for Multiple Languages with Flexible Meaning Representations for Home Scenarios

We present a Recurrent Neural Network (RNN), namely an Echo State Network (ESN), that performs sentence comprehension and can be used for Human-Robot Interaction (HRI). The RNN is trained to map sentence structures to meanings (i.e. predicates). We have previously shown that this ESN is able to generalize to unknown sentence structures in English and French. The flexibility of the predicates it can learn to produce enables one to use the model to explore language acquisition in a developmental approach. This RNN has been encapsulated in a ROS module which enables one to use it in a cognitive robotic architecture. Here, for the first time, we show that it can be trained to learn to parse sentences related to home scenarios with higly flexible predicate representations and variable sentence structures. Moreover we apply it to various languages, including some languages that were never tried with the architecture before, namely German and Spanish. We conclude that the representations are not limited to predicates, other type of representations can be used.

I. INTRODUCTION

For humans, communicating with current robots is challenging. It involves either learning a programming language or using complex interfaces. The most sophisticated ones, that recognise command given orally, are limited to a preprogrammed set of stereotypical sentences such as "Give me cup". In this paper, we propose an approach that allows one to use natural language when interacting with robots. Our architecture enables one to train a sentence parser easily on potentially many different contexts, including home scenarios (e.g. grasping remote objects or cleaning furnitures or rooms) [START_REF] Cruz | Interactive reinforcement learning through speech guidance in a domestic scenario[END_REF]. It can also enable the users to directly teach new sentences to the robot [START_REF] Hinaut | Exploring the acquisition and production of grammatical constructions through human-robot interaction with echo state networks[END_REF].

Current approaches typically involve developing methods specifically aimed at -or only tested on -the English language. Specific parsers then need to be designed for other languages, often adapting the algorithms and methods to their specificities. Here, we propose to overcome these limitations by providing a simple and flexible way of training a sentence parser for any arbitrary language, without requiring any new programming effort. This enables to easily create parsers even for languages that are spoken by a small population, thus broadening the potential application of robotics to new communities. *This work was partly supported by a Marie Curie Intra European Fellowship within the 7th European Community Framework Programme: EchoRob project (PIEF-GA-2013-627156).

1 X. Hinaut is with Inria Bordeaux Sud-Ouest, Talence, France; LaBRI, UMR 5800, CNRS, Bordeaux INP, Université de Bordeaux, Talence, France; and Institut des Maladies Neurodégénératives, UMR 5293, CNRS, Université de Bordeaux, Bordeaux, France xavier.hinaut@inria.fr 2 J. Twiefel is with Knowledge Technology Group, Department Informatik, Universität Hamburg, 22527 Hamburg, Germany twiefel@informatik.uni-hamburg.de

Here, we propose to overcome these limitations by providing a simple and flexible way of training a sentence parser for potentially any language. We demonstrate the potential of our model in home scenarios for four common European languages: English, German, Spanish and French. To make home robotics possible and useful, we need robots that are able to provide social adaptation to the user, and able to adapt continuously over their whole lifetime. Our architecture is inspired from neurosciences [START_REF] Dominey | A neurolinguistic model of grammatical construction processing[END_REF] and language acquisition theories [START_REF] Tomasello | Constructing a language: A usage based approach to language acquisition[END_REF][5] [START_REF] Bates | Cross-linguistic research in aphasia: An overview[END_REF] with the goal of modelling human language use: thus it aims to have these social and life-long adaptabilities.

First, we present the general ESN architecture. Then, we detail the reservoir sentence processing model. Afterwards, we show how it can be used within a ROS module, and give some perspectives. Finally, we provide corpora examples for a home scenario in four languages, and show how flexible the meaning representations can be.

II. METHODS & RESULTS

A. Echo State Networks

The language module is based on an ESN [START_REF] Jaeger | The "echo state" approach to analysing and training recurrent neural networks[END_REF] with leaky neurons: inputs are projected to a random recurrent layer and a linear output layer (called "read-out") is modified by learning (which can also be done in an online fashion). The units of the recurrent neural network have a leak rate (α) hyper-parameter which corresponds to the inverse of a time constant. These equations define the update of the ESN:

x(t + 1) = (1 -α)x(t) + αf (W in u(t + 1) + W x(t)) (1)
y(t) = W out x(t) (2)
with x(t), u(t) and y(t) the reservoir (i.e. hidden) state, the input and the read-out (i.e. output) states respectively at time t, α the leak rate, W , W in and W out the reservoir, the input and the output matrices respectively and f the tanh activation function. After the collection of all reservoir states the following equation defines how the read-out (i.e. output) weights are trained:

W out = Y d [1; X] + (3)
with Y d the concatenation of the desired outputs, X the concatenation of the reservoir states (over all time steps for all train sentences) and M + the Moore-Penrose pseudoinverse of matrix M . Hyper-parameters that can be used for this task are the following: spectral radius: this Fig. 1.

Sentences are converted to a sentence structure by replacing semantic words by a SW marker. The ESN is given the sentence structure word by word. Each word activates a different input unit. During training, the connections to the readout layer are modified to learn the mapping between the sentence structure and the arguments of the predicates. When a sentence is tested, the most active units are bound with the SW kept in the SWs memory to form the resulting predicate. (Adapt. from [START_REF] Hinaut | Exploring the acquisition and production of grammatical constructions through human-robot interaction with echo state networks[END_REF].)

B. Reservoir Sentence Processing Model

How do children learn language? In particular, how do they associate the structure of a sentence to its meaning? This question is linked to the more general issue: how does the brain associate sequences of symbols to internal symbolic or sub-symbolic representations? We propose a framework to understand how language is acquired based on a simple and generic neural architecture (Echo State Networks) [START_REF] Jaeger | The "echo state" approach to analysing and training recurrent neural networks[END_REF] which is not hand-crafted for a particular task.

The reservoir sentence processing model has been adapted from previous experiments on a neuro-inspired model for sentence comprehension using ESN [START_REF] Hinaut | Real-time parallel processing of grammatical structure in the fronto-striatal system: a recurrent network simulation study using reservoir computing[END_REF] and its application to HRI [START_REF] Hinaut | Exploring the acquisition and production of grammatical constructions through human-robot interaction with echo state networks[END_REF]. The model learns the mapping of the semantic words (SW; e.g. nouns, verbs) of a sentence onto the different slots (the thematic roles: e.g. action, location) of a basic event structure (e.g. action(object, location)). As depicted in Fig. 1, the system processes a sentence as input and generates corresponding predicates. Before being fed to the ESN, sentences are transformed into a sentence structure (or grammatical construction) semantic words (SW), i.e. nouns, verbs and adjectives that have to be assigned a thematic role, are replaced by the SW item. The processing of the grammatical construction is sequential (one word at a time) and the final estimation of the thematic roles for each SW is read-out at the end of the sentence.

By processing constructions [START_REF] Goldberg | Constructions: A construction grammar approach to argument structure[END_REF] and not sentences per se, the model is able to bind a virtually unlimited number of sentences to these sentence structures. Based only on a small training corpus (a few tens of sentences), this enables the model to process future sentences with currently unknown semantic words if the sentence structures are similar. One major advantage of this neural network language module is that no parsing grammar has to be defined a priori: the system learns only from the examples given in the training corpus.

Here are some input/output transformations that the language model performs:

• "Please give me the mug" → give(mug, me)

• "Could you clean the table with the sponge?"

→ clean(table, sponge) • "Find the chocolate and bring it to me" → find(chocolate), bring(chocolate, me) As shown, the system can robustly transform different types of sentences. Recently, we have explored how flexible our system is: we found that it can handle various kinds of representations at the same time. For instance, it allows to use nouns as main elements of a predicate, and use its arguments to fill in adjectives:

• "Search for the small pink object"

→ search(object), object(small, pink) It also allows to process various kinds of complex sentences:

• "Bring me the newspaper which is on the table in the kitchen" → bring(newspaper, me), newspaper(on, table), table(in, kitchen)

C. Preprocessing

Preprocessing to identify semantic words can be done in two ways, one may be more convenient than the other depending on the application:

• define a list of function words (i.e. all the words that are not in the meaning representation part of the construction) and consider any other word as semantic word; • define a list of semantic words (i.e. words that are in meaning representations). For some language like Spanish, one may need to extract some word suffixes (or prefixes) from semantic words. For instance, "sirve -lo" is usually written as one word ("sirvelo") even if its translation to English is composed of two words ("serve it").

Currently, there was no need to use part-of-speech (POS) tagging, but it may help to add this complementary information in the input representation of words.

D. Usage of the ROS Module

The proposed model was encapsulated in a ROS module [START_REF] Hinaut | Recurrent neural network for syntax learning with flexible predicates for robotic architectures[END_REF]. It is coded in the Python language and uses the rospy library. When running the program, the reservoir model is trained using a text file and the ROS service is initialized.

The training text file contains sentences and corresponding predicates and can be edited easily. If predicates represent multiple actions that have to be performed in a particular order, the predicates have to be specified in chronological order:

• bring coffee me, clean define which kind of predicate representation they want to use. Moreover, parentheses were removed in order to make the typing and editing quicker: by convention the first word is the predicate, and the following words are the arguments.

Once initialized, a request could be sent to the ROS service: it accepts a sentence (text string) as input and returns an array of predicates in real time. With an ESN of 100 units, the training of 200 sentences takes about one second on a laptop computer. Testing a sentence is of the order of 10 ms.

E. Perspectives

In Hinaut et al. [START_REF] Hinaut | A recurrent neural network for multiple language acquisition: Starting with english and french[END_REF], it has been shown that the model can learn to process sentences with out-of-vocabulary words. Moreover, we demonstrated that it can generalize to unknown constructions in both French and English at the same time. To illustrate how the robot interaction works, a video can be seen at youtu.be/FpYDco3ZgkU [START_REF] Hinaut | Humanoidly speaking -learning about the world and language with a humanoid friendly robot[END_REF] [START_REF] Twiefel | Using Natural Language Feedback in a Neuro-inspired Integrated Multimodal Robotic Architecture[END_REF]. The source code, implemented as a ROS module, is available at github. com/neuronalX/EchoRob 1 .

This ROS module could be employed to process various hypotheses generated by a speech recognition system (like in [START_REF] Twiefel | Using Natural Language Feedback in a Neuro-inspired Integrated Multimodal Robotic Architecture[END_REF]), then returning the retrieved predicates for each hypothesis, thus, enabling a semantic analyser or world simulator to choose the predicates with the highest likelihood. Preliminary work has shown that the model could be trained fully incrementally [START_REF] Hinaut | An incremental approach to language acquisition: Thematic role assignment with echo state networks[END_REF]: we plan to add this feature to the ROS module in the future.

In a nutshell, the objectives of this model are to improve HRI and provide models of language acquisition. From the HRI point of view, the aim of using this neural networkbased model is (1) to gain adaptability because the system is trained on corpus examples (no need to predefine a parser for each language), (2) to be able to process natural language sentences instead of stereotypical sentences (i.e. "put cup left"), and (3) to be able to generalize to unknown sentence structures (not in the training data set). Moreover, this model is quite flexible when changing the output predicate representations, as we have shown here. From the computational neuroscience and developmental robotics point of view, the aim of this architecture is to model and test hypotheses about child learning processes of language acquisition [START_REF] Tomasello | Constructing a language: A usage based approach to language acquisition[END_REF].

III. HOME CORPORA IN MULTIPLE LANGUAGES

A. Introduction

In this section, we show that the network is able to learn to parse sentences related to home scenarios. In particular, similar networks (with the same hyper-parameters) can learn to map sentences to predicates in English, German, Spanish and French.

Each line contains a sentence together with its corresponding meaning representation: left part of the semi-column is the meaning, right part is the sentence. One can see that the way to write predicates is fairly intuitive and can be done 1 We would be very grateful if you could share you corpus by uploading it to the repository. Thus we could enhance the model based on various corpora.

without prior knowledge of a predefined structure. Hereafter, we show the four home corpora. D. Spanish 1) abre puerta ; abre la puerta 2) contesta teléfono ; contesta el teléfono 3) riega plantas ; riega las plantas 4) liempia mesa ; limpia la mesa 5) toma café, sirve café en taza ; toma el café y sirve -lo en la taza 6) limpia mesa, pon taza sobre mesa ; limpia la mesa y pon la taza sobre ella 7) pon taza en izquierda ; pon la taza en la izquierda 8) toma teléfono, trae teléfono -me ; toma el teléfono y trae -me -lo 9) ve baño ; ve al baño 10) prepara té -me; prepara -me té 11) di broma -me ; di -me una broma 12) prepara sandwich -me, sandwich tomates ; prepara -me un sandwich con tomates 13) trae periodico -me, periodico sobre mesa, mesa en cocina ; trae -me el periódico que está sobre la mesa en la cocina 14) trae vestido -me, vestido azul, vestido en armario ; trae -me el vestido azul que está en el armario 15) trae lápiz -me, lápiz azul, lápiz junto taza, taza roja ; trae -me el lápiz azul junto a la taza roja 16) baila para mi, limpia piso, limpia mismo tiempo ; baila para mi y limpia el piso al mismo tiempo 17) apaga luz ; apaga la luz 18) encuentra botella, botella agua ; encuentra la botella de agua 19) busca objeto, objeto rosado pequeño ; busca el objeto rosado pequeño 20) busca receta internet, receta tiramisú ; busca la receta de tiramisú en internet 21) chequea si, si marido casa, marido mi, si cinco ; chequea si mi marido está en casa a las cinco E. French

B. English

F. Remarks

All sentences in German, Spanish and French correspond to the translation from English sentences, but there are some specificities in each language which make the predicates not a direct translation word by word. For instance, in the German sentence "geh an Telefon ; geh an das Telefon" ("answer phone ; answer the phone"), the "an" is not present in the English predicate because it is a "verb particle" (a German specificity). In a similar way, for the Spanish sentence "toma el telefono y trae -me -lo" ("get the phone and bring it to me"): the direct translation of "to me" would be "a mi", but it is more natural in Spanish to attach "-me" to the verb. When grammatical markers such as "-me" are used in the meaning representation, we use "-" to indicate it is not a word by itself, and the direction indicates to which word this marker should be attached.

G. Results

A network of 100 neurons is able to learn a set of 21 sentence-predicate pairs in any of these languages (i.e. reproduce exactly the same predicates for each sentence). In particular, a network of 75 units is able to learn separately any of English, French or Spanish corpora. Only the German corpus needs a 100 unit reservoir to be learned perfectly 2 . The difference of units needed is not surprising since some language specificities (for this tiny highly variable data set) may be more difficult than others to learn 3 . Moreover, we found for instance that a network with just 150 neurons was able to learn both English and German corpora at the same time. A network of size 325 was needed to learn the four corpora at the same time. Thus, the learning capabilities of the network seems to increase linearly when adding new languages 4 . This needs to be confirmed with further experiments.

We did not investigate generalization concerning these corpora, even if we already demonstrated that the same network could generalize on both English and French at the same time [START_REF] Hinaut | A recurrent neural network for multiple language acquisition: Starting with english and french[END_REF]. It was out of scope here; we focus on the flexibility of the meaning representations, and in particular in home scenarios. Furthermore, the corpora are of tiny size (only 21 sentences for each language) with a high variability in their structure. Consequently, each sentence is nearly unique in its structure (and its use of function words), which does not enable generalization as shown in previous studies.

IV. DISCUSSION

We proposed an approach that allows people to use natural language when interacting with robots. Our architecture enables to train a sentence parser easily on home scenarios: no parsing grammar has to be defined a priori, it only relies on the particular corpus used for training. Moreover, we showed that this neural parser is not limited to one language, but was able to learn corpora in four different languages at the same time: English, German, Spanish and French. In [START_REF] Dominey | A neurolinguistic model of grammatical construction processing[END_REF] an anterior version of the model was able to learn a Japanese copora, thus this neural model is applicable to many languages.

We used an Echo State Network (ESN) for the core part of the module for two main reasons. Firstly, it aims at modelling brain processes of language comprehension and language acquisition [START_REF] Hinaut | Real-time parallel processing of grammatical structure in the fronto-striatal system: a recurrent network simulation study using reservoir computing[END_REF]. Reservoir Computing paradigm (such as ESNs) is considered to be a biologically plausible model of "canonical circuits" (i.e. generic pieces of cortex) [START_REF] Dominey | Complex sensory-motor sequence learning based on recurrent state representation and reinforcement learning[END_REF] [START_REF] Maass | Real-time computing without stable states: A new framework for neural computation based on perturbations[END_REF] and is also used to decode neural activity of primate prefrontal cortex [START_REF] Rigotti | The importance of mixed selectivity in complex cognitive tasks[END_REF]. Secondly, we believe that HRI applications need modules that can be trained quickly (e.g. via oneshot offline learning), executed in tens of milliseconds, and can process (and provide outputs) in an incremental fashion (word by word).

The main drawback of the architecture is the fact that it only relies on function words to interpret a sentence: this may cause some ambiguities when an identical sentence structure corresponds to different meanings (see [START_REF] Hinaut | Real-time parallel processing of grammatical structure in the fronto-striatal system: a recurrent network simulation study using reservoir computing[END_REF] for more details). However, reliance on function words is also its strength since it enables to generalize to new inputs with only tens of sentence structures in the training corpus. We believe this is not a limitation of the architecture itself since some current unpublished experiments show that real semantic words could be used instead of SW markers (i.e. fillers).

The ability of the model to scale to larger copora depends on the similarity of the sentence structures in the corpus. If sentence structures are different variants of similar expressions (usually in a same home context), then there is no need to use an high number of units in the reservoir. For instance in [START_REF] Hinaut | Real-time parallel processing of grammatical structure in the fronto-striatal system: a recurrent network simulation study using reservoir computing[END_REF] we have shown that a 5.000 units reservoir could generalize up to 85% on unkown sentence structures on a corpus of size 90.000. Conversely, if sentence structures are highly different, the number of units should be increased (apparently linearly) with the number of sentences. Moreover, if sentence structures are similar or applied to the same home context (e.g. kitchen, living room, ...), the generalization to new sentence structures will come for free (with a quick tuning of main parameters: spectral radius, leak rate and input scaling). In future work, we could limit the number of reservoir unit needed if some contextual inputs are provided to the network: for instance, kitchen or living room environment will not provide the same context input, thus giving the network more information to discriminate/parse input sentences.

The way to write predicates (left hand of each line) is fairly intuitive and can be done without prior knowledge of a predefined structure like Robot Control Language (RCL) commands [START_REF] Dukes | Semeval-2014 task 6: Supervised semantic parsing of robotic spatial commands[END_REF]. In other words, we propose to let the users define which meaning/predicate representation they want to use. For instance, some words like "on" can be used in the meaning representation when needed (e.g. "clean table, put mug on table ; clean the table and put the mug on it"), and can be discarded when they are not necessary (e.g. "search recipe internet, recipe tiramisu ; search the recipe of tiramisu on internet"). Accordingly, one can adapt the meaning representation to any kind of "series of slots" as soon as there are consistent with each other: consistency should be kept both within slots and in the linear organization of the slots. In conclusion, this means that we are not limited to predicates, and our architecture could be used to learn other type of representations.

Read-out Layer Input Layer on the left put the toy .

	Semantic words
			left
		(SWs)
			put
	Sentence:		toy
			SWs Memory
	SW1 SW2	SW3
		the to	P A		SW1	P: Predicate Meaning: P (A, L)
			L
				left
						A: Agent
	Function words
	(FWs)	on	P	put		L: Location
	and	A L		SW2	put (toy, left) P(A, L)
	SW …	L A P	toy	SW3	Connection Fixed connections SW: Semantic word item
	(e.g. toy)
						Learnable connections
			Recurrent Neural			Inactive connection
			Network			Active connection

1, input scaling: 0.75, leak rate: 0.17, number of reservoir units: 100.

  table; bring me the coffee before you clean the table • bring coffee me, cleaning table; before cleaning the table bring me the coffee This predicate representation enables one to easily integrate this model into a robotic architecture. It enables the users to

table 5 )

 5 prends café, verse café tasse ; prends le café et verse le dans la tasse 6) nettoie table, met tasse dessus table ; nettoie la table et met la tasse dessus 7) met tasse gauche ; met la tasse à gauche 8) prends téléphone, amène téléphone moi ; prends le téléphone et amène le moi 9) va dans salle de bain ; va dans la salle de bain 10) fais thé moi ; fais moi du thé 11) raconte blague moi ; raconte moi une blague 12) fais sandwich moi, sandwhich tomates ; fais moi un sandwhich avec des tomates 13) apporte journal moi, journal sur table, table dans cuisine ; apporte moi le journal qui est sur la table dans la cuisine 14) apporte robe moi, robe bleu, robe dans placard ; apporte moi la robe bleue qui est dans le placard 15) apporte stylo moi, stylo bleu, stylo côté tasse, tasse rouge ; apporte moi le stylo bleu à côté de la tasse rouge 16) danse pour moi, nettoie sol, nettoie même temps; danse pour moi et nettoie le sol en même temps 17) éteins lumière ; éteins la lumière 18) trouve bouteille, bouteille eau ; trouve la bouteille d' eau 19) cherche objet, objet petit rose ; cherche le petit objet rose 20) cherche recette internet, recette tiramisu ; cherche la recette du tiramisu sur internet 21) vérifie si, si mari maison, mari mon, si heures cinq ; vérifie si mon mari est à la maison à cinq heures

1) ouvre porte ; ouvre la porte 2) réponds téléphone ; réponds au téléphone 3) arrose plantes ; arrose les plantes 4) débarrasse table ; débarrasse la

We only changed the network size by 25 unit steps.

In our experiments, the German sentence-predicate pair "switch off light; switch off the light" was the only one not learned by a 75 units network.

75(English)+75(Spanish)+75(F rench)+100(German) = 325

ACKNOWLEDGMENT

We thank Ikram Chraibi Kaadoud, Pramod Kaushik, Louis Devers, and Iris Wieser for their ideas on the home corpora, Francisco Cruz for his nice help on the Spanish corpus, and Fabien Benureau for his very/damn useful feedback.