Gérard Ferrand
email: gerard.ferrand@lifo.univ-orleans.fr

Willy Lesaint
email: willy.lesaint@lifo.univ-orleans.fr

Alexandre Tessier
email: alexandre.tessier@lifo.univ-orleans.fr

Theoretical Foundations of Value Withdrawal Explanations for Domain Reduction

Solvers on finite domains use local consistency notions to remove values from the domains. This paper defines value withdrawal explanations. Domain reduction is formalized with chaotic iterations of monotonic operators. To each operator is associated its dual which will be described by a set of rules. For classical consistency notions, there exists a natural such system of rules. They express value removals as consequences of other value removals. The linking of these rules inductively defines proof trees. Such a proof tree clearly explains the removal of a value (the root of the tree). Explanations can be considered as the essence of domain reduction.

Introduction

Constraint programming [START_REF] Marriott | Programming with Constraints: An Introduction[END_REF] is an important programming paradigm of the last years. It combines declarativity of relational style and efficiency of constraint solvers which are implemented for specific domains. We are interested here in the constraints over finite domains [START_REF] Tsang | Foundations of Constraint Satisfaction[END_REF][START_REF] Van Hentenryck | Constraint Satisfaction in Logic Programming[END_REF]. A constraint is a relation between variables. In finite domains, each variable can only have a finite set of possible values. The aim of constraint programming is to prove satisfiability or to find one or all the solutions of a Constraint Satisfaction Problem (a set of variables with their domains and a set of constraints). In theory, solutions can be obtained by an enumeration of all the combination of values for the variables of the problem (the labeling method). But in practice this method is very expensive, so one prefers to interlace the labeling with domain reduction stages. Domain reduction consists in eliminating some values from variable domains which cannot belong to a solution according to the constraints. In general, these values are characterized by a notion of local consistency. The labeling can be seen as additional constraints. This paper only deals with the domain reduction part.

Several works [START_REF] Fages | A reactive constraint logic programming scheme[END_REF][START_REF] Benhamou | Heterogeneous constraint solving[END_REF][START_REF] Apt | The role of commutativity in constraint propagation algorithms[END_REF] formalize domain reduction thanks to operators (these operators reduce the variable domains). In practice, they are applied according to different strategies. Chaotic iterations [START_REF] Cousot | Automatic synthesis of optimal invariant assertions mathematical foundation[END_REF] have been used in order to describe domain reduction from a theoretical general point of view. It ensures confluence, that is to obtain the same reduced domain whatever the order of application of the operators is. Domain reduction can then be described with notions of fix-points and closures.

From another point of view, constraint community is also interested in explanations (or nogoods). The notions of explanations seem to be an interesting answer to constraint retraction problems: they have been used for dynamic constraint satisfaction problems, over-constrained problems, dynamic backtracking, . . . . An explanation is roughly a set of constraints responsible for a value withdrawal: domain reduction by this set of constraints, or any super-set of it, will always remove this value. There exist other applications of the explanations, among others debugging applications. See http://www.e-constraints.net for more details.

