Cédric Eichler
email: eichler@irit.fr

Patricia Stolf
email: stolf@irit.fr

Thierry Monteil
email: monteil@laas.fr

Khalil Drira
email: drira@laas.fr

Correctness by Construction and Style Preserving Reconfigurations of Distributed Systems

Keywords: Correctness by Construction, System Reconfigurations, Graph Rewriting, Dynamic Software Architecture

In distributed systems and dynamic environments, software architectures may evolve. A crucial issue when conducting system evolutions is to maintain the system in a consistent and functional state. Based on formal proofs in design-time, correctness by construction has recently emerged to efficiently guarantee system coherency. This article proposes a new method for the construction and specification of correct by construction system reconfigurations. Such transformations are characterized by graph rewriting rules that necessarily preserve the coherency of a system. We firstly propose operators on graph transformations and show that they conserve their correctness. Given a system specified by a graph grammar, these operators then serve to construct and characterize a set of correct transformations. We show in particular that any correct configuration can be reached starting from any other one without inconsistent intermediate step, using these transformations only.

Introduction

Dynamic software architectures are studied in order to handle adaptation in autonomic distributed systems, coping with new requirements, new environments, and failures. By their very nature, the description of evolving architectures cannot be limited to the specification of a unique static topology, but must cover the scope of all the correct configurations. This scope is characterized by an architectural style, qualifying what is correct and what is not. Once this distinction made, system transformations themselves must be specified to depict their applicability conditions and effects. A crucial undesirable implication of these evolutions is a potential loss of correctness, the system withdrawing from the scope of consistency.

Formal unambiguous methods are necessary to study the consistency of a system at a given time (i.e., its compliance to a specified architectural style). Several ways of doing so have been developed in the literature. The most immediate approach, checking the consistency of the system at run-time, may lead to combinatorial explosions and the necessity of roll-backs if it is discovered that the system is in an inconsistent state. To efficiently tackle correctness in the scope of dynamic reconfiguration, correctness by construction [START_REF] Gössler | Program analysis and compilation, theory and practice[END_REF] through formal approaches have emerged [START_REF] Baleani | Correct-by-construction transformations across design environments for model-based embedded software development[END_REF][START_REF] Bonakdarpour | Automated conflict-free distributed implementation of component-based models[END_REF]. Based on formal proofs and reasoning in design-time, they guarantee the correctness of a system, requiring little or no verifications in run-time. A way to achieve such proofs is to investigate the properties of transformations with regard to consistency preservation, so as to ensure that if a transformation is applicable on a correct configuration its result is another correct configuration. A transformation satisfying this property is then considered correct. Note that this notion of correctness is related to a certain style (a rule correct w.r.t. a style is not necessarily correct w.r.t. another). Conceptually, this means that any evolution characterized by a correct transformation can be safely triggered without worrying about the consistency of the resulting configuration.

Graph grammars constitute an expressive formalism for the characterisation of architectural styles. In particular, they offer a generative definition of the scope of correctness, where a set of graph rewriting rules called production rules axiomatically satisfy the criteria of correctness for the specified system. The approach presented in this paper consists in exploiting three operators on graph rewriting rule preserving the properties of consistency preservation (i.e., transformation correctness). Given some graph grammar, and thus a set of production rules, these operators can be used to construct a set of correct transformations. Evolutions specified by this set are sufficient to reach any correct instance of the style starting from any other one without any inconsistent intermediate step.

This paper present a new method for the construction and specification of correct transformations. To achieve this aim, the key contributions of this paper are :

1. The specification of two operators on graph transformations (specialization and composition). 2. The proof that these two operators conserve the correctness of transformations. 3. The stipulation of the hypothesises under which inversion of graph transformations preserve their correctness. 4. The characterization, for any given grammar (that satisfies the one hypothesis required for inversion to preserve correctness), of a set of correct transformations ensuring that :

-Any instance of the style may be reached starting from any other.

-Reconfigurations from a correct instance to another can be done without any inconsistent intermediate step.

Vocabulary and concepts from category theory is willingly ignored in this paper. Rather, a low-level, implementation-appropriate, view is adopted.

Section 2 introduces aspects of model transformations and approaches for correctness verification. Key concepts related to partially instantiated graphs, their relationships and transformations are introduced in Sec. 3. Based on those, said section presents the formal specification of architectural styles using graph grammars. Operators on transformations conserving their correctness are defined in Sec. 4. Section 5 shows that, starting from the set of correct transformations comprised in a given grammar, these operators can be used to generatively characterize a set of correct transformation. Besides, it establishes the property of configuration reachability using only correct transformation from the previously built set.

Related Works

Methodologies for correctness validation of evolving systems can be classified within three categories :

-Model checking, that consists in validating in run-time the whole system by verifying that some properties are met. This technique is very timeconsuming and may lead to combinatorial explosions. Furthermore roll-backs may have to be applied if it is discovered that the system is in an inconsistent state. -Transformation checking [START_REF] Hirsch | Consistent transformations for software architecture styles of distributed systems[END_REF][START_REF] Percebois | Rule-level verification of graph transformations for invariants based on edges' transitive closure[END_REF], consists in verifying in run-time that a transformation do not introduce any inconsistency. While it is generally more effective than the previous solution, roll-backs are not dismissed. In real-life systems, roll-backs induce a loss of time, energy, and resources and should be avoided. -Correct-by-Construction Transformations [START_REF] Baleani | Correct-by-construction transformations across design environments for model-based embedded software development[END_REF][START_REF] Bonakdarpour | Automated conflict-free distributed implementation of component-based models[END_REF][START_REF] Tounsi | From Event-B Specifications to Programs for Distributed Algorithms[END_REF], consists in guaranteeing in design time that a transformation necessarily produce a correct state. Not only does this method implies few to no reasoning in design-time, but it also completely discard roll-backs.

There exists also various taxonomy for transformations themselves, each different kind having different purposes. They are classified :

-Depending on their impact on the model used to represent a transformation.

• Exogenous transformations [START_REF] Baleani | Correct-by-construction transformations across design environments for model-based embedded software development[END_REF][START_REF] Bonakdarpour | Automated conflict-free distributed implementation of component-based models[END_REF][START_REF] Tounsi | From Event-B Specifications to Programs for Distributed Algorithms[END_REF] imply a change of model but do not modify the system (or its properties). They are used to generate code or to transform a graphical model into a more formal one, for example. • Endogenous transformations [START_REF] Hirsch | Consistent transformations for software architecture styles of distributed systems[END_REF][START_REF] Percebois | Rule-level verification of graph transformations for invariants based on edges' transitive closure[END_REF][START_REF] Oquendo | pi-arl: An architecture refinement language for formally modelling the stepwise refinement of software architectures[END_REF] remains the model invariant but change the state of a system (e.g., its architecture, its behaviour...). -Depending on their impact on the considered level of abstraction.

• Vertical transformations [START_REF] Baleani | Correct-by-construction transformations across design environments for model-based embedded software development[END_REF][START_REF] Bonakdarpour | Automated conflict-free distributed implementation of component-based models[END_REF][START_REF] Tounsi | From Event-B Specifications to Programs for Distributed Algorithms[END_REF][START_REF] Oquendo | pi-arl: An architecture refinement language for formally modelling the stepwise refinement of software architectures[END_REF] symbolize refinement that modify the granularity and the level of precision with which the system is represented.

• Horizontal transformations [START_REF] Hirsch | Consistent transformations for software architecture styles of distributed systems[END_REF][START_REF] Percebois | Rule-level verification of graph transformations for invariants based on edges' transitive closure[END_REF] are usually related to either model changes or evolutions of adaptive systems.

Endogenous horizontal transformations, called reconfigurations, typically represent system changes and adaptations.

In turn, the notion of correctness may vary depending on the transformations' nature. It may be the preservation of the system behaviour [START_REF] Baleani | Correct-by-construction transformations across design environments for model-based embedded software development[END_REF][START_REF] Bonakdarpour | Automated conflict-free distributed implementation of component-based models[END_REF], for code generation of model modification, for example. In some other case, correctness is linked to the presence, the absence or the the conservation of some property [START_REF] Percebois | Rule-level verification of graph transformations for invariants based on edges' transitive closure[END_REF]. Architectural styles are particularly relevant when considering dynamic system. In this context, consistency is synonym of the compliance to a style [START_REF] Hirsch | Consistent transformations for software architecture styles of distributed systems[END_REF]. Furthermore, and unlike [START_REF] Hirsch | Consistent transformations for software architecture styles of distributed systems[END_REF], we consider transformations as rewriting rules solely and decorrelate them from graphs they are applied to. In this way, correctness is a property of the rule only, and transformations are valid for the whole range of valid graphs. To the best of our knowledge, the method presented in this paper is the first to guarantee correctness-by-construction for reconfigurations w.r.t. an architectural style allowing to reach any of its instance.