This paper is an attempt to lay a theoretical foundation of value withdrawal explanations in the above-mentioned framework of chaotic iteration. It presents the first results obtained by the authors in the RNTL project OADymPPaC (More details at http://contraintes.inria.fr/OADymPPaC/).

A first notion of explanation is defined as a set of operators (from which one can find the set of constraints responsible for the value removal). A monotonic operator can always be defined by a set of rules (in the sense of the inductive definitions of Aczel [START_REF] Aczel | An introduction to inductive definitions[END_REF]). A natural such system exists but is not computed, it is just a theoretical tool to define explanations in our theoretical model. Rules express value removals as consequences of other value removals. So, a more precise notion of explanation can be obtained: the linking of these rules allows to inductively define proof trees. Such a proof tree clearly explains the removal of a value (the root of the tree) by the solver and then, it is called an explanation for this value withdrawal. It is important to note that the unique role of a solver is to remove values and that our explanations are proof of these removals, that is explanations are the essence of domain reduction.

The paper will be illustrated by examples in GNU-Prolog [START_REF] Codognet | Compiling constraints in clp(fd)[END_REF]. More examples, more detailled proofs of lemmas and some basic notions about monotonic operators, closures, rules and proof trees can be found in [START_REF] Ferrand | Theoretical foundations of value withdrawal explanations in constraints solving by domain reduction[END_REF]. The paper is organized as follows. Section 2 gives some notations and definitions for Constraint Satisfaction Problems in terms of rules in a set theoretical style. Section 3 recalls in our formalism a model for domain reduction based on local consistency operators and chaotic iterations. Section 4 associates deduction rules with this model. Section 5 uses deduction rules in order to build explanations.

Preliminaries

We recall the definition of a constraint satisfaction problem as in [START_REF] Tsang | Foundations of Constraint Satisfaction[END_REF]. The notations used are natural to express basic notions of constraints involving only some subsets of the set of all variables.

Here we only consider the framework of domain reduction as in [START_REF] Benhamou | Heterogeneous constraint solving[END_REF][START_REF] Codognet | Compiling constraints in clp(fd)[END_REF][START_REF] Van Hentenryck | Constraint Satisfaction in Logic Programming[END_REF].

A Constraint Satisfaction Problem (CSP) is made of two parts, the syntactic part:

a finite set of variable symbols (variables in short) V ; -a finite set of constraint symbols (constraints in short) C; -a function var : C → P(V ), which associates with each constraint symbol the set of variables of the constraint; and a semantic part for which preliminaries are needed. We are going to consider various families f = (f i ) i∈I . Such a family can be identified with the function i → f i , itself identified with the set {(i, f i ) | i ∈ I}. We consider a family (D x ) x∈V where each D x is a finite non empty set.

In order to have simple and uniform definitions of monotonic operators on a power-set, we use a set which is similar to an Herbrand base in logic programming: we define the global domain by D = x∈V ({x} × D x ). We consider subsets d of D. We denote by d| W the restriction of a set d ⊆ D to a set of variables

W ⊆ V , that is, d| W = {(x, e) ∈ d | x ∈ W }.
We use the same notations for the tuples (valuations). A global tuple t is a particular d such that each variable appears only once: t ⊆ D and ∀x ∈ V, ∃e ∈ D x , t| {x} = {(x, e)}. A tuple t on W ⊆ V , is defined by t ⊆ D| W and ∀x ∈ W, ∃e ∈ D x , t| {x} = {(x, e)}. So a global tuple is a tuple on V .

Then the semantic part of the CSP is defined by:

the family (D x ) x∈V (D x is the domain of the variable x); -a family (T c ) c∈C such that: for each c ∈ C, T c is a set of tuples on var(c) (T c is the set of solutions of c).

A global tuple t is a solution to the CSP if ∀c ∈ C, t| var(c) ∈ T c . Let d ⊆ D, for x ∈ V , we define d x = {e ∈ D x | (x, e) ∈ d}. To give any d ⊆ D amounts to give a family (d x ) x∈V with d x ⊆ D x . So we can note: ∀x ∈ V , d| {x} = {x} × d x ; d = x∈V d| {x} ; for d, d ′ ⊆ D, (d ⊆ d ′ ⇔ ∀x ∈ V, d x ⊆ d ′ x );
Example 1. We introduce a CSP which will be used in several examples throughout the paper. Let us consider the CSP defined by:

-V = {x, y, z}; -C = {x < y, y < z, z < x}; -var(x < y) = {x, y}, var(y < z) = {y, z} and var(z < x) = {x, z}; -D = {(x, 0), (x, 1), (x, 2), (y, 0), (y, 1), (y, 2), (z, 0), (z, 1), (z, 2)}; -T x<y = {{(x, 0), (y, 1)}, {(x, 0), (y, 2)}, {(x, 1), (y, 2)}}, T y<z = {{(y, 0), (z, 1)}, {(y, 0), (z, 2)}, {(y, 1), (z, 2)}}, T z<x = {{(x, 1), (z, 0)}, {(x, 2), (z, 0)}, {(x, 2), (z, 1)}};

To reduce the domains of variable means to replace each D x by a subset d x of D x without losing any solution. Such d x is called a domain of the variable x and d = x∈V ({x} × d x ) is called a domain. D x is merely the greatest domain of x.

Here, we focus on the reduction stage. Intuitively, we want all the solutions to remain in the reduced domain and we attempt to approximate the smallest domain containing all these solutions. So this domain must be an "approximation" of the solutions according to the subset ordering ⊆. Next section describes a model for the computation of such approximations.

A way to compute an approximation of the solutions is to associate with the constraints a notion of local consistency which is expressed here by some local consistency operators. The type of such an operator is (W in , W out ) with W in , W out ⊆ V . A local consistency operator is applied to the whole domain. But in fact, it eliminates from the domains of W out some values which are inconsistent with respect to the domains of W in and the local consistency notion used. We introduce the use of local consistency operators by the following examples.

Example 2. Arc consistency is a simple and particular case of hyper-arc consistency. Let c ∈ C with var(c) = {x, y} and d ⊆ D. The property of arc consistency for d is: [START_REF] Aczel | An introduction to inductive definitions[END_REF]

∀e ∈ d x , ∃f ∈ d y , {(x, e), (y, f )} ∈ T c ; (2) ∀f ∈ d y , ∃e ∈ d x , {(x, e), (y, f )} ∈ T c .
We can associate with (1) the operator r defined by: r

(d) = D| V \{x} ∪{(x, e) ∈ D | ∃(y, f ) ∈ d, {(x, e), (y, f )} ∈ T c }. It is obvious that the property of arc consistency is equivalent to d ⊆ r(d).
Here, W out = {x} and we can take W in = {y}. There exist different possibilities to choose r, but for reasons which will appear later this one is the most convenient. An operator associated with (2) can be defined in the same way.

This example motivates the following definition.

Definition 1. A local consistency operator of type (W in , W out ), W in , W out ⊆ V , is a monotonic function r : P(D) → P(D) such that: ∀d ⊆ D, -r(d)| V \Wout = D| V \Wout , -r(d) = r(d| Win ).
We can note that r(d)| V \Wout does not depend neither on d, nor on r and that r(d)| Wout only depends on d| Win .

Definition 2. We say a domain

d is r-consistent if d ⊆ r(d), that is, d| Wout ⊆ r(d)| Wout .
The solver is described by a set of such operators associated with the constraints of the CSP. We can choose more or less accurate local consistency operators for each constraint (in general, the more accurate they are, the more expensive is the computation). Any notion of local consistency in the framework of domain reduction may be expressed by such operators. Reduction operators are associated with these operators in order to reduce the domains.

Definition 3. The reduction operator associated with the local consistency operator r is the monotonic and contracting function d → d ∩ r(d).

All the solvers proceeding by domain reduction may be formalized by operators with this form. GNU-Prolog associates with each constraint as many operators as variables in the constraint (W out is always a singleton).

Example 3. In GNU-Prolog, these operators are written x in r [START_REF] Codognet | Compiling constraints in clp(fd)[END_REF], where r is a range dependent on the domains of a set of variables. GNU-Prolog has two kinds of local consistency: hyper-arc consistency and partial hyper-arc consistency. The constraint x #= y (partial arc consistency) is implemented by two GNU-Prolog rules x in min(y)..max(y) and y in min(x)..max(x). The rule x in min(y)..max(y) uses the local consistency operator of type ({y}, {x}) defined by r(d)| {x} = {(x, e) | min(d y ) ≤ e ≤ max(d y )} where min(d y ), max(d y ) are respectively the smallest and the greatest value in the domain of y. The reduction operator associated with this local consistency operator computes the intersection with the domain of x and is applied by activation of the rule.

The local consistency operators we use must not remove solutions from the CSP. This is formalized in [START_REF] Ferrand | Theoretical foundations of value withdrawal explanations in constraints solving by domain reduction[END_REF] by notions of correct operators that are not essential here.

The solver applies the reduction operators one by one replacing the domain with the one it computes. The computation stops when a domain of a variable becomes empty (in this case, there is no solution), or when the reduction operators cannot reduce the domain anymore (a common fix-point is reached).

From now on, we denote by R a set of local consistency operators (the set of local consistency operators associated with the constraints of the CSP). A common fix-point of the reduction operators associated with R starting from a domain d is a domain

d ′ ⊆ d such that ∀r ∈ R, d ′ = d ′ ∩ r(d ′ ), that is ∀r ∈ R, d ′ ⊆ r(d ′ ). The greatest common fix-point is the greatest d ′ ⊆ d such that ∀r ∈ R, d ′ is r-consistent.
To be more precise:

Definition 4. The downward closure of d by R, denoted by CL ↓ (d, R), is the greatest d ′ ⊆ D such that d ′ ⊆ d and ∀r ∈ R, d ′ ⊆ r(d ′ ). Note that CL ↓ (d, ∅) = d and CL ↓ (d, R) ⊆ CL ↓ (d, R ′ ) if R ′ ⊆ R.
The downward closure is the most accurate set which can be computed using a set of (correct) local consistency operators in the framework of domain reduction. CL ↓ (d, R) can be computed by chaotic iterations introduced for this aim in [START_REF] Fages | A reactive constraint logic programming scheme[END_REF]. The following definition is taken up to Apt [START_REF] Apt | The essence of constraint propagation[END_REF].

Definition 5. A run is an infinite sequence of operators of R, that is, a run associates with each i ∈ IN (i ≥ 1) an element of R denoted by r i . A run is fair if each r ∈ R appears in it infinitely often, that is, ∀r ∈ R, {i | r = r i } is infinite.
The downward iteration of the set of local consistency operators R from the domain d ⊆ D with respect to the run r 1 , r 2 , . . . is the infinite sequence d 0 , d 1 , d 2 , . . . inductively defined by:

d 0 = d; for each i ∈ IN, d i+1 = d i ∩ r i+1 (d i ). Its limit is ∩ i∈IN d i .
A chaotic iteration is an iteration with respect to a fair run.

Note that an iteration starts from a domain d which can be different from D. This is more general and convenient for a lot of applications (dynamic aspects of constraint programming for example).

The next well-known result of confluence [START_REF] Cousot | Automatic synthesis of optimal invariant assertions mathematical foundation[END_REF][START_REF] Fages | A reactive constraint logic programming scheme[END_REF] ensures that any chaotic iteration reaches the closure. Note that, since ⊆ is a well-founded ordering (i.e.

D is a finite set), every iteration from d ⊆ D is stationary, that is, ∃i ∈ IN, ∀j ≥ i, d j = d i .
Lemma 1. The limit of every chaotic iteration of the set of local consistency operators R from d ⊆ D is the downward closure of d by R.

Proof. Let d 0 , d 1 , d 2 , . . . be a chaotic iteration of R from d with respect to r 1 , r 2 , . . .. Let d ω be the limit of the chaotic iteration.

[CL

↓ (d, R) ⊆ d ω ] For each i, CL ↓ (d, R) ⊆ d i , by induction: CL ↓ (d, R) ⊆ d 0 = d. Assume CL ↓ (d, R) ⊆ d i , CL ↓ (d, R) ⊆ r i+1 (CL ↓ (d, R)) ⊆ r i+1 (d i ) by monotonicity. Thus, CL ↓ (d, R) ⊆ d i ∩ r i+1 (d i ) = d i+1 . [d ω ⊆ CL ↓ (d, R)] There exists k ∈ IN such that d ω = d k because ⊆ is a well-founded ordering. The run is fair, hence d k is a common fix-point of the set of reduction operators associated with R, thus d k ⊆ CL ↓ (d, R) (the greatest common fix-point).
Infinite runs and fairness are a convenient theoretical notion to state the previous lemma. Every chaotic iteration is stationary, so in practice the computation ends when a common fix-point is reached. Moreover, implementations of solvers use various strategies in order to determine the order of invocation of the operators. These strategies are used to optimize the computation, but this is out of the scope of this paper.

In practice, when a domain of variable becomes empty, we know that there is no solution, so an optimization consists in stopping the computation before the closure is reached. In this case, we say that we have a failure iteration.

We have recalled here a model of the operational semantics for the solvers on finite domains using domain reduction. This model is language independent and general enough to be applied to different solvers. Furthermore it allows us to define a notion of explanation.

Sometimes, when the domain of a variable becomes empty or when a value is simply removed from a domain of a variable, the user wants an explanation of this phenomenon [START_REF] Jussien | Relaxation de Contraintes pour les Problèmes Dynamiques[END_REF]. The case of failure is the particular case where all the values are removed. It is the reason why the basic event here is a value withdrawal. Let us consider a chaotic iteration, and let us assume that at a step a value is removed from the domain of a variable. In general, all the operators used from the beginning of the iteration are not necessary to explain the value withdrawal. It is possible to explain the value withdrawal by a subset of these operators such that every chaotic iteration using this subset of operators removes the considered value.

We can define an explanation set [START_REF] Jussien | Relaxation de Contraintes pour les Problèmes Dynamiques[END_REF], which is a set of operators responsible for a value withdrawal during a computation starting from a fixed domain d. Definition 6. Let h ∈ D and d ⊆ D. We call explanation set for h wrt d a set of local consistency operators d,E). So an explanation set E is independent of any chaotic iteration with respect to R in the sense of: if the explanation set is responsible for a value withdrawal then whatever the chaotic iteration used is, the value will always be removed. Note that when h ∈ d, then the empty set is an explanation set for h.

E ⊆ R such that h ∈ CL ↓ (d, E). Since E ⊆ R, CL ↓ (d, R) ⊆ CL ↓ (
For some applications (as debugging for example), we need a notion of explanation which is finer than explanation set. We are interested in the dependency between the values and the operators. This will be the purpose of section 5, but before we need to associate systems of rules with the operators.

Deduction rules

We are interested by the value withdrawal, that is, when a value is not in a domain but in its complementary. So we consider this complementary and the "duals" of the local consistency operators. In this way, at the same time we reduce the domain, we build its complementary. We associate rules systems (inductive definition [START_REF] Aczel | An introduction to inductive definitions[END_REF]) with these dual operators. These rules will be the constructors of the explanations.

First we need some notations. Let d = D \ d. In order to help the understanding, we always use the notation d for a subset of D if intuitively it denotes the complementary of a domain. Definition 7. Let r be an operator, we denote by r the dual of r defined by: ∀d ⊆ D, r(d) = r(d).

We need to consider sets of such operators as for local consistency operators. Let R = { r | r ∈ R}. The upward closure of d by R, denoted by CL ↑ (d, R) exists and is the least d ′ such that d ⊆ d ′ and ∀r ∈ R, r(d ′ ) ⊆ d ′ (see [START_REF] Ferrand | Theoretical foundations of value withdrawal explanations in constraints solving by domain reduction[END_REF]).

Next lemma establishes the correspondence between downward closure of local consistency operators and upward closure of their duals.

Lemma 2. CL ↑ (d, R) = CL ↓ (d, R). Proof. CL ↑ (d, R) = min{d ′ | d ⊆ d ′ , ∀ r ∈ R, r(d ′ ) ⊆ d ′ } = min{d ′ | d ⊆ d ′ , ∀r ∈ R, d ′ ⊆ r(d ′ )} = max{d ′ | d ′ ⊆ d, ∀r ∈ R, d ′ ⊆ r(d ′ )}
In the same way we defined a downward iteration of a set of operators from a domain, we define an upward iteration of a set of dual operators.

The upward iteration of R from d ⊆ D with respect to r 1 , r 2 , . . . is the infinite sequence δ 0 , δ 1 , δ 2 , . . . inductively defined by: δ 0 = d and δ i+1 = δ i ∪ r i+1 (δ i ).

We can rewrite the second item: δ i+1 = δ i ∪ r i+1 (δ i ), that is, we add to δ i the elements of δ i removed by r i+1 .

If we consider the downward iteration from d with respect to r 1 , r 2 , . . ., then the link between the downward and the upward iteration clearly appears by noting that:

δ i ∪ r i+1 (δ i ) = d i ∩ r i+1 (d i ), that is, δ i+1 = d i+1 , and ∪ j∈IN δ j = CL ↑ (d, R) = CL ↓ (d, R) = ∩ j∈IN d i .
We have shown two points of view for the reduction of a domain d with respect to a run r 1 , r 2 , . . .. In the previous section, we considered the reduced domain, but in this section, we consider the complementary of this reduced domain, that is, the set of elements removed of the domain. Now, we associate rules in the sense of [START_REF] Aczel | An introduction to inductive definitions[END_REF] with these dual operators. These rules are natural to build the complementary of a domain and well suited to provide proof trees.

Definition 8. A deduction rule of type (W in , W out ) is a rule h ← B such that h ∈ D| Wout and B ⊆ D| Win .
A deduction rule h ← B can be understood as follow: if all the elements of B are removed from the domain, then h does not participate in any solution of the CSP and can be removed.

For each operator r ∈ R of type (W in , W out ), we denote by R r a set of deduction rules of type (W in , W out ) which defines r, that is, R r is such that:

r(d) = {h ∈ D | ∃B ⊆ d, h ← B ∈ R r }.
For each operator, this set of deduction rules exists [START_REF] Ferrand | Theoretical foundations of value withdrawal explanations in constraints solving by domain reduction[END_REF]. There exists possibly many such sets, but in general one is natural in our context.

We provide an illustration of this model for arc consistency. Examples for partial-arc consistency and hyper-arc consistency are provided in [START_REF] Ferrand | Theoretical foundations of value withdrawal explanations in constraints solving by domain reduction[END_REF].

Value withdrawal explanations

We use the deduction rules in order to build proof trees [START_REF] Aczel | An introduction to inductive definitions[END_REF]. We consider the set of all the deduction rules for all the local consistency operators of R: let

R = ∪ r∈R R r .
We denote by cons(h, T ) the tree defined by: h is the label of its root and T the set of its sub-trees. The label of the root of a tree t is denoted by root(t). Let us recall the definition of a proof tree for a set of rules. Definition 9. A proof tree cons(h, T ) with respect to R is inductively defined by: h ← {root(t) | t ∈ T } ∈ R and T is a set of proof trees with respect to R. Our set of deduction rules is not complete: we must take the initial domain into account. If we compute a downward closure from the global domain D, then its complementary is the empty set (in this case, R is complete). But if we compute a downward closure from a domain d ⊂ D, then its dual upward closure starts with d. We need to add facts (rules with an empty body) in order to directly deduce the elements of d: let R d = {h ← ∅ | h ∈ d}. The next theorem ensures that, with this new set of deduction rules, we can build proof trees for each element of CL ↑ (d, R).

Theorem 1. CL ↓ (d, R) is the set of the roots of proof trees with respect to R ∪ R d . Proof. Let E the set of the roots of proof trees wrt to R ∪ R d . E ⊆ min{d ′ | d ⊆ d ′ , ∀ r ∈ R, r(d ′ ) ⊆ d ′ } by induction on proof trees. It is easy to check that d ⊆ E and r(E) ⊆ E. Hence, min{d ′ | d ⊆ d ′ , ∀ r ∈ R, r(d ′ ) ⊆ d ′ } ⊆ E.
Example 6. Let us consider the CSP defined in example 1. Six local consistency operators are associated with the constraints of the CSP: r 1 of type ({y}, {x}) and r 2 of type ({x}, {y}) for x < y r 3 of type ({z}, {y}) and r 4 of type ({y}, {z}) for y < z r 5 of type ({z}, {x}) and r 6 of type ({x}, {z}) for z < x

Figure 1 shows three different proof trees rooted by (x, 0). For example, the first one says: (x, 0) may be removed from the domain if (y, 1) and (y, 2) may be removed from the domain (thanks to a deduction rule of R r2 ). (y, 1) may be removed from the domain if (z, 2) may be removed from the domain (thanks to R r4 ). (y, 2) and (z, 2) may be removed from the domain without any condition (thanks to R r4 and R r6 ).

Each deduction rule used in a proof tree comes from a packet of deduction rules, either a packet R r defining a local consistency operator r, or the packet R d . We can associate sets of local consistency operators with a proof tree. Definition 10. Let t be a proof tree. A set of local consistency operators associated with t is a set X such that, for each node of t labeled by h ∈ d, if B is the set of labels of its children then there exists r ∈ X, h ← B ∈ R r .

Note that there exist several sets associated with a proof tree because, for example, a deduction rule may appear in several packets or each super-set is also convenient. It is important to recall that the root of a proof tree does not belong to the closure of d by the set of local consistency operators. So there exists an explanation set (definition 6) for this value. The biggest one is the whole set R of local consistency operators, but we prove in the next theorem that the sets defined above are also explanation sets for this value. In fact, such a set of operators is responsible for the withdrawal of the root of the tree: Theorem 2. If t is a proof tree, then a set of local consistency operators associated with t is an explanation set for root(t).

Proof. by theorem 1 and definition 6.

We proved that we can find explanation sets in proof trees. So it remains to find proof trees. We are going to show that some proof trees are "computed" by chaotic iterations, but it is important to note that some proof trees do not correspond to any chaotic iteration. We are interested in the proof trees which can be deduced from a computation.

Example 7. The first and third proof trees of figure 1 correspond to some chaotic iterations. But the second one does not correspond to any (because (x, 0) could not disappear twice).

From now on, we consider a fixed chaotic iteration d = d 0 , d 1 , . . . , d i , . . . of R with respect to the run r 1 , r 2 , . . .. In this context we can associate with each h ∈ CL ↓ (d, R), one and only one integer i ≥ 0. This integer is the step in the chaotic iteration where h is removed from the domain. Definition 11. Let h ∈ CL ↓ (d, R). We denote by step(h), either the integer i ≥ 1 such that h ∈ d i-1 \ d i , or the integer 0 if h ∈ d = d 0 .

A chaotic iteration can be seen as the incrementaly construction of proof trees. We define the set of proof trees S i which can be built at a step i ∈ IN. More formally, the family (S i ) i∈IN is defined by: S

0 = {cons(h, ∅) | h ∈ d}; S i+1 = S i ∪ {cons(h, T ) | h ∈ d i , T ⊆ S i , h ← {root(t) | t ∈ T } ∈ R r i+1 }.
We prove that the roots of the trees of S i are exactly the elements removed from the domain at a step j ≤ i of the chaotic iteration.

Lemma 3. {root(t) | t ∈ S i } = d i . So, {root(t) | t ∈ ∪ i∈IN S i } = CL ↓ (d, R). Proof. {root(t) | t ∈ S i } = d i by induction on i. {root(t) | t ∈ ∪ i∈IN S i } = ∪ i∈IN {root(t) | t ∈ S i } = ∪ i∈IN d i = ∩ i∈IN d i = CL ↓ (d, R)
This lemma is important because it ensures that, whatever the chaotic iteration used is, we can incrementaly compute the proof trees for each element which is not in the closure. All proof trees do not correspond to a chaotic iteration, but for each one, there exists a proof tree with the same root which correspond to the chaotic iteration. Consequently, we will call explanation a proof tree and computed explanation a proof tree of ∪ i∈IN S i .

Let t ∈ ∪ i∈IN S i , according to definition 10 and theorem 2, the set of local consistency operators {r step((x,e)) | (x, e) has an occurrence in t and step((x, e)) > 0} is an explanation set for root(t). From a theoretical point of view, the fundamental object is the explanation t.

Conclusion

This paper has laid theoretical foundations of value withdrawal explanations in the framework of chaotic iteration. We were interested in domain reduction for finite domains. But this work could be extended to interval constraints [START_REF] Benhamou | Applying interval arithmetic to real, integer and boolean constraints[END_REF]: our approach is general enough for any notion of local consistency and the domain is a (finite) set of floating point values. Furthermore, labeling could be included in this framework if we consider it as constraint addition. But dynamic aspects are not in the scope of this paper, the focus is on pure domain reduction by chaotic iterations.

Domain reduction can be considered as a particular case of constraint reduction [START_REF] Apt | The essence of constraint propagation[END_REF] because domains can be seen as unary constraints. This work could also be extended to constraint reduction. To extend D, it would be enough to consider the set of all possible tuples for the constraints of the CSP. The operators should then reduce this set, that is remove tuples from the constraints.

First, we have shown how each solver based on some notions of local consistency can be described in our formalism in term of local consistency operators. In systems like GNU-Prolog, these operators correspond to the implementation of the solver (the X in r scheme [START_REF] Codognet | Compiling constraints in clp(fd)[END_REF][START_REF] Deville | Constraint processing in cc[END_REF]). The associated reduction operators reduce the domains of variables according to a constraint and a notion of local consistency.

In other works, CSP resolution is described by considering the reduced domains instead of the removed values. Indeed, users are interested in the solutions (which belong to the reduced domains) and the removed values are forgotten. So a natural view of domain reduction is to consider the values which remains in the domains. But this does not reflect the solver mechanism. The solver keeps in the domains values for which it cannot prove that they do not belong to a solution (incompleteness of solvers). In other words, it computes proof only for value removals. So, we claim that domain reduction is based on negative information and we have described it from the natural view point of removed values.

Note that by considering d in place of d we reverse an ordering: d ⊆ d ′ ⇔ d ′ ⊆ d. This inversion must not be mistaken for another inversion: the inverse ordering defined by d ′ d ⇔ d ⊆ d ′ i.e. d gives more information than d ′ , the least fix-point of an operator becomes the greatest fix-point of the same operator (and vice versa). To choose or ⊆ is just a matter of taste. But in this paper we do not use the same idea: we cannot freely choose the ordering because it is only for the ⊆ ordering that the least fix-point of an operator is a set of proof tree roots. Here, the complementary of a greatest fix-point becomes a least fix-point by the use of dual operators.

A monotonic operator can always be defined by a set of rules in the sense of inductive definitions of [START_REF] Aczel | An introduction to inductive definitions[END_REF]. We have shown in [START_REF] Ferrand | Theoretical foundations of value withdrawal explanations in constraints solving by domain reduction[END_REF] that there always exists such a system which has a natural formulation for classical notions of consistency (partial and hyper-arc consistency of GNU-Prolog for example). These rules express a value removal as a consequence of other value removals. A notion of explanation, more precise than explanation sets, has been defined: the linking of these rules allows to inductively define proof trees. These proof trees explain the removal of a value (the root of the tree), so we called them value withdrawal explanations. Finally we have shown how to build incrementaly a proof tree from a chaotic iteration, in other words, how to obtain an explanation from a computation.

There already exists another explanation tree notion defined in [START_REF] Freuder | A case study in explanation and implication[END_REF] but it explains solutions obtained by inference in a particular case. In [START_REF] Freuder | A case study in explanation and implication[END_REF] the problem is assumed to have only one solution and the resolution of the problem must not require any search. The inference rules used to build explanations are defined thanks to cliques of disequalities.

There exists another formalization of solvers by domain reduction in terms of rules in [START_REF] Apt | Automatic generation of constraint propagation algorithms for small finite domains[END_REF]. The body of such a rule contains positive information (that is the membership of a domain) and the head contains negative information (that is non membership of a domain). So they have not the appropriate form to inductively define proof trees. Furthermore, the scope of these rules is to describe a new form of consistency called rule consistency. This consistency coincides with arc consistency in some cases and has been implemented thanks to Constraint Handling Rules [START_REF] Frühwirth | Constraint Handling Rules[END_REF]. Note that these Constraints Handling Rules could be transformed to obtain the appropriate form by allowing disequality constraints in the body.

Explanation sets have been proved useful in many applications: dynamic constraint satisfaction problems, over-constrained problems, dynamic backtracking, . . . The formalism proposed in this paper has permitted to prove the correctness of a large family of constraint retraction algorithms [START_REF] Debruyne | Correctness of constraint retraction algorithms[END_REF]. Explanations may be an interesting notion for the debugging of constraints programs (already used for failure analysis in [START_REF] Jussien | User-friendly explanations for constraint programming[END_REF]). Constraints programs are not easy to debug because they are not algorithmic programs [START_REF] Meier | Debugging constraint programs[END_REF]. Negative semantics provided by explanations can be a useful tool for debugging. An approach of constraint program debugging consists in comparing expected semantics (what the user want to obtain) with the actual semantics (what the solver has computed). The symptoms, which express the differences between the two semantics, can be either a wrong answer, or a missing answer. The role of diagnosis is then to locate the error (for example an erroneous constraint) from a symptom. In logic programming, it is easier to understand a wrong answer than a missing answer because a wrong answer is a logical consequence of the program then there exists a proof of it (which should not exist). Here, it is easier to understand missing answer because explanations are proof of value removals. Explanations provide us with a declarative view of the computation and we plan to use their tree structure to adapt declarative diagnosis [START_REF] Shapiro | Algorithmic Program Debugging[END_REF] to constraint programming.

In [START_REF] Tessier | Analysis and Visualisation Tools for Constraint Programming[END_REF] a framework for declarative debugging was described for the CLP scheme [START_REF] Jaffar | Semantics of constraint logic programs[END_REF]. Symptom and error are connected via some kind of proof tree using clauses of the program. The diagnosis amounts to search for a kind of minimal symptom in the tree. In [START_REF] Tessier | Analysis and Visualisation Tools for Constraint Programming[END_REF], the solver was only seen as a (possibly incomplete) test of unsatisfiability (well-behaved solver of [START_REF] Jaffar | Semantics of constraint logic programs[END_REF]) so constraint solving was not fully taken into account. But, for CLP in finite domains, constraint solving involves domain reduction for which we have defined in this paper another kind of proof tree: explanation trees. In a future work we plan to integrate these two kinds of proof trees in order to have finer connections between symptom and error.

Example 4 .Example 5 .

 45 Let us consider the local consistency operator r defined in example 2. So r(d) = r(d) = {(x, e) ∈ D | ∀(y, f ) ∈ d, {(x, e), (y, f )} ∈ T c }. Let B (x,e) = {(y, f ) | {(x, e), (y, f )} ∈ T c }. Then it is easy to show that B (x,e) ⊆ d ⇔ ∀(y, f ) ∈ d, {(x,e), (y, f )} ∈ T c . So r(d) = {(x, e) ∈ D | B (x,e) ⊆ d}. Finally, r is defined by R r = {(x, e) ← B (x,e) | (x, e) ∈ d}. Let us consider the CSP of example 1. Two local consistency operators are associated with the constraint x < y: r 1 of type ({y}, {x}) and r 2 of type ({x}, {y}). The set of deduction rules R r1 associated with r 1 contains the three deduction rules: (x, 0) ← {(y, 1), (y, 2)}; (x, 1) ← {(y, 2)}; (x, 2) ← ∅.

Fig. 1 .

 1 Fig. 1. Proof trees for (x, 0)

Acknowledgements: This paper has benefitted from works and discussions with Patrice Boizumault and Narendra Jussien.


Anissa Dakhli
email: dakhlianissa@yahoo.fr

Anissa Dakhli Doctorante

BUDGETARY PARTICIPATION, LOCUS OF CONTROL AND JOB SATISFACTION IN TUNISIA

Keywords: Budgetary participation, job satisfaction and locus of control participation budgétaire, satisfaction au travail et locus of control

 which are considered relevant to participative budgeting issues. In contrast to the "Anglo" Cluster, the Arabic Cluster of which Tunisia is a unit differs on the dimensions of "uncertainty avoidance" and "power distance." The results of this study suggest that budgetary participation affects negatively job satisfaction. It supports, also, the moderator effect of the personality variable locus of control. Internals appear more job-satisfied under conditions of high participation. By contrast, Externals are more job-satisfied under conditions of low participation.

INTRODUCTION

The effectiveness of the management planning and control systems used in developing countries remains an important issue for many reasons. As developing countries become more industrialized, progressive local firms may import systems and techniques from the more industrialized nations; indeed, such importation may be encouraged by educational institutions and consultants. Unfortunately, the progressive local firm may be importing systems from the industrialized world without considering the potential impact of cultural differences on the success of implementing such systems.

Support for the concern about the issues outlined above is found in current definitions of culture as a "shared reality" or shared "cognitive maps" [START_REF] Adler | Cross-cultural management: Issues to be faced[END_REF]Hofstede, 1980-87). Through the socialization process, members of a group learn the premises that make up this "subjective culture." These premises provide the essential basis for interpersonal relations leading to the effects described by [START_REF] Adler | Cross-cultural management: Issues to be faced[END_REF]: Culture influences organizations through societal structures such as laws and political systems and also through the values, attitudes, behaviour, goals, and preferences of participants. Thus, the view of "reality" held by members of a group is expected to affect their perception of the budgetary process and the values that they place on participation in that process [START_REF] Hofstede | Culture's consequences: International differences in work-related values[END_REF].