3 Preliminaries, Graph Background.

The following offer a quick overview of the formal approach adopted in this paper. Firstly, variable attributed graphs are introduced, as well as relationships between them based on patterns matching through attributed graph morphisms. These relations then serve as a basis for the definition of various graphs transformations and rewriting techniques. Transformations themselves intervene in the definition of a software architecture, as finally seen.

Attributed Graphs

The state of a system at a given time can be modelled by a conceptual graph. Following the commonly used conventions for standard graphical descriptions, one considers that vertices (V ) represent services or architectural components and edges (E ⊆ V 2 ) correspond to their related connections, interdependencies or relationships. Each element el of the graph (i.e., its vertices and edges) is associated with an arbitrary number of attributes Att el representing any relevant property or information. Each attribute might be either constant or variable. It is a couple composed by its value Att el i and its domain of definition DAtt el i (the set of its possible values, Att el i DAtt el i ). An graph with constant and variable attributes is noted G = (V, E, Att).

To distinguish between constant and variable attributes in the examples, a constant attribute will be noted within quotation marks. Furthermore, we impose that two variable attributes from two disjoint graphs can not have the same name.

Pattern Matching and Relationships between Graphs

In order to find graph-like patterns in a context where attributes may be variable, the notion of element (vertices and edges) identification has to be defined. When trying to identified two elements, theirs attributes are matched two at a time w.r.t. the order of their occurrence (i.e., the i-th attributes of the first and second are associated with one another). Two elements are unifiable if (1) they have the same number of attributes and (2) matched attributes have the same domain of definition.

Element unifications thus induce attribute associations that can be seen as an equivalence relation (noted ∼ )over the set of considered attributes. The resulting setoid is called a set of identifications. Such a set is considered coherent if each of the induced equivalence class contains at most one constant. It simply means that no variable has been directly or transitively identified with two different constants, and that the overall attribute matching is correct.

An affectation is the function impacting attributes identifications. Each occurrence of a variable is substituted with the representative of its equivalence class. If the class contains a constant, it is its representative, else the representative is chosen arbitrarily.

The existence of a homomorphism between two graphs formalizes the presence of a pattern similar to the first graph within the second. A homomorphism h between two attributed graphs G and G is defined as an injective function f from the vertices of G to those of G that preserves the edges [START_REF] Rozenberg | Handbook of Graph Grammars and Computing by Graph Transformations[END_REF] (if there is an edge between two vertexes in G, there is an edge between their images in G). In addition, associated vertexes and edges have to be unifiable and the resulting set of identification Ĩ has to be consistent. An homomorphism is characterized by f and I, a consistent set of identification such as I ⊇ Ĩ. Due to space shortage, the formal definition and an example of graph homomorphisms are detailed in appendix. By notational abuse, any function f : A → B is assimilated to its canonic extension f :

A ∪ A 2 → B ∪ B 2 such as ∀ (a,ã) ∈ A 2 , f((a,ã)) = (f(a), f(ã)).
In addition of graph homomorphisms, we consider the notion of graph compatibility. The idea is to consider two induced sub-graphs and to associate them, not through any morphism, but a weaker condition : if there exists an edge between two vertices of the first graph there does not need to be an edge between their images, but if there is one, then those two edges have to be unifiable. Due to space shortage, the definition of compatibility is presented in appendix.

Example 1. Figure 1 shows an example of two compatible graphs. For readability sake, the attributes of the edges have not been represented and will all be considered equals (and thus disregarded).