Specially, the moderated relationship between budgetary participation and job satisfaction has attracted the interest of many researchers. Brownell (1982a) examined the effects of participative budgeting and locus of control on performance and job satisfaction in a field setting. He found that a manager's personality would mediate the effects that the budget participation process would have on job performance and job satisfaction. Using the work of [START_REF] Hofstede | Culture's consequences: International differences in work-related values[END_REF]Hofstede ( , 1983) ) for hypotheses development, Frucot and Shearon (1991) theorized that culture might be an important variable in the budget participation-performance and budget participation-job satisfaction relationships. They tested the interrelationship of budget participation and locus of control (a personality variable) and their impact on job performance and job satisfaction of Mexican managers. They assumed that an organizational system such as budget participation would have different effects in different cultures. They suggested that foreign owned firms "may wish to exercise caution when applying participative budgeting techniques in Mexico (p. 96)."

While there is a large body of prior research on the relationship between budget participation and job satisfaction, none has specifically focused attention on participative budgeting within an Arabic country such as Tunisia. Nonetheless, it represents a fruitful area for managerial researches. Because of the strong cultural gap between Tunisia and these where were born modern managerial practices, these are likely to be inappropriate for Tunisian companies. In fact, importing management systems developed in industrial countries may create coherence problems.

When management approaches are transferred and insufficient consideration given to their cultural assumptions, they are likely to miss their objectives and to prove very disappointing.

Particularly, in Tunisian environment, with the recent phenomenon of internationalization of competition, Tunisian company had to improve its economic performance by adopting sophisticated managerial tools, and its social performance by giving more interest to its human resources. Thus, budgetary participation may serve to enhance managerial job attitudes such as job satisfaction and in consequence the performance of the manager who was involved in the budgetary system.

The findings of Brownell (1982) and the ostensible cultural gap between U.S and Tunisia have left several unanswered questions. (1) Can Tunisian companies expect budget participation to affect the job satisfaction of their middle-level managers? (2) Are there significant cultural differences between Tunisian managers and their US counterparts? And, (3) do these cultural differences, if they exist, lead to differences in the participation-job satisfaction relationships. The purpose of our study is to address these questions.

The remainder of this paper is organized as follows: Section 2 examines the theory for the hypothesis development. Section 3 includes a brief description of [START_REF] Hofstede | Culture's consequences: International differences in work-related values[END_REF] cultural dimensions. Section 4 outlines the research method employed and is followed by an analysis of the results of the hypothesis tests. The last section provides a discussion of the implication of the study, the limitations and suggestion for future research.

BUDGETING, PARTICIPATION, AND LOCUS OF CONTROL

The participation of operating managers in the budgeting process has long been one of the most controversial issues in the budgeting and management accounting literature. Early models of the budget-setting process were autocratic in nature. A company's top management was viewed as having the responsibility for setting operating budgets issuing them to operating managers, and then holding these managers accountable for performance in accordance with these imposed budgets. Pointing to evidence of restriction of output and lack of involvement under traditional managerial systems, several social psychologists, most notably Mc [START_REF] Mc Gregor | Do management control systems achieve their purpose?[END_REF] and [START_REF] Likert | New patterns in management[END_REF], argued for greater participation in decision implementation and execution.

Participation can be broadly defined as an organizational process whereby individuals are involved in, and have influence on, decisions that have direct effects on those individuals. While participation can have many contexts and settings, one in particular has, for the last decades, been of great interest to researchers in management accounting. This is the area of participation in budgeting that can be more specifically defined as a "process in which individuals, whose performance will be evaluated, and possibly rewarded, on the basis of their achievement of budgeted targets, are involved in, and have influence on, the setting of these targets (Brownell 1992 : 124).

In connection with budgeting, [START_REF] Becker | Budgeting and Employee Behavior[END_REF], [START_REF] Hofstede | Culture's consequences: International differences in work-related values[END_REF] and [START_REF] Swieringa | Some effects of budgetary participation on managerial behavior[END_REF] called for the participation of operating managers in budget-related activities pointing to evidence of operating manager resistance and hostility under early models of the budget-setting process, they suggested that top management share budget-setting responsibility with operating managers. That is the emergence of budgetary participation as an innovation in management accounting practices presumed to procure desirables organizational outcomes.

Extensive research has been conducted in the area of participative budgeting. The results are inconsistent in explaining linkages between participative budgeting and outcome variables such as job satisfaction and job performance. A review of some of the seminal works in the participative budgeting literature will be conducted.