Let V S be the set of vertices named 1, 2, and 3 in the figure and V' S be the set of vertices named 2 ′ , 3 ′ and 4 ′ . The function f : V S → V ′ S associating the vertices named 1 to 2 ′ , 2 to 4 ′ , and 3 to 3 ′ induces the (coherent) set of identification I = {a, b, c, x, y, "1 ′′ , "2 ′′ } with a ∼ x and b ∼ 2. G and G' are (f, I, V S , V' S )-compatible.

Graph Transformations

The occurrence of a pattern within a graph or a relation between two graphs, grant the possibility of applying graphs transformations. Since configurations of a system can be represented using graphs, graph transformations are used to model their evolutions.

Before introducing graph rewriting rules, let's consider two binary operator on graphs, restriction ↑ and expansion ↓. These lasts are similar to classical intersection and union, respectively. The difference arises from the fact that a similarity shall be found rather than a strict equality between elements of the graphs. Identifying analogous elements or sub-graphs is tackled by the notion of compatibility previously defined. Restriction and expansion thus depend on a graph compatibility, and are similarly characterized by an injective function between two sets of vertices and an affectation. Due to space shortage, formal definitions of these two operators are reported in appendix.

Example 2. With G, G', f, Aff, V S and V' S defined in the example 1, the result of G↓ (f,I,VS ,V ′ S ) G' is represented in Fig. 2(a). The result of G↑ (f,I,VS ,V ′ S ) G' is represented in Fig. 2(b).

Remark 1. For any (f, Aff, V S , V' S )-compatible graphs G and G' and any subgraphs G sub and G' sub ,

G sub ↓ (f,I,VS,V ′ S ) G' sub → G sub and G sub ↓ (f,I,VS,V ′ S ) G' sub → G' sub . Similarly, G sub → G sub ↑ (f,I,VS ,V ′ S ) G' sub and G' sub → G sub ↑ (f,I,VS,V ′ S ) G' sub . (a) restriction, G↓ (f,I,V S ,V ′ S ) G' (b) expansion, G↑ (f,I,V S ,V ′ S ) G'
Fig. 2. graph restriction (intersection) and expansion (union

)
Graph rewriting is a well-studied domain where a rule describes both a graph transformation and the circumstances under which it may be applied. The approach used in this paper is based on the Single Pushout (SPO) [START_REF] Löwe | Algebraic approach to single-pushout graph transformation[END_REF], where a rule is characterized by two graphs (L,R), respectively called left-and right-hand side, alongside a partial morphism m from L to R. For clarity sake, we consider rules satisfying L ∩ R = ∅, so that m is implicit and induced by the identity function over L ∩ R (noted K). In addition, transformations are given the possibility to update the value of attributes of the graph on which they are applied. An example of a rule and its application is provided in appendix. We assume the canonic notations where for any set S, its cardinality is noted |S| and an interval of integer between a and b is noted [|a, b|]. Definition 1. (Graph rewriting rule) A graph rewriting rule is a 3-tuple (L, R, OPs) where L = (V L , E L , Att L ) and R = (V R , E R , Att R ) are two graphs. OPs is a set of triples OP = (el, i, op), where el The following notations will be adopted :

∈ V K ∪ E K , i ∈ [| 1, |(Att K ) el | |],
1. r h(G) is the result of the application of a graph rewriting rule r to the graph G considering the homomorphism h : L → G. 2. r 2 h 2 .r 1 h 1 (G) is the result of the sequence of rewriting consisting in applying r 2 in regard of the matching h 2 to the result of r 1 applied to G with the matching h 1 .

Characterizing Architectural Style

Inspired from Chomsky's generative grammars, graph grammars [START_REF] Rozenberg | Handbook of Graph Grammars and Computing by Graph Transformations[END_REF] constitute an expressive formalism for describing dynamic structures. In this paper, architectural styles are characterized by such grammars. The correctness of the design (i.e. of the grammar) is not questioned and defines the scope of acceptable configurations.

Definition 2. (Graph Grammar)A graph grammar is defined by the 4-tuple (AX, N T, T, P ) where AX is the axiom, N T is the sets of non-terminal archvertices or archetypes of vertices, T is the set of terminal arch-vertices or archetypes of vertices, and P is the set of graph rewriting rules (or productions) belonging to the graph grammar.

Definition 3. (Instance belonging to the graph grammar) An instance belonging to the graph grammar (AX, N T, T, P ) is a graph whose vertices and edges have only constant attributes and obtained by applying a sequence of productions in P to AX. If it does not contain any vertex unifiable with an arch-vertex from N T , it is said to be consistent.

We consider in the following that an instance of the style is a correct configuration whether it is consistent or not. Restricting the notion of correctness to consistent instances would only require to verify whether a correct rule introduces a non terminal vertex.

Three Operators Preserving Transformations Correctness

The generative definition of the architectural style is at the very core of the work proposed here. By very definition, any production rule is correct by construction. This means that the specification of a style also provides an initial set of correct transformations. Starting from this original set, we wish to build other correct transformations. To do so, this section introduces operations on transformations and show that they preserve transformation correctness.

Specialization

The first operation introduced in this paper is rule specialization. It consists in strengthening the applicability condition of a rule and/or narrowing the scope of its possible results. A possible use is to restrict the application of a rule to a particular context or to an entity with a specific identifier (e.g., a component that has been reported as faulty) or nature, for example.

Definition 4. Specialization A rule q = (L q , R q , OPs q ) is said to be a specialization of p = (L p , R p ,OPs p ) if and only if each of the following conditions is met.

1. There is a homomorphism h L1 = (f L , I L ) : L p hL --→ L q such as the elements I L are attributes of L q and L q is invariant for the affectation induced by I L2 .

2. There is a homomorphism h R = (f R , I R ) : R p hR --→ R q such as the elements I R are attributes of R q , R q is invariant for the affectation induced by I R and

∀v ∈ V Rp , v ∈ V Lp =⇒ f R (v) = f L (v). 3. ∀ el ∈ V Lq ∪ E Lq , el / ∈ f L (V Lp ) ∪ f (E Lp ) =⇒ el ∈ V Rq ∪ E Rq . 3 4. ∀ el ∈ V Rq ∪ E Rq , el / ∈ f R (V Rp ) ∪ f R (E Rp ) =⇒ el ∈ V Lq ∪ E Lq . 4 5. OPs q = OPs p .
Lemma 1. For any graph G, any graph rewriting rule p and any specialization q of p, if there exist a homomorphism h such as L q h -→ G then there exists a homomorphism h such as L p h -→ G and q h(G) = p h(G).

Proof. Remember that a homomorphism is characterized among others by a consistent set of identifications that includes the identifications resulting from the actual element unifications. For any graph G, let's suppose that there exist a homomorphism h = (f, I) such as

L p h -→ G. L q → G =⇒ L p → G since L p → L q .
In particular, let h = (f • f L , I ∪ I L ∪ I R ). Since I L and I R are integrated within L q and R q , I ∪ I L ∪ I R can not be inconsistent. Hence, h is an homomorphism from L p to G. Thanks to the third condition, the application of p to G w.r.t. h can not leads to the apparition of a dangling edge that would not have been deleted by the application of q (since any vertex deleted by p is deleted by q). It is immediate that q h(G) = p ĥ(G). Theorem 1. A specialization of a correct (w.r.t. some architectural style) graph rewriting rule is correct (w.r.t. said style).

Proof. Let G be a graph representing a consistent configuration of some architectural style, p a graph rewriting rule p correct w.r.t. said style, and q a specialization of p.

If q is applicable to G w.r.t. h, according to lemma 1 there exists a homomorphism h such as p is applicable to G and q h(G) = p h(G). By hypothesis and since p is correct, p h(G) is a correct instance of the style. Hence q h(G) is consistent.

Composition

Compositionality of graph transformation depends on the formalism used for their specification [START_REF] Duval | Categorical abstract rewriting systems and functoriality of graph transformation[END_REF]. It is usually employed to enable re-usability of rules and to decompose rules, for better understanding and scalability [START_REF] Rensink | Compositionality in graph transformation[END_REF][START_REF] Balogh | Pattern composition in graph transformation rules[END_REF]. Remember that production rules can includes non-terminal vertexes with no "real-life" value. Consequently, composition can also be used in the context of this paper to skip inconsistent instances of the style. Yet, there exists, to the best of our knowledge, no low-level definition of composition for SPO-expressed rules. For rules expressed in the SPO formalism including variable attributes and operators, composition exists but is not unique and depends on compatibilities between parts of the rules, as defined below.

Definition 5. (Graph rewriting rule composition considering a specific compatibility) For any couple of graph rewriting rules (p,q) and any compatibility C = (f, I, V ⊆ V Lp , V'⊆ V Rq ) such as L p and R q are C-compatible. 5 Let G be the sub-graph of L p induced by V and let G' be the sub-graph of R q induced by V'.

If (H1) ∀ v ∈ V G , ∃ ṽ ∈ V Lp such as (v, ṽ) ∈ E Lp ∨ (ṽ, v) ∈ E Lp =⇒ f(v) ∈ K q and (H2) ∀(v, v ′ ) ∈ V G , f (v, v ′ ) / ∈ (K q ) 2 =⇒ ((v, v ′ ) ∈ E Lp =⇒ f ((v, v ′ )
) ∈ E Rq ) then p and q can be composed w.r.t. C and p• C q is the rewriting rule described by :

1. Let r 1 = (Aff I (G), G ↓ (f,Af f,VG,f (VG)) K q , ∅) and let M = r 1 (id,Aff I )(L p ). 6 L p•C q = M ↑ (f,I,V (G↓ f,Af f,V,V ′ Kq ) ,VK q L q . 2. Let r 1 ' = (Aff I (G'), K p ↓ (f,I,V,V ′ ) G', ∅) and M' = r 1 ' (id,Aff I )(R q ). 7 R p•C q = R p ↑ (f,I,V (G↓ f,Af f,V,V ′ Kq ) ,VK q M'.
3. OPs p•C q = OPs p ∪ OPs q Lemma 2. For any graph G and any graph rewriting rule r such as there exists a couple of graph rewriting rule (p,q) and a compatibility C with r = p• C q, if r is applicable to G w.r.t. h, then there exists a couple of homomorphism ( h, h) such as q is applicable to G w.r.t. h, p is applicable to q h(G) w.r.t. h, and r h(G) = p h.q h(G).

Proof. Let C = (f, I, V, V ′ ) and h be (f ′ , I ′ ).

According to remark 1, there exists h = ( f , Í) such as

L q h -→ L r . By hypoth- esis, L r h -→ G. Hence h = (f ′ | f (VL q ) • f , Í ∪ I ′ ) is such as L q h -→ G.
By definition of graph rewriting rules, there exists a homomorphism ĥ = ( f , I ′ ) such as R q ĥ -→ q h(G). According to remark 1, there exists h = ( f , Ì) such

as M h -→ L r . Let f : V Lp → V q h(G) be such as ∀v ∈ V Lp , f (v) = f ′ • f (v) if v ∈ V M and f • f (v) else. By construction, h = ( f , I ∪ I ′ ∪ Í) is a homomorphism from L p to q h(G) if it preserves edges. Thanks to H1, ∀(v, v ′ ) ∈ E Lp , (1) (v, v ′ ) ∈ (V M ) 2 ∨ (2) ((v, v ′ ) ∈ V G ∧ f (v, v ′ ) / ∈ (K q ) 2 ). (1) Since M h -→ L r h -→, (v, v ′ ) ∈ (V M ) 2 =⇒ f ((v, v ′ )) ∈ E G . (2) Thanks to H2, (v, v ′ ) ∈ V G ∧ f (v, v ′ ) / ∈ (K q ) 2 =⇒ f ((v, v ′ ) ∈ E Rq . Since R q ĥ -→ q h(G), f ((v, v ′ )) ∈ E G . Hence, L p h -→ q h(G).
Due to space shortage, we do not report here the second part of the proof that states that with the appropriate homomorphisms defined in this proof and the construction of R r , r h(G) = p h.q h(G).

Theorem 2. The composition of two correct (w.r.t. some style) graph rewriting rules is correct (w.r.t. said style).

This theorem is immediate considering lemma 2

Inversion

Inversion exploits the property of reversibility of graph rewriting rules [START_REF] Rozenberg | Handbook of Graph Grammars and Computing by Graph Transformations[END_REF]. It consists in defining an opposite transformation cancelling the effect of another. Intuitively, considering for example the deployment of a new server to absorb a load peak, inversion allows the characterization of its shut-down once the load goes back to normal. Inversion is classically conducted by swap the right and left hand-side of a rule. However, this would not be enough to guarantee correctness conservation. In addition, we have to verify that as long as a transformations that did require (i.e., that could be applied only in the presence of) the component has not been "cancelled", the component can not be suppressed. When using graph rewriting, this "require" relationship translates to the presence of the component in the image of the left hand-side of the rule considering the homomorphism linked with its application.

As a consequence, we assume that each vertex possesses an attribute that is a matching counter. This can be easily automated and hidden to the user by adding, for each element el, a concealed attribute ATT el 0 in N that is a mute free variable, except when initialized. It is initialized at 0 (i.e., for each production rule p, for all el element of R p \ K p , ATT el 0 = 0). To each production rule is appended operators that increment the counter of each element in K (i.e., for each el ∈ V K ∪ E K , OP = (el, 0, f : N → N such as f(x) = x+1) ∈ OPs). Definition 6. (Inverse rule) A graph rewriting rule r -1 is the inverse of a graph rewriting rule r if : R r -1 = L r , L r -1 = R r , and OPs r -1 = { OP = (el, i, f ) : ∃ ÕP ∈ OPs r , OP = (el, i, f -1 ) }.

Noticeably, if the inversion of a production rule is applicable on a graph, then the matching counter of each vertex that would be deleted during its application is equal to 0. Moreover, its application decrements the matching counter of each vertex in its invariant part. In addition, for any graph rewriting rule r, (r -1 ) -1 = r. Theorem 3. The inversion of a correct (w.r.t. some style) graph rewriting rule r is correct (w.r.t. said style) if :

-(H1) : there exists a "matching counter" as described previously.

-(H2) : for any instance of the style G, the presence of a pattern isomorph to R r in G implies that G can be obtained starting from the axiom by applying a sequence of correct rewriting rules, one of which being r (that has introduced said pattern).

Please note that the second hypothesis is not met for any grammar. Intuitively, for the set of rules : p 1 : AX → a, p 2 : AX → ab, it is possible to have a pattern corresponding to the right-hand side of a rule (a) in a word that can not be derived using said rule (ab). It is also not a property of the style (i.e., the scope of consistency) itself, but rather of its definition (i.e., the grammar). Indeed, the previous grammar can be rewritten in a way that respects this property such as : p 1 : AX → a and p 2 : a → ab.

Proof. By hypothesis (H2), if r -1 is applicable to G w.r.t. some homomorphism h, then there exists a sequence of rules and homomorphisms ((r i , h i )) i∈[|1,n]] such as r n h n .. . . .r 1 h 1 (AX) = G and there exists k ∈ [|1, n]] such as r k = r.

It is immediate that for any graph graph rewriting rule r and any graph G, if r is applicable to G w.r.t a homomorphism h then there exists a homomorphism h' such as r -1 h'.r h(G) = G. h' is the canonical homomorphism associating L r -1 = R r with the isomorph copy of R r introduced while applying r on G. Consequently, if k = n, the theorem is true since r -1 h(G) = r n-1 h n-1 .(. . . ) .r 1 h 1 (AX) which is by definition an instance of the style. If k < n, the idea of the proof is as follows:

According to H2, h(L r -1 has been introduced by applying r k (i.e., r n applied w.r.t. h n do not introduce anything required for the application of r -1 w.r.t. h). Hence r -1 is applicable on r n-1 h n-1 .(. . . ).r 1 h 1 (AX) w.r.t. h.

Since r -1 does not delete any element of G match with L rn through h n (H1), (2.a) suppressing dangling edges can not affect h n (since the suppressed extremity should also be matched through h n ), (2.b) r -1 do not invalidate h n Hence, r n is applicable to r -1 h.r n-1 h n-1 .(. . . ).r 1 h 1 (AX) w.r.t. h n . In particular, r n h n .r -1 h.(. . . ).r 1 h 1 (AX) = r -1 h(G).

By conducting this reasoning until getting r -1 h(G) = r n h n .(. . . ).r -1 h.r k .h k . (. . . ).r 1 h 1 (AX), we obtain r -1 h(G) = r n h n .(. . . ).r k-1 h.r k+1 .h k .(. . . ).r 1 h 1 (AX), which is by definition an instance of the style.

On one hand, we have seen in Sec. 3.4 that the definition of an architectural style through a graph grammar comprises a set of correct rules called production rules. On the other, section 4 introduces unary and binary operators on transformations that preserve their correctness. These two facts immediately bring up the following questions : what do we obtain if we apply introduced operators to the set of productions? Is a dynamic system manageable using correct transformations only?

Configuration reachability

The first worthwhile property that is studied here is the capacity of reaching a configuration given an initial state. Typically, a (potentially autonomic) manager identify a desirable configuration that better some optimization criterion. Can it necessarily be reached given the current state of the system? The focus of this paper is the correctness of rules, a property linked to their application on an instance of the style. In particular here, we aim at studying the reachability of configurations using correct rules only, and have few to no information on their behaviour w.r.t. states that do not conform the style.. Thus, the possible initial states are restricted to instances of the style. Theorem 4. Any instance of a given graph grammar can be reached starting from any other using only production rules and their inverses.

The proof is summarized in the next sub-section.

Avoiding inconsistent instances of the style

Instances of the style can be correct or not, depending on the existence of nonterminal vertexes within them. Such vertexes are theoretic artefacts with no "real-life" value. Inconsistent instances of the style thus carry vertex(es) that are not matched with any component of the modelled system. To avoid this discrepancy, one may wish to remain in the scope of consistent configurations and avoid inconsistent instances.

Theorem 5. For any graph grammar (AX, T, NT, P), let Trans be the smallest set of graph rewriting rules containing P for which inversion and composition have closure. 8 Any consistent instance of the grammar can be reached starting from any other without any inconsistent intermediary by applying a sequence of rules in Trans.

Proof. The idea of the proof of theorems 4 and 5 is as follows :

Firstly, for a given grammar, let's consider a graph whose vertexes represent configurations of the style. An edge model the application of a production (a rule and a homomorphisms) such as the application of the symbolized transformation to its source result in its target. For each edge (v, v ′ ) symbolizing the application of p, one can introduce an edge (v ′ , v) representing the application of p -1 cancelling the application of p.

Since there exists a path from the axiom to any vertex and a path from any vertex to the axiom, it is easy to see that there exists a path from any vertex to any other one. The fact that this graph is strongly connected directly implies theorem 4.

For each path from a consistence instance to another, each sub-path that contains only inconsistent instances can be by-passed by adding to the graph a vertex representing the composition of the transformation leading to or within the set of inconsistent instances. Finally, each inconsistent configuration can be deleted, and the resulting graph is still strongly connected, giving theorem 5.

Conclusion

Given a graph grammar specifying an architectural style, this paper introduces a method to build correct-by-constructions transformations that are style-preserving. It is important to notice that the style axiomatically defines the scope of correctness and that its faultlessness is not questioned. Correct transformations are particularly relevant in the management of dynamic distributed systems. Their use can assure the theoretical consistency of a system without requiring any checking in run-time.

The defined method originate from the fact that a graph grammar comprise a set of axiomatically correct transformations. The first contribution of this paper is the specification of correctness-preserving operators on system transformations. Alongside the initial correct transformations, they allow the characterization of a larger (infinite) set of correct transformations. We finally prove that any correct configuration can be reached starting from any other one without any inconsistent intermediate step using transformations from the previously defined set only.

However, the style-preserving property of one of the operator (inversion) is subject to an hypothesis on the grammar. Furthermore, there exists some grammars that do not satisfy hypothesis. In a short future, we plan on further investigating this property. We are particularly interested in grammar transformations that introduce the satisfaction of the required condition. On a more practical side, it is necessary to hide the intrinsic complexity of the formalism to future users. To this end, we wish to implement a graphical tool for the creation and manipulation of transformations.

Fig. 1 .

 1 Fig. 1. two compatible graphs

  and op is an unary invertible operation on (Datt K ) el i under which (Datt K ) el i has closure.A rule is applicable on a graph G = (V, E, Att) if there is a homomorphism h = (f, I) : L → G.Its application consists in (1) erasing the image of L\K and deleting the potential dangling edges. (2) Adding an isomorph copy of R\K integrating the affectation obtained with h. (3) Conducting the specified updates of attributes.

This homomorphism can be an identity alongside some set of identification.

Hence, h(Lq) has necessarily less free variables than Lp.

This means that any element deleted during an application of q is deleted during an application of p; i.e. any element of Lq that is not an image of an element of Lp by fL is invariant w.r.t. the application of q.

This means that any element added during an application of q is added during an application of p; i.e. any element of Rq that is not an image of an element of Rp by fR is invariant w.r.t. the application of q.

Note that there exists at least one compatibility since V' can be empty (in which case the rule would be applied on independent parts of the graph).

M is, modulo an affectation, Lp deprived of the part of G not identified with Kq via f (the part of G added when q is applied).

M' is, modulo an affectation, Rq deprived of the part of G' not belonging to f(Kp) (the part of G' suppressed when p is applied).

Acknowledgement The work presented in this paper has been partially funded by the ANR in the context of the project SOP, ANR-11-INFR-001.

Appendix

Definition 7. (Graph homomorphism with variable label) There exists an homomorphism h between two graphs G and G' such as G = (V, E, Att) and G' = (V', E', Att'), noted G → G' or G h -→ G', if and only if there is a consistent set of identification I and an injective function f : V → V', such as :

3. I ⊇ Ī, where Ī is the set of identifications resulting from element unifications.

The resulting homomorphism is characterised by the couple (f, I). Definition 8. (Compatible graphs) Two graphs G = (V, E, Att) and G' = (V', E', Att') are said to be compatible or (f, I, V S , V' S )-compatible if and only if there exists V S ⊆ V, V' S ⊆ V', a consistent set of identification I and a bijective function f : V S → V' S such as :

The restriction relation is defined by G

Definition 10. (Expansion ↑) For any G and G' (f, Aff, V S , V' S )-compatible graphs and any sub-graphs

The expansion relation is defined by : Example 3. Figure 3 offers an example of how a transformation is handled in this paper. To lighten the figure, the attributes of the edges have not been represented and will all be considered equals. Considering that L and G1 are homomorph and that the suppression of the edge 4 would not introduce any dangling edge, the transformation R can be applied to G1. The graph corresponding to the Del zone is removed and an isomorph copy of the Add zone is then added.


Cuong Le Van
email: levan@univ-paris1.fr

Anh Ngoc Nguyen

Ngoc-Minh Nguyen
email: ngocminh@depocen.org

Growth Strategy with Social Capital and Physical Capital-Theory and Evidence: the Case of Vietnam

Keywords: Social Capital, Optimal Growth JEL Classification Numbers: Z1, E2, O00

We study the impact of social capital in both simple theoretical and empirical model with the main assumption is the price of physical capital is a decreasing function of social capital. In our theoretical model, there exists a critical value such that firm will not invest in social capital if its saving is lower than the critical value and otherwise. Moreover, the output depends positively and non-linearly on the social capital. Our empirical model that captures the impact of physical capital, human capital, and social capital using the database from Survey of Small and Medium Scale Manufacturing Enterprises (SMEs) in Vietnam 2011, confirms the conclusions of the theoretical model.

Introduction

Capital is one of the major elements that support the entrepreneurs in their production and business activities. The more capital firms own, the easier they improve quantity and quality of their tools and machines, consequently the higher profitability level they could achieve. Today, in sophisticated economies, the concept "capital" does not simply stand for "physical capital", it also implies non-physical resources such as "human capital" in the form of managerial talent as well as education and training, skills of the labors working in enterprises, etc.; and "social capital" in the form of social networks, the relationships between individuals, norm, trust that have certain impact on the firm productivity.

In the recent years, there are a mass of studies on social capital as well as its e↵ects on a very wide-ranging set of socioeconomic phenomena (Durlauf 2002a;Krishna 2001). Through researches, the concept of social capital is still being discussed and developed despite a lack of an agreed upon and consistent definition. Bourdieu (1986) classifies social capital as the aggregate of the actual or potential resources which are linked to possession of a durable network of more or less institutionalized relationships of mutual acquaintance or recognition (Bourdieu 1986, p. 248) and made up of social obligations ('connections'), which are convertible, in certain conditions, into economic capital and may be institutionalized in the form of a title of nobility (Bourdieu 1986, p. 243).

The Organization for Economic Co-operation and Development (OECD) and the World Bank also have their own definitions of social capital. According to OECD, social capital is defined as "networks together with shared norm, values and understanding that facilitate co-operation within or among groups" (Cote and Healy, 2001:41). The World Bank suggests that "Social capital refers to the institutions, relationship, and norms that shape the quality and quantity of a society's social interaction. Social capital is not just the sum of the institutions which underpin a society it is the glue that holds them together."

However, the most popular definition belongs to Putnam (1993Putnam ( , 1995Putnam ( , and 2000) ) who successfully exported the concept out of academia and into the wider media and is also the most well-known theorist within the social capital paradigm.

He showed that social capital is the "features of social organization such as networks, norms, and social trust that facilitate coordination and cooperation for mutual benefit" (Putnam 1995, p. 67). Despite the diversity in definition, the widespread application of the concept verified the importance of social capital.

Through researches, authors have provided generous evidence of its influence on political, economic and social aspects (Fine 2001;Jack and Jordan 1999;Montgomery 2000).

Kurt Amen (2001) pointed out the potential trade-o↵ between sustainability of self-enforcement and the magnitude of gains from trade in social networks as an explanation. Based on an infinitely repeated multi-player prisoners' dilemma, the paper showed that inclusive social capital could combine both low enforcement cost and high gains from trade. Similarly, B.R. Routledge and J. von Amsberg (2003) used the structure of the prisoners' dilemma to describe the trade between two people and introduced a theoretical growth model in which they defined and characterized social capital as the social structure which facilitates cooperative trade as equilibrium. The key assumption of their model was that technological innovation, which drives growth, involves a reallocation of labour that a↵ects social capital. The connections between growth, labour mobility, and social capital were explored by the combination of trading model and growth model.

Besides theoretical studies, many empirical studies verified the e↵ect of social capital on economic growth. Using three measures: (i) an index of the extent of civic community; (ii) an index of various direct measures of the e↵ectiveness of regional government; and (iii) survey of citizen satisfaction with their regional governments, J.F. Helliwell and R.D. Putnam (1995) showed that there was a strong convergence of per capita incomes among the Italian regions during the 1960s and 1970s, and the more social capital a region has, the faster convergence is, as well as the higher equilibrium income level is. They also provided evidence of a sharp reversal of convergence in the period 1983 1990, indicated by increasing in the levels of real per capita GDP among regions since the regional government reforms. In the USA, there is an outstanding diversity of social capital by region (S. Iyer, M. Kitson, and B.Toh 2005). The social capital data from the Social Capital Community Benchmark Survey 2000 showed education is important for almost indicators of social capital, and ethnic diversity is associated with lower levels of social capital.

The role of social capital is also verified through cross-country empirical works. S. Knack and P. Keeper (1997) realized that trust and civic norm are stronger in countries with higher and more equal incomes, with institutions that restrain predatory actions of chief executives, and with better-educated and ethnically homogenous populations. Meanwhile, they denied the role of Putnams measure of social capital memberships in formal group that is not associated with improved economic performance. A study on a cross section of 54 European regions also confirmed that growth di↵erentials in European regions are positively related to social capital as associational activity (S. Beugelsdijk, T. Schaik 2004). In case of Africa, social capital is one of three most important initial conditions that mainly a↵ect growth by determining policy outcomes; developing countries with relatively low social capital seem more likely to have bad policy outcomes, low investment and slow growth (J. Temple 1998).

Recently, W. Stam, S.Arzlanian, and T. Elfring (2013) have conducted a metaanalysis of the link between entrepreneurs' personal networks and small firm performance to examine the role of social capital in the entrepreneurial process. The authors collected the population of 59 empirical studies (of which 10 are unpublished) that considered the relationship between social capital of entrepreneurs and small firm performance. The results showed that the relationship is positive, significant, and depends on the age of small firms, the industry and institutional contexts they operate, and on the specific network or performance measures used.

In Vietnam, there are 2 branches of research on social capital. The first branch concerns the summary and introduction of the theory of social capital. Some examples of research papers produced this branch are "Understanding the concept of social capital" (H.Q. Tran, 2006), "Social capital and Economics" (H.D. Tran, 2003 and2006), "Social capital and Development" (N. B.Nguyen, 2006), "Capital and Social capital" (Q. A.Nguyen, 2006) and "Social capital in Vietnam" (V.P. Nguyen, 2006), etc., however, these papers simply introduced and discussed the general theory, and did not prepare a specified theory for empirical research. The second branch focuses on empirical research. S.J.Appold and Q.T.Nguyen highlighted the role of social capital in small enterprises' performance. "Social capital, human capital and social networks some studies in Vietnam" (N.H. Le, 2008) discussed some of the di↵erent concepts of social capital. T.A. Nguyen and Fleur Thomse (2007) applied the concept of social capital to examine the phenomenon of land consolidation in agricultural production through the study "Kinships and land consolidation in term of social capital perspective in a North Central village".

All of the studies mentioned above demonstrated the role of social capital in the "Doi moi" (reform) period of Vietnam, it could help to promote industrialization, modernization and international integration. However, almost all of these studies were only concerned with kinship and limited their scope to the village level.

In this paper, we are able to analyze the e↵ect of social capital on productions and business activities, using the database from Survey of Small and Medium Scale Manufacturing Enterprises (SMEs) in Vietnam 2011. To the best of our knowledge, this is the first time social capital is considered as a key determinant of Vietnamese firm performance.

Our empirical analysis is guided by a theoretical model in which there exists a certain value of total saving such that upon this threshold the investment in social capital is e cient. Moreover, the more resourceful the social capital technology is and/or the lower investment in social capital is required, the slighter the value of total saving is needed. Our theoretical model also shows that the steady state of the optimal path of total saving when firm invests in social capital is always higher than the steady state of the optimal path without social capital.

Although, the theoretical model of B.R. Routledge and J. von Amsberg (2003) focused more on the social aspect of social capital as influencing cooperative behaviour, and confirmed the ability of government to increase the social capital at the expense of a less e cient allocation of labour by setting laws that reduce mo-6 Documents de travail du Centre d'Economie de la Sorbonne -2014.45 bility like a rigid seniority system or harsh unemployment scheme, the authors did not provide any empirical evidence. By contrast, we verified through our empirical results that the social capital is not really a capital in the sense we cannot produce with social capital as the only input.

The rest of this paper is organized as follows. Section 2 discusses the theoretical model, analyzed the link between social capital and growth, and showed the conditions that promote firms to invest in social capital. Section 3 presents our data and shows the empirical model as well as its results. Section 4 summarizes and concludes.

Theoretical Model

Model

We consider the Social Planner problem which consists to maximize the intertemporal utility of a representative consumer

max {ct} 1 X t=0 t u(c t )
where c t denotes her/his consumption at date t, 2 (0, 1) is the discount factor, u is a strictly concave, strictly increasing function. The constraints for this agent are, for any period t:

c t + Z t+1 + m t  F (k t , L t ) + (1 k )p t k t
m t is the amount devoted for the social capital t , Z t+1 is the amount devoted for the purchase of the physical capital k t+1 which will be used in period t + 1 to produce the consumption good of this period. The technology used for that is represented by the function F . This function is strictly concave, strictly increasing, F (0, L) = 0. For simplicity, we assume exogenous labour supply and full employment of labour. Hence, the production function does not involve labour and we will write

F (K t ) instead of F (K t , L t ).
Finally, p t is the price (in terms of consumption good) of the physical capital.

Why is the social capital useful? Assume that the consumer (who is also the producer of the consumption good) has on hand a quantity Z of savings (in terms of consumption goods). The quantity of physical capital she gets is k = Z p . The price p of the capital changes with the social capital. We assume that the price p is a decreasing function of the social capital .

We can also interpret slightly di↵erently the role of the social capital. Suppose the firm wants to get a loan to buy a quantity of physical capital k with a saving Z. Let q denote the price of the physical capital. If r is the interest rate, we then have q(1 + r)k = Z. The unit cost of the physical capital now is p = q(1 + r). In presence of the social capital, the interest r varies. Eventually it is negative (this corresponds to a subsidy from the government) and p is lower than the market price q. We assume the interest rate is a decreasing function of the social capital.

For simplicity, we assume that p = 1 and hence Z = k . We now suppose that with an amount m, the consumer will get a social capital = (m) where is a non decreasing function.

Let S t be the total saving at period t, i.e. S t = Z t+1 + m t and ✓ t is the share of this saving devoted to Z t+1 . Then

Z t+1 = ✓ t S t+1 m t = (1 ✓ t )S t+1 , ✓ t 2 [0, 1] p t = 1 t
The constraints for the consumer can be written as:

c 0 + S 1  F (k 0 ) + (1 k )p 0 k 0 c t+1 + S t+2  F (k t+1 ) + (1 k ) k t+1 t , for t 0  F ( t ✓ t S t+1 ) + (1 k )✓ t S t+1
where t = (m t ) = ((1 ✓ t )S t+1 ).

Let

H(S) = max F ( ✓S) + (1 k )✓S : ✓ 2 [0, 1], = ((1 ✓)S)
The problem of the social planner now becomes:

max 1 X t=0 t u(c t )
under the constraints

c 0 + S 1  F (k 0 ) + (1 k )p 0 k 0 c t+1 + S t+2  H(S t+1 )
2.2 When does Firm invest in Social Capital?

In this section we will show that, when the technology has a threshold then there exists a critical value S c such that if S < S c then firm will not invest in social capital and when S > S c , it will do. We assume for simplicity that k = 1 (full depreciation of the physical capital), and

(m) = 1, if m  m and (m) = a(m m) + 1, a > 0, when m > m
The parameter a measures the e ciency of the technology .

Let us consider again the function H:

H(S) = max F ( ✓S) : ✓ 2 [0, 1], = ((1 ✓)S)
First, observe that, from the Maximum Theorem, H is increasing. We can write:

H(S) = max F ( ((1 ✓)S) ✓S) : ✓ 2 [0, 1]
Let ✓(S) denote the solution to this problem. We wonder whether exists S c such that 1 Proposition 1 There exists S c > m + 1 a such that 1 ✓(S) = 0 for S < S c and 1 ✓(S) > 0 for S > S c . Moreover, when a increases then S c decreases, and when m increases then S c increases.

✓(S) = 0 if S < S c
Proof. Let G(S,✓ ) = ((1 ✓)S) ✓ and Z(S) = max{G(S,✓ ) : ✓ 2 [0, 1]}. (1) If S  m then (1 ✓)S  m for any ✓ 2 [0, 1]. In this case G(S,✓ ) = ✓ )
Z(S) = 1, ✓(S) = 1 and 1 ✓(S) = 0 (Firm will not invest in social capital).

(2) Now consider the case S > m.

• (a) ✓ 1 m S or equivalently (1 ✓)S  m. In this case, G(S,✓ ) = ✓ ) Z(S) = 1, ✓(S) = 1 and 1 ✓(S) = 0. • (b) Let 0  ✓  1 m S .
The maximum cannot be obtained with ✓(S) = 0 since if it is true then Z(S) = 0. If the solution ✓ is interior, i.e. ✓ 2 (0, 1 m S ) then we get ✓ = 1 2 (1 m S ) + 1 2aS . (This value is obtained by writing @G @✓ (S,✓ ) = 0). It is smaller than 1 m S if, and only if,

S > m + 1 a . Hence if S  m + 1 a then ✓ = 1 m S . In this case ((1 ✓)S) ✓ = ✓ = 1 m S .
It is smaller than the value we obtained in (a). Hence, 1 m S cannot be ✓(S). We can summarize at this stage that

S  m + 1 a ) Z(S) = 1, ✓(S) = 1, 1 ✓(S) = 0. Now, assume S > m+ 1 a . Again, ✓(S) > 0. If it is strictly smaller than 1 then ✓(S) = ✓ = 1 2 (1 m S ) + 1 2aS .
(This value is obtained by writing @G @✓ (S,✓ ) = 0).

11

Documents de travail du Centre d'Economie de la Sorbonne -2014. [START_REF] Woolcook | Social Capital: Implications for Development Theory, Research and Policy[END_REF] We have

G(S, ✓) = ( S) = a 4S  S + 1 a m 2 = a 4  S + 2( 1 a m) + ( 1 a m) 2 1 S
We have

0 (S) = a 4S 2  S 2 ( 1 a m) 2
Since S > m + 1 a , we have 0 (S) > 0. It is obvious that (+ 1) = +1. When S ! m + 1 a , we have ( S) ! 1 a m+1 < 1. Hence there exists a unique S c > m + 1 a such that ( S c ) = 1. For m + 1 a < S < S c we have (S) < 1. Since G(S, 1) = 1, ✓(S) cannot be less than 1. Hence ✓(S) = 1 and Z(S) = 1.

For S > S c , we have ( S) > 1 and hence Z(S) > 1 with ✓(S) = ✓ = 1 2 (1 m S ) + 1 2aS . One can easily check that ✓(S) < 1.

Observe that S > m + 1 a ) S + 1 a m > 0. We then get

@ ln( ) @a (S) = 1 a 2 a 2  1 S + 1 a m = 1 a  S ( 1 a + m) ⇥ 1 S + 1 a m > 0 @ ln( ) @ m = 2 S + 1 a m < 0
The graph of the function ( S) 1 shifts up when a increases. Hence S c , which is the unique solution to ( S) 1 = 0, decreases when a increases. Now, when m increases, the graph of ( S) 1 shifts down and S c increases.

Interpretation (i) When the social capital technology is more e cient, the critical value S c decreases. (ii) It is natural that when the threshold of the tech-nology increases, the critical value S c becomes bigger.

Let (S) = ((1 ✓(S))S).

Proposition 2 Assume F (x 2 )

x ! +1 when x ! +1. Then (S) F ( (S)✓(S)S) ! 0 when S ! +1.

Proof. When S ! +1 then ✓(S) = 1 2 (1 m S )+ 1 2aS ! 1 2 and (S) S = a((1 ✓(S))S m)+1 S ! a 2 . Hence (S) F ( (S)✓(S)S) is equivalent to aS 2F ( aS 2 2 )
and converges to 0.

Remark 1 Observe that the output is given by y = F ( k). Given k, since F is concave, the ratio F ( k)/ decreases when increases.

A function F which satisfies the assumption of Proposition 2 is F (x) = Ax ↵ , ↵ > 1 2 . The interpretation of Proposition 2 is that the role of the social capital becomes very small when Firm becomes very rich.

Growth and Social Capital

In this section, we study the contribution of the social capital to economic growth.

Assume that the function F is Cobb-Douglas, F (k) = Ak ↵ with ↵ 2 (0, 1) and the utility function u satisfies the additional assumptions that it is twice continuously di↵erentiable and satisfies the Inada condition u 0 (0) = +1.

Let S be defined by A↵ S↵ 1 = 1 . This S is the steady state to which will converge the optimal path when Firm never invests in social capital.

We have the following preliminary results. Let {S ⇤ t+1 } t 1 denote the optimal sequence of the total saving.

Lemma 1 The optimal path (S ⇤ t ) is monotonic. Proof. From what we wrote above, for t > 0, the model can be stated as:

max 1 X t=1 t u(H(S t ) S t+1 ) s.t. 8t > 0, 0  S t+1  H(S t )
Since H is increasing and @ 2 u @St@S t+1 > 0, we apply the result in [START_REF] Amir | Sensitivity analysis of multisector optimal economic dynamics[END_REF].

Lemma 2 Assume ( S) > 1. Then there exists T such that 1 ✓(S ⇤ T ) > 0, i.e. Firm will invest in social capital at date T .

Proof. If Firm never invests in Social Capital then the optimal path (S ⇤ t ) will converge to S. Since S > S c , there exists a date T with S ⇤ T > S c . From Proposition 1, Firm will invest at T in social capital.

Lemma 3 The optimal path (S ⇤ t ) cannot converge to zero.

Proof. We have the Euler equation:

8t, u 0 (H(S ⇤ t ) S ⇤ t+1 ) = u 0 (H(S ⇤ t+1 ) S ⇤ t+2 )H 0 (S ⇤ t+1 )
Let us compute H 0 (0). It is obvious that H(0) = 0. We have

H 0 (0) = lim S!0 H(S) S = lim S!0 AS ↵ 1 [ ((1 ✓(S))S)✓(S)] ↵
When S is close to zero ((1 ✓(S))S) = 1 and ✓(S) = 1. Hence lim S!0

H(S) S = +1.
Consider again the Euler equation. If S ⇤ t converges to zero, then, there exists T such that, for any t > T, H 0 (S ⇤ t+1 ) > 1. This implies

u 0 (c ⇤ t ) = u 0 (H(S ⇤ t ) S ⇤ t+1 ) > u 0 (c ⇤ t+1 ) = u 0 (H(S ⇤ t+1 ) S ⇤ t+2 ), 8t T
Equivalently, c ⇤ t+1 > c ⇤ T > 0, for any t > T . However, if S ⇤ t goes to zero then c ⇤ t goes to zero too. We get a contradiction which ends the proof.

Lemma 4 Let S denote the steady state of the optimal path of the total saving when Firm never invest in social capital, and S denote the steady state (if it exists)

of the optimal steady state of the optimal path with social capital. Then S > S.

Proof. The steady states S and S are respectively defined by F 0 ( S) = H 0 ( S) = 1 . Observe that F (S) = AS ↵ and H(S) = AS ↵ (S) ↵ . We then have:

1 = A↵ S↵ 1 = A↵ S↵ 1 [ ( S) ↵ + S ( S) ↵ 1 0 ( S)]
Since ( S) > (S c ) = 1, 0 > 0, we have S↵ 1 > S↵ 1 or equivalently S > S.

From these Lemma we obtain the main result of this paper.

Theorem 1 Assume ( S) > 1. Then there exists T such that 1 ✓(S ⇤ t ) > 0, 8t T , i.e. Firm will invest in social capital after date T . Either the optimal path will converge to infinity (growth without bound) or converges to a steady state higher than the one without social capital.

Proof. Since the optimal sequence (S ⇤ t ) is monotonic and cannot converge to zero, there exists T such that S ⇤ t > S c for any t T . The remaining claims follow Lemmas 1 -4.

We now give conditions for which the optimal paths (S ⇤ t ) will grow without bound.

Theorem 2 Assume S = (A↵ )

1 1 ↵ > m and ↵ > 1 2 .
(i) Then there exists ā such that if a > ā then S ⇤ t ! +1 when t ! +1.

(ii) And the ratio t H(St) converges to zero when t goes to infinity.

Proof. (i) The idea is to prove when a is large enough, the equation H 0 (S) = 1 has no solution, i.e., there is no steady state for the optimal (S ⇤ t ). Hence this one will converge to infinity.

We have

H(S) = A ⇣ a 4 ⌘ ↵ ✓ S + 1 a m◆ 2↵
and hence

H 0 (S) = 2↵A ⇣ a 4 ⌘ ↵ ✓ S + 1 a m◆ 2↵ 1
Since S > S, we have

H 0 (S) > 2↵A ⇣ a 4 ⌘ ↵ S m 2↵ 1
which converges to infinity when a converges to infinity.

(ii) The statement follows (i) and Proposition 2.

Comment If ↵ > 1 2 and the TFP A is su ciently large or the threshold m is small, then the economy which uses optimally the social capital, grows without bound if the social capital technology is su ciently e cient. Second, the role of the social capital diminishes when the revenue becomes very large.

Empirical Results

Data Description

Prior to the econometric investigation of how social capital a↵ects firm performance, it is useful to provide a description of dataset and some key variables used in our study.

A firm-level dataset is compiled from database of the Survey of Small and Medium Scale Manufacturing Enterprises (SMEs) in Vietnam. The survey is conducted every 2 year and in 2011 the dataset contains information of over 2500 Vietnamese SMEs from 10 provinces. The total revenue of surveyed firms was about 100 US billions. For each interviewed enterprise, two types of questionnaire were taken: (i) the main questionnaire asked about various characteristics and performance of enterprise; (ii) the labour questionnaire was to collect information on wages, work and job satisfaction of workers. One advantages of using data from Vietnamese SMEs survey is that it collects information about all aspects of business activities such as enterprise history, production characteristics, investments, assets, liabilities, credit, networks of enterprise and entrepreneurs, economic constraints and potential, etc. It is a fruitful source for study on Vietnamese SMEs performance.

In Vietnamese SMEs survey, collected information about social capital of firm are: (i) the information on social network such as the number of business contacts that the manager/entrepreneur has, who is the most important contact for firm performance, and the number of support the firm received from these contacts in last year, etc.; (ii) the information about business associations that the firm participates in such as the number of associations that the firm is their member, whether the members have to pay the fee or not, the reason why firm participated in these associations, the assessment of firms about supportability of these association.

The Vietnamese SMEs database showed that the number of firms who are participated in a formal business association is very modest, it decreased from 9.58% (equivalent to 270/2821 surveyed firms) in 2005 to 7.56% (193/2552 surveyed firms) in 2011. In fact, Vietnamese business associations do not have the key role in supporting the business activities of firms. Therefore, it is inappropriate to choose participating in associations or the number associations that the firms participated in as a proxy for social capital. In our empirical model, the total people with whom the manager/the entrepreneur has regular contact in their business activities was chosen as the explanatory variable of interest. These contacts include business people, bank o cials (both formal and informal creditors), and politicians and civil servants, etc.

Empirical Specification

In our empirical model, we suggest that social capital has an e↵ect on revenue of firms using the following regression specification: lnRevenue = 0 + 1 lnP hysical + 2 lnLabour + 3 lnP roLabour + 4 T otalContact where lnRevenue measured as the logarithm of the total revenue of firm in the end of 2010.

We include Total Assets (lnPhysical), Total Labour Force (lnLabour), and Number of Professional Employer (LnProLabour) as standard control variables.

All dataset are lagged one year, and computed in their log value. LnPhysical is proxy variable for physical capital, LnLabour and LnProLabour are proxy variable for human capital. Professional Employer is covered to estimate the impact of labour quality on firm performance.

The proxy variable for e↵ect of social capital is TotalContact that indicates the number of contact a firm has.

As the theoretical model implied, there exists a threshold S c of total saving such that if the total saving of firm is smaller than this threshold S c , the investment in social capital will be ine cient. In addition, the steady state in case of investing in social capital is always higher than the one without social capital.

In empirical model, we analyse the impact of social capital and make an e↵ort to prove that social capital only impacts on the performance of certain firms whose revenue is larger than a critical value. Since proficient social capital also requires a fixed cost, if the firm's saving is not large enough, it could not invest in social capital, or the social capital that it achieves could not support its performance.

Simultaneously, it should be noted that the higher revenue a firm reaches, the larger saving it could make, as a result, only these firms could be employ social capital as a determinant of its growth.

In order to examine whether the link between social capital and firm revenue is nonlinear as we expected or not, as well as to detect the threshold, we regress the log value of firm revenue on the proxy variables of social capital and the control variables, using OLS regression and Quantile regression methods.

Quantile regression is a type of regression analysis used in statistics and econometrics that intended to estimate, and conduct inference about, conditional quantile functions. Whereas the method of least squares results in estimates that ap-proximate the conditional mean of the response variable given certain values of the predictor variables, quantile regression methods o↵er a mechanism for estimating models for the conditional median function, and the full range of other conditional quantile functions. By supplementing the estimation of conditional mean functions with techniques for estimating an entire family of conditional quantile functions, quantile regression is capable of providing a more complete statistical analysis of the stochastic relationships among random variables. Based on quantile regression, we could detect a critical value such that the model is significant in case of all observations that are upper the critical value and otherwise.

Empirical Results

In our empirical model, we postulate that the revenue of firm is determined by the elements listed in the censored regression. The empirical model predicts that social capital a↵ects on firm performance in a certain range of revenue.

In tables 1 and 2, we introduce the results of OLS and Quantile regression method at several levels of firm revenue, i.e., column QR(0.01) shows results using quantile regression method which estimates the e↵ect of the change of conditioning variables on the position of 1% level of quantile of the distribution of firm revenue (the similar explanation for the other columns from QR(0.018) to QR(0.72)).

As can be seen in the table 1, in line with other standard control variables, the number of contacts in business activities normally has a a rmative impact on revenue of firm (indeed, the estimate of TotalContact variable is positive in all regressions). In OLS regression, the estimate of TotalContact is positive, and significant at 1% level. Generally, quantile regression is more robust to outliers than OLS regression, and in case of social capital and revenue of firm, the me-Based on above empirical results, we could see the fluctuation of the coecient of TotalContact across each quantile level and conclude that firm revenue a rmatively and non-linearly depends on the social capital.

Conclusion

This paper has explored the potential impact of the number of contacts in business activities on firm performance, how and in which conditions firms should invest in social capital in generally, and social network in particularly. The empirical results were guided by a theoretical model that analyses the contribution of social capital to economic growth and allows us to make progress along two lines. First, we have showed if the saving is not large enough, or equivalently if the revenue is very modest, it is not optimal for firms in social capital is not e cient. Second, we have found out that social capital only has a certain e↵ect on revenue of firm; it cannot take over from physical capital or human capital in order to produce goods (i.e., by itself, social capital is not an input).

From the empirical results, we make two observations: (1) The elasticities for the physical capital and labour are respectively around 0.3 and 0.

  , and 1 ✓(S) > 0 if S > S c . 10 Documents de travail du Centre d'Economie de la Sorbonne -2014.45 It is obvious that ✓(S) actually solves the problem max{ ((1 ✓)S)✓ : ✓ 2 [0, 1]

13

  Documents de travail du Centre d'Economie de la Sorbonne -2014.45

  Figure 1: The Quantile graphs of coe cients

Table 1 :

 1 Results of social capital and firm performance with OLS and quantile regressions The table reports the results of estimation equation (1) corresponding to each specified threshold. Robust errors are in parentheses underneath coe cient estimates. ***, **, * indicate 1%, 5%, and 10% level of significance, respectively.

		OLS	QR(0.01) QR(0.018) QR(0.02) QR(0.05)
	LnPhysical	0.333*** 0.344*** 0.328***	0.337*** 0.311***
		(0.000)	(0.002)	(0.000)	(0.000)	(0.000)
	Labour	0.664*** 0.818*** 0.752***	0.750*** 0.659***
		(0.000)	(0.000)	(0.000)	(0.000)	(0.000)
	LnProLabour	0.238*** -0.009	0.081	0.132	0.210*
		(0.000)	(0.974)	(0.654)	(0.380)	(0.090)
	TotalContact	0.130*** 0.231	0.249	0.241*	0.206*
		(0.001)	(0.341)	(0.111)	(0.063)	(0.054)
	Constant	3.099*** 0.855	1.261***	1.203*** 1.975***
		(0.000)	(0.211)	(0.004)	(0.001)	(0.000)
	Pseudo R2/ R2 0.7547	0.4220	0.4292	0.4299	0.4477
	Obs	1408	1408	1408	1408	1408
	Note:

Table 2 :

 2 Results of social capital and firm performance with OLS and quantile regressions (cont) The table reports the results of estimation equation (1) corresponding to each specified threshold. Robust errors are in parentheses underneath coe cient estimates. ***, **, * indicate 1%, 5%, and 10% level of significance, respectively.

		QR(0.10) QR(0.25) QR(0.50) QR(0.71) QR(0.72)
	LnPhysical	0.291*** 0.273*** 0.343*** 0.340
		(0.000)	(0.000)	(0.000)	(0.000)	(0.000)
	Labour	0.595*** 0.615*** 0.648*** 0.677*** 0.679***
		(0.000)	(0.000)	(0.000)	(0.000)	(0.000)
	LnProLabour	0.323*** 0.343*** 0.234*** 0.199*** 0.206***
		(0.000)	(0.000)	(0.000)	(0.000)	(0.000)
	TotalContact	0.179*** 0.160*** 0.118*** 0.084*	0.081
		(0.002)	(0.001)	(0.009)	(0.069)	(0.102)
	Constant	2.465*** 3.041*** 3.158*** 3.440*** 3.487***
		(0.000)	(0.000)	(0.000)	(0.000)	(0.000)
	Pseudo R2/ R2 0.4656	0.4895	0.5194	0.5362	0.5364
	Obs	1408	1408	1408	1408	1408
	Note:

Documents de travail du Centre d'Economie de la Sorbonne -2014.45

dian estimate is not similar to the OLS point estimate. The di↵erence between median and mean estimates could be clearly seen in the figure 1, the coe cient of TotalContact in case of OLS method is slightly higher than in case of QR(0.5) -Quantile Regression method at median level of firm revenue.

When we use quantile regression method and separate the dataset into 3 groups as (i) the 1.8% of lowest revenue firms, (ii) the medium revenue firms (from 1.9 71%), and (iii) the 28% of highest revenue firms, we could receive di↵erent pvalues of TotalContact (as well as p-values of the other variables) for each group.

In quantile regressions, the firms are arranged in ascending order of their revenue.

For 1.8% of firms that have lowest revenue and 28% of ones that have highest revenue, the estimate of TotalContact is insignificant at 10% level (p-values of TotalContact in case of QR(0.018) and QR(0.72) are 0.341 and 0.102, respectively).

By contrast, the estimate is significant in case of 70% of firms whose revenue is at medium level from QR(0.2) to QR(0.71).

In case of 1.8% of firms that have lowest revenue, it could be said that their revenues are not large enough to saving and invest in e cient social capital or e cient business contacts. This is appropriate with the results of our theoretical model. However, it is clearly that the proportion of these firms is very small. The role of social capital in Vietnamese SMEs performance is considerable so that a very small firm should use social capital to improve their performance.

The insignificant estimate of social capital in case of firms that have highest revenue provides evidence that social capital only has a certain e↵ect on firm performance. In order to increase their revenue as well as their performance, firms cannot only concern in their social capital, they also need to improve other types of capital such as physical capital, human capital, etc.