In a related participative budgeting environment, [START_REF] Milani | The relationship of participation in budget-setting to industrial supervisor performance and attitudes: A field study[END_REF] investigated whether (1) the degree of participation in budget-setting and performance are positively related, (2) the degree of participation in budget-setting and attitude toward the job are positively related, and (3) the degree of participation in budget-setting and attitude toward the company are positively related.

Results of the study indicate that there is no significant relationship between participation and performance. However, strong support exists for both the relationship between participation and

(1) attitude toward the job and (2) attitude toward the company. [START_REF] Kenis | Effects of Budgetary Goal Characteristics on Managerial Attitudes and Performance[END_REF] reveal that managers who participate in the budgeting process appear to be more satisfied than are their counterparts. In a similar vein, Merchant (1981) reported a strongly positive relationship between participation and both motivation and attitudes. However, [START_REF] Brownell | A field study examination of budgetary participation and locus of control[END_REF] found only weak evidence of positive effects of participation on job satisfaction.

Yet in spite of this long line of inquiry, the literature remains fraught with contradictions, overlap and a general lack of conclusiveness on the question of whether participation is effective or not.

Particularly concerning the effects of budgetary participation on job satisfaction, the results were difficult to integrate and often conflicting. Participative budgeting research that investigates the relationships between budgetary participation and job satisfaction reveals significantly positive relationship [START_REF] Milani | The relationship of participation in budget-setting to industrial supervisor performance and attitudes: A field study[END_REF]Brownell, 1983b;Chenhall, 1986;Frucot and Shearon, 1991;[START_REF] Lindquist | Fairness as an antecedent to participative budgeting: Examining the effects of distributive justice, procedural justice and referent cognition on satisfaction and performance[END_REF], weak or non significant relationships (Brownell, 1982;Harrisson, 1992), and some even reveal negative relationships [START_REF] Otley | Budgetary criteria in performance evaluation: A critical appraisal using new evidence[END_REF].

Various researchers suggested that the relationship between participative budgeting and job satisfaction might be contingent upon the presence of other moderating factors. Brownell (1982:124) advanced four major classes of variables-cultural, organizational, interpersonal, and individual that may influence the relationship between participation and its consequences.

Internal-external locus of control was found by [START_REF] Brownell | Participation in Budgeting, locus of control and organizational effectiveness[END_REF] to influence the effects of participation. [START_REF] Rotter | Generalized expectancies for internal versus external control of reinforcement[END_REF] developed the locus of control construct. The construct refers to individual differences in a generalized belief in internal versus external control of reinforcement.

Those with an external locus of control see themselves as relatively passive agents and believe that the events in their lives are due to uncontrollable forces. Externals feel that the things they want to achieve are dependent on luck, chance and powerful persons or institutions. They believe that the probability of being able to control their lives by their own actions and efforts is low.

Conversely, those with an internal locus of control see themselves as active agents, feel that they are masters of their fates and trust in their capacity to influence the environment. Internals assume that they can control the events in their lives by efforts and skill. It is important to mention that prior researches indicated that locus of control is a fundamental personality trait.

They revealed that Internals are more satisfied than Externals when the budgetary process is participatory and that internals supervisors or managers are more participative in their budgetsetting style (Licata et al., 1986). Brownell (1982a) examined the effects of participative budgeting and locus of control on performance and job satisfaction in a field setting. Brownell's results indicate that participation does not have a significant direct effect on job satisfaction, but that individuals' locus of control has a moderating effect on the relationship between participation and job satisfaction.

Using the work of [START_REF] Hofstede | Culture's consequences: International differences in work-related values[END_REF]Hofstede ( , 1983) ) for hypotheses development, Frucot and Shearon (1991) tested the interrelationship of budget participation and locus of control (a personality variable) and their impact on job performance and job satisfaction. They assumed that an organizational system such as budget participation would have different effects in different cultures. Frucot and Shearon (1991) theorized that culture might be an important variable in the budget participation-performance and budget participation-job satisfaction relationships. They found that the Brownell (1982) result couldn't be generalizable to Mexican managers with regard to job satisfaction. The impact of locus of control on job satisfaction was not significant reflecting, thus, an ostensible difference in culture (between U.S and Mexico). Recently, Maria A. Leach-López et al. (2008) examine the effects of budgetary participation, and the personality variable, locus of control, on the performance and job satisfaction of Mexican managers working for US controlled maquiladoras on the US/Mexican border and within interior Mexico. This study follows the methodology employed by Frucot and Shearon (1991) and finds similar empirical results.

Despite that it attracted great attention of numerous researchers in occidental countries; little consideration had been given to budgeting in developing countries such as Tunisia. For instance, few studies interested in budgeting systems adopted by Tunisian companies were mainly exploratory. The purpose of this paper is to provide some support for a "contingent benefits" model of the effects of participation in the budgeting process. That is, the paper aims to investigate whether budgetary participation of Tunisian managers affects job satisfaction and if the managerial locus of control, as a personality variable, moderates this effect. Frucot and Shearon (1991, p. 85) expect budget participation to be less beneficial to job satisfaction among Mexican managers because of the high power distance and high uncertainty avoidance documented by [START_REF] Hofstede | Culture's consequences: International differences in work-related values[END_REF]. Harrison and McKinnon (1999, pp.494-496) indicate that high collectivism should be associated with a preference for participation. Based on Hofstede's scheme, Tunisian culture differs largely to American one where Brownell's study took place. [START_REF] Hofstede | Culture's consequences: International differences in work-related values[END_REF] identified four dimensions of culture:

CULTURAL DIMENSIONS

• Power distance: A measure of the degree to which cultures prefer a more autocratic structure. In an organizational context, it translates into the degree of participation that would be favored. A country scoring high on this construct would prefer a less participative style. Hofstede (1980, p.92) provides evidence that in a large PD society "close supervision [is] positively evaluated by subordinates." In a large PD society, subordinate consultation may not be as important as in a small PD society because there is a tendency for its members to accept paternalistic management [START_REF] Perera | The cultural relativity of accounting and international patterns of social accounting[END_REF]. Opposite from the US, Tunisia (as a unit of Arabic Cluster) is classified as a large PD society [START_REF] Hofstede | Culture's consequences: International differences in work-related values[END_REF], and thus Tunisian managers would be expected to prefer a centralized management, and be averse to budget participation.

• Uncertainty avoidance: A measure of the mean anxiety level. A high anxiety level translates into less willingness to take risks and a preference for security. Organizations in a high uncertainty avoidance environment would favor rigid rules, so as to decrease uncertainty. According to [START_REF] Perera | The cultural relativity of accounting and international patterns of social accounting[END_REF], the fundamental issue involved in this dimension is how a society reacts to the fact that the future is not known; whether the society tries to control the future or just let it happen. Unlike the US, Tunisia is classified as a medium UA society, thus Tunisian managers should prefer low budget participation.

• Individualism: A measure of the relative importance of independence from the organization. Cultures scoring high on this construct stress goals and independence.

Cultures scoring low on this construct favor more dependence on the organization. Under this perspective, an individual is seen as having an identity in and of him or herself, which is separable from, and is not dependent upon, a group affiliation [START_REF] Hofstede | Culture's consequences: International differences in work-related values[END_REF].

According to [START_REF] Perera | The cultural relativity of accounting and international patterns of social accounting[END_REF], in an individualistic society, the employer-employee relationship would tend to be calculative (benefit the individual), but in a collectivistic society this relationship would tend to be morally based (benefit the group).

Opposite from the US, Tunisia is classified as a collectivistic society [START_REF] Hofstede | Culture's consequences: International differences in work-related values[END_REF], so Tunisian managers would be expected to prefer teamwork and team rewards.

• Masculinity: A measure of the relative importance to the culture of income, recognition, and advancement as compared to the importance of work relations, cooperation, and security. Femininity represents a preference for putting relationships with people before money, the quality of life, and preservation of the environment. This dimension draws attention to the existence within society of competitiveness as opposed to solidarity, and achievement motivation as opposed to relationship motivation. Some of the issues raised by this dimension are career expectations and acceptability of an autocratic manager [START_REF] Perera | The cultural relativity of accounting and international patterns of social accounting[END_REF]. Both Tunisia and the US are classified as High in the Masculinity dimension [START_REF] Hofstede | Culture's consequences: International differences in work-related values[END_REF].

With respect to Hofstede's classification, Arabic countries were grouped in one Cluster. That is, to more explore the Tunisian culture, Zghal's (1990-91-94) and Ben Fadhel's (1992) studies provide particularly useful evidences on this question. With an exploratory research, Zghal identified a cultural configuration based on three variables that may explain many behaviors observed in Tunisian companies. The Tunisian culture highlights ambiguity in decision making, equity, and dignity but dislikes subordination relationship.

With respect to delegation, Zghal concluded that's rarely practiced. Tunisian top managers think that their subordinates perform better their tasks when they had, only, to execute without taking any initiative. They consider them as relatively passive agents who search, only, personal goals. Also, they dislike responsibilities and particularly decisions making. In management, the Arab manager is likely to tolerate uncertainty but does not delegate power to his subordinates.

Ben Fadhel initiated his research on Tunisian culture with a historic analysis of Tunisian values.

He identified six dimensions that describe Tunisian national culture: A high collectivism, a large power distance, a high Masculinity, a small anxiety, a medium tolerance for uncertainty, and an aversion towards risk taking.

Based on Hofstede's dimensions and with reference to Zghal's (1990-91-94) and Ben Fadhel's (1992) studies, respondents from the United States and Tunisia (which is a unit of Arabic Cluster) would be classified as follows:

The potential implication of this classification is: In Tunisia, a more paternalistic and autocratic leadership style (with less participation in decision making and more rules and centralization) would be preferred. In addition, more dependence of the individual on the organization is expected. Based on Hofstede's classification scheme, we would expect that the relationship between participation in the budgeting process and managerial satisfaction may be different in Tunisia than in the U.S. Adler (1984) stresses that it is important to replicate research performed in one national culture, in order to increase our knowledge of culture's impact. To facilitate comparability, Adler also recommends that the replication in another culture follow the initial study's research method as closely as possible. Therefore, the hypotheses tested in this study follow Brownell (1982a). They can be stated as follows:

H 1 : In Tunisia, the degree of participation in the budgetary process leads to higher satisfaction.

H 2 : In Tunisia, there will be a significant interaction between budgetary participation and locus of control affecting job satisfaction.

METHOD

A questionnaire survey was used. The sample consisted of 75 middle-level managers working in 30 industrial companies. The research started with a brief interview with a senior corporate official, such as the financial vice-president, controller, or director of planning and budgeting. This interview was used to gather data on the company( size, kind of industry...) and the

U.S. Tunisia

Power distance Low High

Uncertainty avoidance Low medium

Individualism

High Low

Masculinity

High High corporate planning and budgeting systems and to identify a sample of middle-level managers who were involved in budgeting.

The questionnaires were personally distributed to 93 managers involved in the study who kept them to complete on their own time. The completed questionnaires were then collected. Personal contacts with both the companies and respondents led to 83 per cent response rate. However, of the 78 questionnaires collected, three were excluded from the study for incomplete responses.

The final sample size for hypotheses testing was reduced to N=75.

Variables measurement:

Three variables were measured by questionnaire: budgetary participation, locus of control, and job satisfaction.

Budgetary participation:

The six-item instrument of [START_REF] Milani | The relationship of participation in budget-setting to industrial supervisor performance and attitudes: A field study[END_REF] was employed to assess budgetary participation. The instrument attempted to assess the respondent's involvement in and influence on the budget process. The scale is additive with the summed score providing a measure of the respondent's perceived degree of participation in the budgeting process.

Satisfactory reliability and validity for the scale have been reported by prior researchers (e.g. [START_REF] Brownell | A field study examination of budgetary participation and locus of control[END_REF]-83, Brownell and Hirst, 1986, Chenhall, 1986, Dunk, 1989, Frucot and Shearon, 1991[START_REF] O'connor | The influence of organizational culture on the usefulness of budget participation by Singaporean-Chinese managers[END_REF]. In the current study, the Cronbach alpha coefficient was 0.95.

Locus of control:

The internal-external scale questionnaire, developed by [START_REF] Rotter | Generalized expectancies for internal versus external control of reinforcement[END_REF] was employed to assess locus of control. It contains 29 questions which require a forced response between "internal and external" answers. This instrument is widely used in psychological and accounting researches and several extensive literature reviews attest to its validity and reliability [START_REF] Swieringa | Some effects of budgetary participation on managerial behavior[END_REF]Brownell, 1981-82b;Licata et al., 1986). In this study, the Cronbach alpha coefficient was 0.65.

Job satisfaction:

Job Descriptive Index (JDI) of Smith, Kindall and Halin (1969) was chosen to assess job satisfaction. This instrument outperformed a satisfactory rate of validity [START_REF] Kenis | Effects of Budgetary Goal Characteristics on Managerial Attitudes and Performance[END_REF]. It measures managerial satisfaction at five scales: the remuneration, the opportunity of promotion and advancement, the job itself, the relations with supervisor, and the relations with colleagues. As for reliability of the scale, the Cronbach alpha coefficient was 0.88.

RESULTS

As noted later, descriptive statistics for the independent variables and dependent variable are presented in Table 1, while Table 2 presents the correlation matrix among the independent and dependent variables. Table 3 presents the results of the regression analysis.

The following model was used to test the hypotheses:

SAT=a 0 + a 1 BP + a 2 LOC + a 3 BP*LOC + ε ε ε ε (1)
Where SAT is satisfaction measure using the JDI of Smith et al. (1969),

BP is budget participation measured as the sum of the six-item scale developed by [START_REF] Milani | The relationship of participation in budget-setting to industrial supervisor performance and attitudes: A field study[END_REF],

LOC is locus of control as measured using [START_REF] Rotter | Generalized expectancies for internal versus external control of reinforcement[END_REF] Internal/External scale, BP*LOC is the interaction of budgetary participation and locus of control.

Direct effect of budgetary participation

The model ( 1) tests the effect of participation, locus of control, and their interaction on job satisfaction. The interaction term matches the personality trait with the characteristics of the firm's budgetary process. The results of the moderated regression analysis are reported in table 3.

The participation coefficient is found to be significantly negative (-0.348) and fails, hence, to

show the expected sign. It suggested that participation, alone, exerts a substantial negative influence on job satisfaction of the Tunisian managers. This finding is not consistent with previous results [START_REF] Milani | The relationship of participation in budget-setting to industrial supervisor performance and attitudes: A field study[END_REF][START_REF] Kenis | Effects of Budgetary Goal Characteristics on Managerial Attitudes and Performance[END_REF][START_REF] Brownell | Leadership style, budgetary participation and managerial behavior[END_REF]Chenhall, 1986;Frucot and Shearon, 1991;[START_REF] Leach-Lopez | Differences in the role of job relevant information in the budget participation-performance relationship among U.S and Mexican managers: A question of culture or communication?[END_REF][START_REF] Leach-Lopez | An update on budgetary participation, locus of control, and the effects on Mexican managerial performance and job satisfaction[END_REF] which attest a positive association between the two constructs. Thus, the first hypothesis is rejected. This finding is in accordance with Hofstede's framework, in which it was expected that Tunisian managers would prefer a non participative budgetary structure.

Moderating effect of locus of control

According to [START_REF] Sharma | Identification and analysis of moderator variables[END_REF], to identify the presence and the kind of the moderator variable, two methods may be used: sub-group analysis and moderated regression analysis-ARM.

Really, these two methods are complementary because the moderated regression analysis, alone, can detect only the presence or not of an interactive effects. It doesn't permit to know how this factor influences the direct relationship. For the present study, we combined the two methods in order to know if there is any interaction between locus of control and job satisfaction and, if it exists, how it affects job satisfaction.

The matrix of intercorrelation, as provided in table 2, indicates that there is no significant correlation between independent variables. Therefore, we can use the moderated regression analysis method.

As reported in table 3, the interaction coefficient is significant at the 0.01 level. The coefficient for locus of control is positive but fails to reach significance at any reasonable level. These results

indicate that job satisfaction is associated with both locus of control and participation. It's clear that there is a significant interaction between budgetary participation and locus of control in affecting job satisfaction. These results lead to a support of the second hypothesis.

Further analysis

In order to better explore the second hypothesis, a sub-group analysis was performed by devising the sample into two groups (G 1 : internals and G 2 : externals). The interviewee was classified as internal or external based on his number of internals and externals responses. Thus, if the most of his responses are externals, he will be classified as external and if the most of his responses are internals, he will be internal. Then, a linear regression analysis was performed on each group.

SAT I = β 0 + β 1 BP I +ε Where SAT I is standardized job satisfaction for internals BP I is standardized budgetary participation for internals SAT E = α 0 +α 1 BP E + ε Where SAT E is standardized job satisfaction for externals yytyssssssssssss BP E is standardized budgetary participation for externals

As shown in tables 4 and 5, the participation coefficients are statistically significant and show the expected sign. These results are consistent with Brownell's (1982a). They imply that satisfaction with the particular job-aspect is higher for internals in high participation conditions and for externals in low participation conditions.

It seems that internals are significantly more satisfied with high budgetary participation.

However, externals do not prefer this kind of budgeting system.

DISCUSSION AND CONCLUSION

This study provides evidence that cultural differences may lead to different responses to participative budgeting and that various groups within a culture may react differently to a particular budgeting system. We conclude that participation alone negatively affects the job satisfaction of the Tunisian manager. This result is, clearly, not consistent with the findings of a number of studies which focused on the influence of budgetary participation on managers' attitudes and behaviours. Particularly, it does not support Brownell (1982)'s one. This divergence may be attributed to cultural differences. These cultural differences between the US and Tunisia documented by [START_REF] Hofstede | Culture's consequences: International differences in work-related values[END_REF] may reduce the benefits of participative budgeting in Tunisia.

This unexpected result may be justified as follows: First, the participative management is, relatively, recent in Tunisian companies. The managers did not, already, familiarised themselves with this new managerial practice and, so, they don't value the benefits brought by this opportunity. Second, Tunisian top managers are likely practicing a pseudo-participation and not a real participation. In other words, they are relatively involved in budgeting process but without any influence in final budgets.

A pseudo-participative process is defined as budgeting process that leads subordinates to believe that they will have some influence on the budget that is set, but in reality, their input is ignored [START_REF] Libby | The influence of voice and explanation on performance in a participative budgeting setting[END_REF]. The pseudo-participation can have demotivating effects on subordinates (Pasewark and Welker, 1990) and can lead to dysfunctional effects [START_REF] Becker | Budgeting and Employee Behavior[END_REF][START_REF] Libby | The influence of voice and explanation on performance in a participative budgeting setting[END_REF].

Third, studies focused on Tunisian culture (Zghal R, 1991;B. Fadhel A, 1992) allow us to describe this negative association between budgetary participation and job satisfaction as reasonable and even expected. The Tunisian culture emphasizes a rare power delegation (strong decentralization) and a refuse of responsibilities. Furthermore, based on [START_REF] Hofstede | Culture's consequences: International differences in work-related values[END_REF] classification scheme, in Tunisia a more paternalistic and autocratic leadership style (with less participation in decision making and more rules and centralization) would be preferred (B.Fadhel Adnen, 1992). In addition, more dependence of the individual on the organization is expected. In fact, Arabic cluster of which Tunisia is a unit is classified as having high power distance, and low individualism. In such cultural climate, managers' reactions to participation are expected to be negative (Harrisson, 1992).

Based on this study's results, Tunisian firms may wish to exercise caution when applying participative budgeting techniques, perhaps involving middle-level managers in the implementation process. Bourguignon et al. (2004) indicate that when a management technique (such as participative budgeting) is exported to a new cultural environment, implementation is more successful when the ideological framework (of which the culture is a unit) is coherent with the characteristics of that technique. "When management approach are transferred and insufficient consideration given to their ideological assumptions, they are likely to miss their objectives and to prove very disappointing .The importance of local ideology should be recognised, especially in the case of management systems created and developed in ideologically different environment" (Bourguignon et al. 2004 :109).

The results support the expectation that participation is most effective for internally oriented individuals. In the area of job satisfaction, the tentative conclusion from previous Brownell's 1982) study is confirmed in the present study. Brownell identified the relationship between locus of control (a personality variable) and participation in the budgeting process as it impacts managerial satisfaction. Tunisian Internals managers are satisfied under a participative budgeting system but Externals are not. The reactions of managers to budgetary participation differ clearly according to their personal traits. Internals, because they behave as active members of the group and aim to be involved in the decisional process of the company, they prefer a participatory budgeting system where they will have some influence on the budget that is set jointly. Thus, this participatory system gives them opportunities to influence the environment and be an active agent in consequence. Also, Externals managers seem refusing responsibilities. They prefer receiving and executing top management's orders. They, even, perform better under an autocratic decisional system. Thus, they react negatively to budgetary participation.

The result of this study has practical as well as theoretical relevance. At the practical level, it recommends to the designers of budgeting systems that they ought not to give high budgetary participation indiscriminately to subunit managers. They must consider the personal characteristics of managers involved in this budgeting system. As regards theory development, the results of this study suggest the fruitfulness of considering other contingency variables in researching the effects of participative budgeting. As Brownell (1982) argued, participation in the budgetary process might be contingent on four groups of variables: cultural, organizational, interpersonal, and individual. Future research should focus attention on all four groups of contingency factors in order to develop a comprehensive and integrated model specifying the conditions under which budgetary participation will produce favorable outcomes. Our study has common limitations found in this type of research. Each variable is measured with an established scale, but each of these scales contains some level of measurement error and each observation is dependant on the subject answering truthfully and accurately. There is also the potential weakness of using self-reported measures of budget participation. Self-reported levels of participation may be more relevant than external measures of participation because it should be the subject's perception of budget participation that influences behavior.

Since, only industrial companies were examined, the result may not be generalized to non industrial companies (such as companies of services, commercial companies…). The survey approach as well has limitations, such as the lack of control over who responds to the questionnaires (Nouri and Parker, 1996). Further, the distribution of questionnaires was not random. In order to insure the managers' collaboration in this research, we were obliged to use our acknowledgements in some companies. Normally, to examine the cross-cultural generalizability of a prior research's findings, we had to follow the same methodology employed by the former. Unfortunately, this condition was not respected in this study. While Brownell (1982a) used the Minnesota Satisfaction Questionnaire (MSQ), the Job Descriptive Index was adopted to assess job satisfaction in the current research. Notwithstanding these limitations, this research provided a supportive evidence of the need to recognize the existence of important moderating effects of the personality variable, locus of control, on the relationship between participation and job satisfaction. Further research is obviously needed to expand our understanding and awareness of other individual characteristics that complement design features of budgetary control systems. Indeed, the more basic question of what control system features are appropriate to manage activities that face differing environmental and cultural circumstances still remains largely unanswered.

Table 1 :

 1 Descriptive statistics for measured variables

		N	Possible range Actual range Mean	Std.deviation variance
	Budgetary participation 75	15-75	15/74	52,733	15,919	253,414
	Job satisfaction	75	19-95	33/92	63,613	13,4816	181,754
	Locus of control	75	-15/15	-11/12	0,53	5,7945	33,58

Table 2 :

 2 Matrix of intercorrelations between independent variables

		BP	LOC	BP*LOC
	Correlation	1
	Sig. BP	-	-----	------
	N	75
	Correlation	.089	1
	Sig. LOC	.225	-	------
	N	75	75
	Correlation	.137	.045	1
	Sig. BP*LOC	.12	.35	-
	N	75	75	75

Table 3 :

 3 Regression results

	Coefficients	Value	Std.deviation	t	Probability
	constant	-0.182	0.122	-1.49	n.s
	Budgetary participation -0.348	0.124	-2.807	< 0.05
	Locus of control	0.177	0.125	0.158	n.s
	Interaction coefficient 1.46 E-02	0.14	4.115	< 0.01
	Adjusted R 2 =0.085

Table 4 : regression results for internalsTable 5 : regression results for externals

 45

	Coeff	Value	Std.	t	prob	Coeff	Value	Std.	t	prob
		deviation					deviation
	β 0 7.851E-02 0.128	0.615	n.s	α 0	-0.625	0.132	-4.719 < 0.01
	BP I	0.412	0.15	2.75 < 0.01	BP E	-0.862	0.117	-7.36 < 0.01
	Adjusted R 2 = 0.157				Adjusted R 2 = 0.61