Hélène Personnier
email: helene.personnier@g-scop.grenoble-inp.fr

Marie-Anne Le Dain
email: marie-anne.le-dain@g-scop.inpg.fr

Richard Calvi
email: richard.calvi@univ-savoie.fr

A G -Scop

21st Annual IPSERA

Keywords: New Product Development (NPD), Early Supplier Involvement (ESI), Failure, Glitch, Literature review

The focus of the firms on their core competencies associated with the increasing complexity of products due to an integration of various technologies has led to an extension of their New Product Development (NPD) activity across organisational boundaries. In this respect, it is now acknowledged that Early Supplier Involvement (ESI) in product development confers a competitive advantage. Nevertheless appraising the benefits of such collaboration on the product development performance is not easy. Our method is based on the "glitch" concept that enables to appraise ESI benefits from the opposite direction i.e. by identifying what happens when the collaboration with suppliers is absent. Our previous work presented at IPSERA 2011 dealt with an in-depth case study analysis of an unsuccessful collaborative development with a supplier. In this previous paper, we identified ten "glitches" that prevented from reaping the benefits of supplier involvement. The aim of this paper is to carry out a literature review about failures in collaborative development of new product between a customer and a supplier. By comparing those literature review results with case study results, we aim at proposing a classification of the failures currently encountered in collaborative development with suppliers in order to tackle them.

Introduction

Today's aggressive and expanding global marketplace and competitive pressures compel firms to consider new strategies in order to compress time between each stage of the value chain [START_REF] Batchelor | Moves in the right direction[END_REF] and to stay competitive. It is acknowledged that innovation helps enterprises to increase their competitive position [START_REF] Rehm | Advantage of open innovation in buyer-supplier relationships -A review and analysis of the literature[END_REF]. The suppliers represent an important source of potential innovation. Furthermore, [START_REF] Stephan | Integration of suppliers into the product development process using the example of the commercial vehicle industry[END_REF] stated that in the year 2015, about 90% of all manufacturing activities will be carried out by suppliers. Therefore, customer companies have to successfully collaborate with suppliers in new product development in order to gain competitive advantage. A means that many companies are adopting to gain competitive advantage is to involve suppliers earlier in the design phases. Early Supplier Involvement (ESI) is generally defined as a form of vertical cooperation in which manufacturers involve suppliers at an early stage in the NPD process [START_REF] Bidault | Leveraged innovation: Unlocking the innovation potential of strategic supply[END_REF]. A large range of papers has identified the benefits of Early Supplier Involvement (ESI) on product development performance measured by shorter time to market, improved product quality and reduced development costs [START_REF] Bidault | Leveraged innovation: Unlocking the innovation potential of strategic supply[END_REF][START_REF] Ragatz | Success Factors for Integrating Suppliers into New Product Development[END_REF][START_REF] Van Echtelt | Managing Supplier Involvement in New Product Development: A Multiple-Case Study[END_REF]. Moreover, literature contains contradictory results [START_REF] Hoegl | Buyer-Supplier Collaboration in Product Development Projects[END_REF] concerning ESI benefits on NPD performance and some studies present a negative impact [START_REF] Eisenhardt | Accelerating adaptive processes: Product innovation in the global computer industry[END_REF][START_REF] Wynstra | Purchasing Involvement in Product Development[END_REF]. For a lot of industrial actors, it is thus difficult to invest resources in collaborative design with suppliers when real expected benefits are unknown. The aim of our research work is to appraise ESI benefits in order to legitimate this practice. But as it is complicated to obtain a quantification of those benefits, we have adopted an approach from the opposite direction through the help of the "glitch" concept i.e. "a costly mistake that could have been avoided if some of the parties involved had understood things that were known by other participants (Hoopes and Postrel, 1999, p838)". A glitch is due to to a lack of knowledge sharing which can cause unnecessary iterative loops in New Product Development Processes for instance in decision making process. As all dysfunctions in collaborative new product development with suppliers are not due to a lack of knowledge sharing but can also be due to strategic aspects for instance, the word "failure" will be used to enlarge to other classes of dysfunctions. Following the ISO 9000 standard (2005), a failure corresponds to the non-fulfilment of one or more product requirements and can have fatal consequences for the product's success. This way, considering glitches and other potential failures, identifying their impact on product development performance and hence defining preventive actions to avoid these unproductive phenomena seems to be a good path to appraise ESI influence on collaborative New Product Development with suppliers. This paper embodies a part of a research program and is complementary with our previous IPSERA paper [START_REF] Personnier | How to appraise the benefits of collaborative design with suppliers? A glitch-based approach[END_REF]. The aim of this research program is threefold: (1) to obtain a list, as exhaustive as possible, of typical failures that can occur during co-development with suppliers, (2) to classify those failures and (3) to identify means to tackle them in order to have successful collaborative development and generate gains. We adopt an iterative approach: case study results have raised questions, then literature results enabled us to answer some questions and other case studies are carrying out in order to enrich results obtained. The first step of this research work was an inductive approach including an in-depth case study of an unsuccessful collaborative development of a new product with a supplier. This work allowed us to gather data and to obtain a first list of ten observed failures with associated costs. The second step of this research work is presented in this paper. Stemming from a literature review about failures in collaborative New Product Development with suppliers, the aim is to draw up a list of typical failures and to categorise them. Then we integrate empirical insights coming from field case study by comparing them to literature review results. Finally conclusions are drawn from this work by discussing future research avenues.

Review methodology

The study is based on a literature review using a four-stage process (Figure 1). It aims at collecting and analysing potential dysfunctions during a collaborative new product development with a supplier. [START_REF] Westner | Information Systems Offshoring: A review of the literature[END_REF] The first step literature retrieval involves a research of articles in databases and journals thanks to key words such as glitch, barrier, failure, dysfunction, and impediment in New Product Development. Only articles published in peer reviewed journals were considered. The time frame starts in the 1980s because following [START_REF] Johnsen | Supplier involvement in new product development and innovation: Taking stock and looking to the future[END_REF] study, the first research focusing on supplier involvement in NPD was the study by [START_REF] Imai | Managing the new NPD process: how Japanese companies learn and unlearn[END_REF]. The second step literature exclusion is a step for selection in order to exclude articles non relevant concerning our focus. We have focused our work on about fifteen articles. Those articles deal with failure/dysfunctions/impediments/glitches in collaborative development of new product between customer and supplier companies. For each article, the main failures reported were extracted. The third step literature classification involves classification of data collected. A table was employed for mapping the literature in order to compare previous papers across various fields such as: the failure description; the article's author and the methodology. More than 100 failures were encountered in the body of literature and were then organized in classes. A feature map was built to locate any similarities and differences between failures identified in literature [START_REF] Hart | Doing a Literature Review, Releasing the Social Science Research Imagination[END_REF]. From those similarities and differences, 22 sub-classes have been proposed. The fourth and last step results summary is an analysis and discussion about the results. The data obtained, which is a list 21st Annual IPSERA Conference of failures, were then compared to the data of our previous case study carried out in a French company considered as a global market leader for roller shutter motorisation.

Fig 1 Review approach inspired from

Proposition of a classification of failures in collaborative design with suppliers

A literature review has been carried out in order to collect and analyse potential failures during a collaborative new product development with a supplier. Table 1 presents an overview of failures noticed in this literature review and mentions the author, the methodology adopted, the failure characteristics and the sub-class the failure is related to. Specifications are even changed after tooling and method of manufacture have been decided Specifications modification

Original equipment manufacturers do not listen enough to the expertise of suppliers. For example, t oo much cost-saving in the design might lead to poor satisfaction of functionality in several cases.

Information sharing

Different actors did not perceive a question in the same way.

Interpretation and understanding

Differences in frame of reference between the company people and the suppliers. Difference of mindset between t ruck customer and automotive supplier. Misunderstandings about what the supplier could contribut e to the project (cars Vs trucks producers).

Relational alignment

Overestimation of what extend the suppliers could contribute to their design process Competene needed Difficulty to achieve a full internal commitment Joint decision for the supplier choice Bad collaboration. Both languages and dist ance complicated collaboration.

Interpretation and understanding

Difficulty for t he project team to explain their problems with the supplier to t he management. T he management knew t he successful st ories from the Japanese automotive industry.

Int ernal communication

Changes in the documents or incomplet e documents. No common management of documents set up. Two comments can be made from this literature review.

• Firstly, all failures reported are not glitches following [START_REF] Hoopes | Shared Knowledge, "Glitches," and Product Development Performance[END_REF] definition.

In fact, when the unit of analysis is the project, three requirements have to be verified to 21st Annual IPSERA Conference recognize a failure as a glitch [START_REF] Hoopes | Shared Knowledge, "Glitches," and Product Development Performance[END_REF]. Firstly, the product development must be conducted by a cross-functional team. This condition is not always explicitly mentioned in literature studies except from research works based on case studies. Secondly, the failures lead to unsatisfactory project results. In most articles, the authors reported the observed failures but without always specifying their sources and their impact on the project results. Thirdly, the failure observed could have been avoided using knowledge of one actor involved in the project. This condition is difficult to verify because details about the failures are not always available. Nevertheless, some authors reported a lack of shared understanding inside the project team [START_REF] Karlsson | Black Box Engineering: Redefining the Role of Product Specifications[END_REF][START_REF] Kleinsmann | Barriers and enablers for creating shared understanding in co-design projects[END_REF]& 2010). (Mc Ivor et al., 2006) observed a lack of information exchange in particular concerning strategy. When the unit of analysis is the organization, [START_REF] Van Echtelt | Managing Supplier Involvement in New Product Development: A Multiple-Case Study[END_REF] report failures due to inappropriate management of the supplier involvement; [START_REF] Koufteros | Organizational Integration for Product Development: The Effects on Glitches, On-Time Execution of Engineering Change Orders, and Market Success[END_REF]) mention a lack of organizational response from the customer organization; [START_REF] Vaaland | Exploring interorganizational conflict in complex projects[END_REF] speak about conflict between organizations. • Secondly, from the list of 22 sub-classes, a categorisation of six global failures classes was proposed (Table 2). This categorisation was inspired by main themes mentioned in literature concerning collaborative development of new products with suppliers. The definition of each class of failures is given below.

Table 2: Proposition of sub-classes and classes of failures in NPD with suppliers

Alignment between both companies

The alignment can take the form of the strategic alignment (motivation and goal congruence), technological alignment or relational alignment [START_REF] Emden | Collaborating for New Product Development: Selecting the Partner with Maximum Potential to Create Value[END_REF][START_REF] Evans | Improving co-development through process alignment[END_REF]. The relational alignment refers to alignment of mindsets (industrial or cultural) and to the trust [START_REF] Sako | Prices, quality and trust. Inter-firm relations in Britain and Japan[END_REF]. Alignment of mindsets is not synonymous to 'similarity of mindset' as highlighted by [START_REF] Lam | Identifying and prioritizing critical success factors for conflict management in collaborative new product development[END_REF]: "With the mindset that certain conflict could be beneficial, clients and suppliers are apt to express their judgmental differences for improving decision making, which also fosters cognitive conflicts and thereby leads to better NPD performance as well" (p.764).

Supplier Choice and Status

This class refers to the question of how the supplier has been chosen and for what competences (supplier status). The supplier status is one of the outputs of the "Design-or Buy-Design" decisionmaking process. It refers to the situation of supplier involvement decided by the project team; black box, or grey box or white box engineering [START_REF] Handfield | Involving Suppliers in New Product Development[END_REF]. Once the supplier status defined, what are the relevant criteria for choosing the appropriate supplier? The choice of the supplier and its status in the collaboration might be characterised by a joint decision (le Dain et al. 2010).

Contractual Coordination

This class has been inspired by [START_REF] Sobrero | Structuring Inter-firm Relationships: A Meta-analytic Approach[END_REF]. It refers to the negotiation between customer and supplier about the issues to be included in the contract (confidentiality agreement, deliverables expected from supplier and customer, intellectual property and patent policies, detailed planning).

Specification Process

This class refers to the specific problems mentioned by [START_REF] Karlsson | Black Box Engineering: Redefining the Role of Product Specifications[END_REF] in their study of automotive suppliers related to the technical content, the requirements, the product cost, and the participation of the supplier in the specification process.

Procedural Coordination

This class is also inspired from [START_REF] Sobrero | Structuring Inter-firm Relationships: A Meta-analytic Approach[END_REF]. It refers to the coordination of the activities of the partners in the collaboration to achieve the objectives of the project. The authors argue that "the higher the level of task uncertainty, the greater the need for procedural coordination" (p.592).

Communication

Communication problems might be the outcome rather than the cause [START_REF] Maier | Towards managing team-interfaces: an exploratory elicitation of factors influencing communication[END_REF]. In this class, we consider the communication failures as symptoms of, for example, lack of information sharing and lessons learned, differing interpretation and misunderstanding between actors. Previous research has stressed the central role played by inter-firm communication [START_REF] Dyer | Collaborative advantage: winning through extended enterprise supplier networks[END_REF][START_REF] Kamath | A second look at Japanese product development[END_REF][START_REF] Petersen | Supplier integration into new product development: coordinating product, process and supply chain design[END_REF][START_REF] Takeishi | Bridging Inter-and Intra-Firm Boundaries: Management of Supplier Involvement in Automobile Product Development[END_REF]).

Discussion with results stemmed from a case study

In a second time, the literature results, presented in the previous section, were compared to results obtained during a case study carried out in a French company. At first the case study is presented.

Then the failures encountered during this case study are reported and discussed with the background of literature.

Case description

A first recent experience of collaborative design (Project P) was judged as unsuccessful by partners ROLMO and its key supplier CAB. Thus, the customer expressed the need of understanding the reasons of this failure. This analysis acted as "learning history" and was used to stimulate thinking and encourage learning in the project teams of ROLMO and the supplier [START_REF] Kleiner | How to make experience your company's best teacher?[END_REF].

ROLMO is a French company that manufactures roller shutter motorisation and supplier CAB is the world leader for cable manufacturer industry (for high voltage, energy cables) and it is an historical supplier of ROLMO. The analysis of project P with supplier CAB was conducted between February 2010 and June 2010 by the participant researcher who has joined the project team on a full-time basis.

The collaboration with supplier CAB has started at the open of Project P in May 2009 and stopped in June 2010. This case study was reported in our previous IPSERA paper.

The goal of Project P is to create a new roller shutter motorization. The level of exigencies is very high because ROLMO wants to distance itself from Asia competitors by launching the development of a high-of-the-range product. Project P included the co-development of the external connector to be used in the new roller shutter motorization. The external connector is a sub-system including the development of a cable and a plug. ROLMO chose to outsource the design and the development of this sub-system. The main reason of this choice is that ROLMO did not beneficiate of internal resources and skills for this specific design and the development of this connector is not a core-activity for the customer. Thus, it was relevant to benefit from the experience of a specialist that can do the development work more efficiently than the customer. This connector is a specific sub-system that must handle the power supply of the motor. It was considered a key sub-system owing to its substantial impact on the performance of the motorisation. The function to be developed is also a critical function as regards part of cost structure, safety, resistance to humidity, resistance to handling, robustness, earth connection, resistance to transport, multi-sourcing and compatibility with voltages and currents. Supplier CAB has been selected to perform this design. The previous roller shutter motor external connector was co-developed 15 years ago with the selected CAB. Since this previous project, CAB manufactured most of cables purchased by the customer but the latter has not been re-mobilised for its design expertise concerning the cables development. For this reason, CAB was more known as a key commodity supplier than as a designer supplier. In addition, CAB has known some difficulties in the past and then had to reduce its R&D resources. CAB has been recently integrated in a group who has a centre of R&D. At the beginning of the considered project, ROLMO needed design expertise and intuitively the project team has consulted this historical supplier for this technology. ROLMO conducted an audit to evaluate the capability of the product development process of CAB. The audit team, composed of supplier quality assessment actors and the commodity manager, highlighted some doubts related to the ability of the supplier to bring in the necessary R&D resources within a new product development project. Despite this negative signal observed, the project team minimized it because of the past experience and the trust toward CAB. In addition, the commodity manager advocated the selection of CAB. Supplier CAB has invested resources to develop a plant in a low cost country to support the business of ROLMO. The implication of CAB in project P1 would lead to the production in this new plant. Nonetheless, as collaboration progressed, the negative signal became more and more harmful. Despite of efforts to continue the collaboration with CAB, ROLMO took the decision to stop the collaboration with CAB and to change of supplier.

Failures encountered during the case study analysis

Table 3 and Table 4 show the failures observed following the six different classes presented in section3.

As the collaboration of this case study was observed in a chronological way, failures are reported following the relationship lifecycle. This chronological view of the co-development relationship is inspired from the lifecycle of partnership model of [START_REF] Fraser | Managing product development collaborations -a process maturity approach[END_REF]. This model allows the mapping of issues that are likely to arise at the different stages of the collaborative relationship. We have distinguished two stages in this relationship lifecycle as in our previous IPSERA paper (Personnier, le Dain, Calvi, 2010):

-The relationship design. This stage takes into account the supplier selection and the construction of the relationship framework (contracting, determination of roles and resources, need specification).

-The day to day interaction. This stage embodies the interface between the supplier and the customer during the collaborative work. This is the daily work. The last columns of Table 3 andTable 4 indicate the novelty of the failure observed compared to failures observed in our literature review. failures were not observed per se in the articles we have considered. However, some authors have mentioned the corresponding issues or have tried to explain the causes of those failures. The results of those authors will bring complements in the following discussion.

-Technical content failures Failures related to technical content were consequently reported in literature but the raisons observed during project P were not found in the literature review. Indeed, the ROLMO project team encountered difficulties to specify the technical requirements as the technology sought was not in its core competencies. In this respect, [START_REF] Stephan | Integration of suppliers into the product development process using the example of the commercial vehicle industry[END_REF] say that more than 30% of the reasons for project failures are associated with the requirements definition. Time would have been necessary to wonder what the competencies to ask to the supplier were but it was not the case. This led to misunderstandings from the Supplier CAB and an inappropriate answer. Furthermore, supplier CAB did not have the necessary R&D capacities to ensure the required development. But as the ROLMO project team was not very accurate about the real expectations, they were incapable of detecting the absence of necessary R&D capacities during the supplier CAB audit. Thus, supplier CAB's development capacity was over-estimated. For [START_REF] Lee | Interfirm Innovation under Uncertainty: Empirical Evidence for Strategic Knowledge Partitioning[END_REF] who have examined the development of automotive emission control technologies over a 28-year period, the problem might be explained by differences of knowledge framework that lead to misunderstandings between the customer and the supplier. Suppliers dominate component innovation whereas assemblers focus more on architectural innovation.

-Supplier choice and status failures This failure was not reported in our literature review. For the choice of the supplier, several suppliers were short listed. Difficulties were encountered internally at the Company ROLMO to choose the appropriate supplier. The project team and the purchasing project manager visions were not in accordance with the commodity manager vision for the supplier selection. As the cable is the most important part in the overall cost, a choice of a cable supplier was privileged. Nevertheless, the expertise is on the connector part. Supplier CAB was already in the supplier base for cable supply and it was an historical and trustworthy supplier. The commodity manager has influenced this choice because of the current development project concerning a manufacturing plant in a low cost country with this supplier. The project team had carried out an audit to evaluate the ability of the supplier to co-design. The results of this audit pointed out an uncertainty related to the ability of Supplier CAB to bring in the necessary R&D resources within a new product development project. On the whole everybody agreed with this supplier choice but specified that it was more a compromise than an appropriate answer to the project needs. Finally, the historical relationship with this supplier and its manufacturing abilities prevailed upon its co-design abilities. During the pre-study stage, the supplier was not able to bring in its R&D resources. After several demands of improvement on this point without results, the customer team decided to change the supplier. One year of work was lost. Literature has largely explored the supplier selection topic in NPD [START_REF] Schiele | How to distinguish innovative suppliers? Identifying innovative suppliers as new task for purchasing[END_REF][START_REF] Humphreys | Integrating design metrics within the early supplier selection process[END_REF][START_REF] Emden | Collaborating for New Product Development: Selecting the Partner with Maximum Potential to Create Value[END_REF] but the actors' point of view divergence in a new product development project was not considered.

-Procedural coordination failures Problems were encountered in the communication of the customer's quality expectations. ROLMO was going to set up a very demanding new quality tool to assess the quality of the propositions made by its suppliers during the relationship lifecycle. CAB was not in accordance with this new tool that was judged too demanding. Furthermore, there was no project manager in the CAB project team at the beginning of the project. Product innovation and quality were affected by all those circumstances. The proposed solution did not present real innovation or optimisation. The level of propositions made by the supplier concerning the solution was judged below what was expected. Another point is that all the actors are not always present at the meetings to internal advancement or to prepare a supplier meeting. It can lead to coordination problems and sometimes the mechanical engineer for instance does not know that some points were already treated or validated with the supplier with the supplier quality assessment actor for instance. Therefore, time is lost and customer team may become incredible by the supplier.

In addition, all actors involved in a project (engineers, purchasing actors, quality actors…) do not progress with the same speed which can lead to bottleneck in the validation of project toll gates. For [START_REF] Dowlatshahi | Designer-buyer-supplier interface: Theory versus practice[END_REF] who studied ESI and used a case study method in a medical manufacturing company for an in-depth analysis and propositions testing about the designer-buyer-supplier interface, supplier meetings are the core of buyer-supplier relationships. The level, frequency, and personal involvement of the designer and buyer largely determines the success of supplier meetings and training programs and the success of supplier meetings is largely dependent upon the success of information sharing. Furthermore, the relationships between buyers and suppliers must be based on confidence and trust. There must be a free flow and information sharing between actors in product design.

-Communication failures Some failures were observed during our case study about communication aspects and not noticed in the literature. At first, the ROLMO project team complained of a lack of checkout that the supplier ability during the project is in accordance with the supplier ability detected by the audit team. Sometimes, the audit team is not involved in the project team and it should be checked that the daily project experience confirm the supplier skills. Secondly, some key performance indicators (KPIs) exist in each project but some team members do not know their existence or do not know where to find them. Therefore, they are not used except from the person who creates them. [START_REF] Dowlatshahi | Designer-buyer-supplier interface: Theory versus practice[END_REF] stated that communication is usually a symptom and not the cause of many problems. Thus, it is generally futile to try to improve communication and dialogue if other aspects of the relationships are not fully mastered. In this respect, [START_REF] Maier | Improving communication design: recommandations from the literature[END_REF], who performed a literature review in order to improve communication in design, recommend to share information to improve communication. This information sharing practice must be set up at the early stages of a project both for internal and external communication.

Conclusion and future research

This paper proposes a list of failures issued from a literature review on new product development in collaboration with supplier. This list was consolidated and enriched with the results of an in-depth case study. From this list of failures, six classes of failures encountered during collaborative development with suppliers were introduced. Those classes are inspired from topics considered as key topics in ESI literature. This categorisation is going to be presented and discussed with industrial actors to benefit from their point of view. Those results have to be generalized with other case studies. In this respect, six case studies have already been carried out and two others are in course. Another future research avenue would be to test the ability of the failures model to explain the success of a co-development project.

••

  Strategic alignment: motivation; goal convergence • Technological alignment • Relational alignment: mindset (industrial or culture)Interpretation and understanding • Information sharing and lessons learned • Internal and external communication 6Communication

Table 1 :

 1 Failures in NPD with suppliers identified

in literature Author Method Failure Failure related to an i ssue i n (sub-class)

	Dowlatshahi, 2000	9 propositions tested with a case st udy in a medical manufact uring company	T he depth and breadth of information sharing between the company ant its largely shallow, insignificant, and superficial suppliers, especially at the early stages of the product design cycle, were	Information sharing
			Problem wit h external cooperation in PD	Internal collaboration
			Non adapted boundary persons (people that transfer information between organizat ional groups or between organizations)	Internal & ext ernal communication
			T oo many boundary persons	Internal & ext ernal communication
			Ext remely short lead times. No coordination on lead t imes	Detailed planning
			Not enough standardizat ion, which increases cost.	Optimisation of product cost
			Specifications are too general. T hey do not cover the requirements of the part in question.	Specifications definit ion
			T here are a lot of opportunities to add more costs	Optimisation of product cost
			T here is a lot of overspecification, which increases the cost. For example:
			the tolerances are too narrow; Some of the criteria are well beyond the life	Optimisation of product cost
			usage of the product
			In t he worst case, suppliers do not even read t he specifications properly	Supplier participation in t he specification proces
			Even when it is very urgent , some specifications are missing. For inst ance tolerances and dimensions are missing.	Specifications definit ion
			Some specifications are non adapted to the supplier capacities	Specifications definit ion
			Internal functional conflicts. Ambiguous specifications.	Specifications definit ion
			Suppliers' role was often far from clear within the OEM	Roles and responsibilities

All funct ions are not agree on the specific act ion outline. Contradictory messages are given to the different suppliers.

Internal and external communicat ion T he original equipment manufacturer does not give reasons for changes in specifications to the supplier Specifications modification Specifications keep changing all the time Specifications modification

Table 1 (

 1 continued): Failures in NPD with suppliers identified in literature

	Information sharing

Additional failures observed

Among the failures observed during this case study, some of them were not noticed during our literature review. We explain below the additional failures compared to literature results. Those


Miguel Couceiro
email: miguel.couceiro@uni.lu

Michel Grabisch
email: michel.grabisch@univ-paris1.fr

On the poset of computation rules for nonassociative calculus

Keywords: symmetric maximum, nonassociative algebra, computation rule, partially ordered set

The symmetric maximum, denoted by , is an extension of the usual maximum ∨ operation so that 0 is the neutral element, and -x is the symmetric (or inverse) of x, i.e., x (-x) = 0. However, such an extension does not preserve the associativity of ∨. This fact asks for systematic ways of parenthesing (or bracketing) terms of a sequence (with more than two arguments) when using such an extended maximum. We refer to such systematic (predefined) ways of parenthesing as computation rules.

As it turns out there are infinitely many computation rules, each of which corresponds to a systematic way of bracketing arguments of sequences. Essentially, computation rules reduce to deleting terms of sequences based on the condition x (-x) = 0. This observation gives raise to a quasi-order on the set of such computation rules: say that rule 1 is below rule 2 if for all sequences of numbers, rule 1 deletes more terms of the sequence than rule 2.

In this paper we present a study of this quasi-ordering of computation rules. In particular, we show that the induced poset of all equivalence classes of computation rules is uncountably infinite, has infinitely many maximal elements, has infinitely many atoms, and it embeds the powerset of natural numbers ordered by inclusion.

Introduction

Among the wide variety of algebraic structures sofar studied in the realm of aggregation theory, only a few have been considered with nonassociative fundamental operations; see e.g. [START_REF] Baets | The quest for rings on bipolar scales[END_REF][START_REF] Grabisch | The symmetric Sugeno integral[END_REF][START_REF] Grabisch | The Möbius transform on symmetric ordered structures and its application to capacities on finite sets[END_REF][START_REF] Grabisch | Theory and Applications of Relational Structures as Knowledge Instruments II[END_REF][START_REF] Pap | Pseudo-integral based on non-associative and noncommutative pseudo-addition and pseudo-multiplication[END_REF], see also [START_REF] Grabisch | Aggregation functions[END_REF] for a recent reference. If commutativity, distributivity, and existence of neutral element and of symmetric element, etc., are often abandonned, associativity remains a desirable property in order to avoid ambiguities when assessing the outcome of composed computations within the algebraic structure. However, in certain situations such nonassociative operations are both natural and necessary: this is the case of the symmetric maximum [START_REF] Grabisch | The symmetric Sugeno integral[END_REF][START_REF] Grabisch | The Möbius transform on symmetric ordered structures and its application to capacities on finite sets[END_REF].

For a preliminary discussion, consider the set N of nonnegative integers and the maximum operation ∨ defined on it. Let us try to build on Z an operation behaving like a group addition but coinciding with ∨ on the positive side, that is, for every a, b ∈ Z, a a = a (idempotency), a 0 = 0 a = a (neutral element), a (-a) = 0 (symmetry),

a b = a ∨ b if a, b
0. If such an operation exists, it is necessarily nonassociative as shown below:

-3 (3 2) = -3 3 = 0

(1) (-3 3) 2 = 0 2 = 2.

(

) 2
One can show [START_REF] Grabisch | The symmetric Sugeno integral[END_REF] that the best definition (in the sense that it fails associativity on the smallest possible domain) of is given by:

a b =    -(|a| ∨ |b|) if b = -a and |a| ∨ |b| = -a or = -b 0 if b = -a |a| ∨ |b| otherwise. (3)
Except for the case b = -a, a b equals the element among the two that has the greatest absolute value. The main problem is how to interpret this nonassociative operation when evaluating expressions like n i=1 a i , as it was the case in [START_REF] Grabisch | The Möbius transform on symmetric ordered structures and its application to capacities on finite sets[END_REF]. The solution proposed in [START_REF] Grabisch | The symmetric Sugeno integral[END_REF][START_REF] Grabisch | The Möbius transform on symmetric ordered structures and its application to capacities on finite sets[END_REF] was to define computation rules, that is, to define systematic ways of putting parentheses so that no ambiguity occurs. Since we deal with commutative operations, a simple example of a computation rule is the following: put parentheses around each pair of maximal symmetric terms. If we apply this to our example above, this rule corresponds to [START_REF] Baets | The quest for rings on bipolar scales[END_REF]. Another one is to make the computation separetely on positive and on negative terms, and to aggregate the result: ( i a + i ) ( i a - i ). This corresponds to [START_REF] Blyth | Lattices and Ordered Algebraic Structures[END_REF]. It is easy to see that there are many possible computation rules, but to study them, one needs to formalize the intuitive idea of a computation rule. The aim of this paper is twofold: to propose a formal definition of a computation rule, which was lacking in [START_REF] Grabisch | The symmetric Sugeno integral[END_REF], and to study the set of all computation rules endowed with a very natural ordering. As we will see, the poset of computation rules induced by this ordering is uncountable; in fact, from Corollary 24 below, it follows that this poset is equimorphic (equivalent with respect to embeddability) to the power set of positive integers ordered by inclusion. Moreover, we show that the poset of computation rules has infinitely many atoms and has infinitely many maximal elements; these are completely described in Subsections 4.3 and 4.4.

Throughout the paper, we adopt the following notation: if Z is a set of symbols, then L(Z) denotes the language (set of words, including the empty word ε) built on the alphabet Z.

The symmetric maximum

In this section we recall basic concepts and preliminary results needed hereinafter (for further developments see [START_REF] Grabisch | The symmetric Sugeno integral[END_REF][START_REF] Grabisch | The Möbius transform on symmetric ordered structures and its application to capacities on finite sets[END_REF] and [8, §9.3]). However, we assume that the reader is familiar with elementary notions in the theory of ordered sets, and refer the reader, e.g., to [START_REF] Blyth | Lattices and Ordered Algebraic Structures[END_REF][START_REF] Caspard | Les ensembles ordonnés finis : concepts, résultats et usages[END_REF][START_REF] Davey | Introduction to Lattices and Order[END_REF] for basic background.

Let C be a chain endowed with an order and least element 0, and let C -= {-c : c ∈ C} be its dually isomorphic copy, which we refer to as its symmetric counterpart.

We define C = C ∪ C -, and set -0 = 0. Since we will only consider countable sequences of elements of C, without loss of generality, we may assume that C = Z, or a finite symmetric interval of it.

Let us introduce a binary operation on C fulfilling the following independent conditions:

(I) coincides with ∨ on C 2 .
(II) -a is the symmetric of a, i.e., a (-a) = 0.

(III) -(a b) = (-a) (-b) for all a, b ∈ C.
As observed in Section 1, (I) and (II) imply that is not associative. Note also that from (III), it follows that coincides with the minimum on C -. The following results are not difficult to verify. Proposition 1. Under the conditions (I), (II) and (III) above, no operation is associative on a larger domain than that on which the symmetric maximum defined by (3) is associative.

Proposition 2. The symmetric maximum has the following properties:

(i) is commutative on C.
(ii) 0 is the neutral element of .

(iii) is associative on an expression involving a 1 , . . . , a n ∈ C, with |{i :

a i = 0}| > 2, if and only if n i=1 a i = -n i=1 a i . (iv)
is nondecreasing in each argument on C.

See [START_REF] Grabisch | The Möbius transform on symmetric ordered structures and its application to capacities on finite sets[END_REF] for a proof. For the sake of completeness, and since this result in central in the paper, we give an alternative proof of (iii).

Proof. We show that (iii) holds. To show that the condition is necessary, suppose that n i=1 a i = -n i=1 a i , and let 1 ≤ j, k ≤ n be such that a j = n i=1 a i and a k = n i=1 a i .

If there exists 1 ≤ t ≤ n such that 0 < a t < a j , then

( i: 0<a i ≤at a i ) ( i: a i >at a i ) ( i: a i ≤0 a i ) = i: 0<a i ≤at a i > 0.
However, ( i: a i >0 a i ) ( i: a i ≤0 a i ) = 0, and hence is not associative. The case when there exists 1 ≤ t ≤ n such that a k < a t < 0 follows similarly.

Therefore we assume that for every 1 ≤ i ≤ n, if a i > 0, then a i = a j , and if a i < 0, then a i = a k . Since |{i : a i = 0}| > 2, we have |{i :

a i = a j }| > 1 or |{i : a i = a k }| > 1.
Without loss of generality, suppose that the former holds, and let 1 ≤ t ≤ n, t = j, such that a t = a j . In this case, we have

a t ( i: i =t a i >0 a i ) ( i: a i ≤0 a i ) = a t > 0,
but ( i: a i >0 a i ) ( i: a i ≤0 a i ) = 0, and hence is not associative.

To show that the condition is sufficient, suppose that n i=1 a i = -n i=1 a i . We consider the case a j = n i=1 a i > -n i=1 a i ; the other case follows similarly. By (3), a j a i = a j for every 1 ≤ i ≤ n, and thus no matter how we parenthesize a 1 , . . . , a n using , we always obtain a j . Hence, is associative. Property (iii) of Proposition 2 will be the basis for defining computation rules.

Computation rules

The lack of associativity of induces ambiguity when evaluating expressions like n i=1 a i . To overcome this difficulty, computation rules were proposed in [START_REF] Grabisch | The symmetric Sugeno integral[END_REF][START_REF] Grabisch | The Möbius transform on symmetric ordered structures and its application to capacities on finite sets[END_REF], and that amount to eliminating situations where nonassociativity occurs, as characterized by property (iii) in Proposition 2.

Given a sequence (a i ) i∈I with I ⊆ N, we say that it fulfills associativity if either |I| 2 or i∈I a i = -i∈I a i . Hence i∈I a i is well-defined if and only if (a i ) i∈I fulfills associativity. Informally speaking, a computation rule is a systematic (predefined) way to delete symbols in a sequence in order to make it associative, provided that this corresponds to some arrangement of parentheses.

Example 3. Consider the following sequence in Z: 3, 2, 1, 0, -2, -3, -3. A possible way to make the sequence associative is to delete 3, -3, which corresponds to the arrangement

(3 -3) (-3 2 -2 1 0) = -3.
Another possibility is to delete all occurrences of maximal symmetric symbols, that is, first 3, -3 then 2, -2, which corresponds to:

(3 (-3 -3)) (2 -2) 1 0 = 1.
Even though deleting the 3 makes this sequence associative, it does not correspond to any arrangement of parentheses.

In this section we reassemble these ideas and propose a formalism where the intuitive idea of a computation rule is made precise, and show that our formalization fulfills our initial requirements.

Since 0 is the neutral element of , we deal with sequences (words) built on Z = C \ {0}, including the empty sequence ε. Hence, we consider the language L(Z). Nonempty words are denoted by σ = (a i ) i∈I , where I is a finite index set.

We are interested in computing expressions i∈I a i unambiguously. Since is commutative, the order of symbols in the word does not matter, and we can consider any particular ordering of the word, like the decreasing order of the absolute values of the elements in the sequence:

(1, 3, -2, -3, 3, 1, 2) → (3, 3, -3, 2, -2, 1, 1).
Hence, we do not deal with words, but with such ordered sequences. We denote by S the set of all such sequences. We introduce a convenient and unambiguous encoding of sequences, based on two mappings. The mapping θ assigns to every σ ∈ S, the list of the absolute values in σ in decreasing order:

θ(σ) = (n 1 , . . . , n q ).
We assume that θ(σ) is always a finite sequence of arbitrary length. The mapping ψ :

S → ∪ i∈N (N 2 0 ) i is defined by: ψ((a i ) i∈I ) = ((p 1 , m 1 ), . . . , (p q , m q ))
where p k , m k are the numbers of occurrences of the k-th greatest absolute value of elements in the sequence, p k being for the positive element, and m k for the negative one. In other words, for θ(σ) = (n 1 , . . . , n q ), the sequence σ can be rewritten after reordering as:

σ = (n 1 , . . . , n 1 p 1 times , -n 1 , . . . , -n 1 m 1 times
, . . . , n q , . . . , n q pq times , -n q , . . . , -n q mq times ).

Note that no pair in ψ(σ) can be (0, 0).

Example 4. Consider the sequence σ = (1, 3, -3, 2, -2, -2, 3, 1, 1, 1). Then θ(σ) = (3, 2, 1) ψ(σ) = ((2, 1), (1, 2), (4, 0)).
Note that θ(σ) and ψ(σ) uniquely determine σ. Also, saying that σ fulfills associativity means that either p 1 or m 1 is 0. We denote by S 0 the set of sequences which do not fulfill associativity. Definition 5. There exist five elementary rules ρ i : S → S, defined as follows. For any sequence σ with ψ(σ) = ((p k , m k ) k=1,...,q ):

(i) elementary rule ρ 1 : if p 1 > 1 and m 1 > 0, the number p 1 is changed into p 1 = 1; (ii) elementary rule ρ 2 : if m 1 > 1 and p 1 > 0, the number m 1 is changed into m 1 = 1; (iii) elementary rule ρ 3 : if p 1 > 0, m 1 > 0, the pair (p 1 , m 1 ) is changed into (p 1 -c, m 1 - c), where c = p 1 ∧ m 1 .
If this results in the pair (0,0), then this pair is deleted, and all subsequent pairs (p k , m k ), k = 2, 3, . . ., are renumbered as (p k-1 , m k-1 ).

(iv) elementary rule ρ 4 : if p 1 > 0, m 1 > 0, and if p 2 > 0, the number p 2 is changed into p 2 = 0. If this results in the pair (0,0), then this pair is deleted, and all subsequent pairs (p k , m k ), k = 3, 4, . . ., are renumbered as (p k-1 , m k-1 ).

(v) elementary rule ρ 5 : if p 1 > 0, m 1 > 0, and if m 2 > 0, the number m 2 is changed into m 2 = 0. If this results in the pair (0,0), then this pair is deleted, and all subsequent pairs (p k , m k ), k = 3, 4, . . ., are renumbered as (p k-1 , m k-1 ).

Rules ρ 1 , . . . , ρ 5 have no action (i.e., ρ i (σ) = σ) if the conditions of application are not satisfied.

We define the (computation) alphabet as Ψ = {ρ 1 , ρ 2 , ρ 3 , ρ 4 , ρ 5 }. Definition 6. A computation rule R is any word built on Ψ, i.e., R ∈ L(Ψ). We say that R is a well-formed computation rule (w.f.c.r.) if for any sequence σ ∈ S we have R(σ) ∈ S \ S 0 . We denote by R the set of well-formed computation rules.

For example, ρ 2 ρ 3 ρ 1 , ρ * 4 ρ 1 , (ρ 1 ρ 3 ) * (ρ 4 ρ 5 ) * are computation rules, where as usual w * denotes the infinite concatenation wwwww • • • of the word w (we recall that words are read from left to right). Observe that only the two latter rules are well-formed.

Note that from Definition 5, we have R(σ) = σ for any rule R and any sequence σ in S \ S 0 . We give examples of w.f.c.r.'s that include those already proposed in [START_REF] Grabisch | The symmetric Sugeno integral[END_REF] (we leave to the reader the proof that they are well-formed):

(i) • 0 = ρ * 3 , (ii) • = = (ρ 1 ρ 2 ρ 3 ) * , (iii) • + -= (ρ 4 ρ 5 ) * • = = (ρ 4 ρ 5 ) * ρ 1 ρ 2 ρ 3 , (iv) • pess = (ρ 4 ρ 5 ) * ρ 1 ρ 3 , (v) • opt = (ρ 4 ρ 5 ) * ρ 2 ρ 3 , (vi) • L = (ρ 1 ρ 3 ) * , (vii) • R = (ρ 2 ρ 3 ) * .
Note that σ + -= ε for all σ ∈ S 0 . We use (R(σ)) to denote the value of i∈I a i after applying the computation rule R ∈ R to ψ(σ) = ψ((a i ) i∈I ). To compute (R(σ)), one needs to delete symbols in the sequence θ(σ) exactly as they are deleted in ψ(σ). We say that R, R ′ ∈ R are equivalent, denoted by R ∼ R ′ , if for any sequence σ ∈ S we have (R(σ)) = (R ′ (σ)).

The next fundamental theorem shows that our setting covers all possible ways of putting parentheses on words in L(Z) in order to make them associative 1 . Theorem 7. Any computation rule applied to some σ ∈ S corresponds to an arrangement of parentheses and a permutation on σ. Conversely, any arrangement of parentheses and permutation on some σ ∈ S making the sequence associative is equivalent to a computation rule applied to σ.

Proof. Let us define 5 basic rules applied on any sequence σ with ψ(σ) = (p k , m k ) k∈K as follows:

(i) basic rule ρ ′ k 1 , for a given k ∈ K: if p k > 1, the number p k is changed into p k -1; (ii) basic rule ρ ′ k 2 , for a given k ∈ K: if m k > 1, the number m k is changed into m k -1; (iii) basic rule ρ ′ k 3 , for a given k ∈ K: if p k > 0, m k > 0, the pair (p k , m k ) is changed into (p k -1, m k -1); (iv) basic rule ρ ′ k 4 , for k > 1: if p k > 0, the number p k is changed into p k -1; (v) basic rule ρ ′ k 5 , for k > 1: if m k > 0, the number m k is changed into m k -1,
For all these rules, if a pair (0,0) appears, it is immediately deleted. Observe that the elementary rules are concatenations of the above basic rules. Indeed, we have:

ρ 1 = (ρ ′ 1 1 ) * , ρ 2 = (ρ ′ 1 2 ) * , ρ 3 = (ρ ′ 1 3 ) * , ρ 4 = (ρ ′ 2 4 ) * , ρ 5 = (ρ ′ 2
ρ ′ k 4 (if a > 0) or ρ ′ k 5 (if a < 0) for a suitable k. Claim 2. Given a sequence σ ∈ S 0 , for any rule ρ in L({ρ ′ k 1 , . . . , ρ ′ k 5 } k∈N ) making σ associative, there exists a computation rule R in L(Ψ) such that (ρ(σ)) = (R(σ)).
Proof of Claim 2. We have already established that any elementary rule is a particular rule in L({ρ ′ k 1 , . . . , ρ ′ k 5 } k∈N ), and therefore this is true also for any computation rule in L(Ψ).

Take then any rule ρ in L({ρ ′ k 1 , . . . , ρ ′ k 5 } k∈N ) making σ associative. The result (ρ(σ)) is some number in σ, say δn k , with δ = 1 or -1 (i.e., the kth positive or negative symbol in θ(σ)). Let us construct a computation rule R such that (R(σ)) = δn k as follows:

• Suppose k = 1, δ = 1 (provided p 1 > 1). Then R = ρ 2 ρ 3 . For the case δ = -1, we find R = ρ 1 ρ 3 .

• Suppose k > 1, δ = 1 (provided p k > 0) or δ = -1 (provided m k > 0). Apply the following algorithm:

-Initialization: R ← ε

-For i = 2 to k -1, Do: * If p i = 0 put R ← Rρ 5 * If m i = 0 put R ← Rρ 4 * Otherwise put R ← Rρ 4 ρ 5 -Case δ = 1: if m k > 0, R ← Rρ 5 .
-

Case δ = -1: if p k > 0, R ← Rρ 4 . -R ← Rρ 1 ρ 2 ρ 3
By construction, R is equivalent to ρ on σ, and the proof of the claim is now complete.

Theorem 7 now follows from Claims 1 and 2.

Remark 8. Note that a well-formed rule in L({ρ ′ k 1 , . . . , ρ ′ k 5 } k∈N ) (i.e., making any σ associative) is not necessarily equivalent to a w.f.c.r. in R. For instance, consider the well-formed rule ρ = ρ ′ 3 5 ((ρ

′ 1 1 ) * (ρ ′ 1 2 ) * ρ ′ 1
3 ) * , and apply it on the sequences:

σ = (2, 3)(1, 0)(0, 1)(2, 1), σ ′ = (2, 3)(1, 1)(0, 1)(2, 0).
Then (ρ(σ)) = n 2 and (ρ(σ ′ )) = n 4 . Let us try to build an equivalent w.f.c.r. R ∈ R . Since the second pair in σ is the final result, one cannot touch it. Therefore, R contains only ρ 1 , ρ 2 , ρ 3 , and thus one finds -n 3 on σ ′ . Hence, compositions of basic rules may result in rules more general than our computation rules. However, those rules that are not computation rules are rather artificial.

Hereinafter, we will make use of the following "factorization scheme" for computation rules.

Lemma 9. Let R be a w.f.c.r. in R.

(i) Factorization: Rule R can be factorized into a composition

R = T 1 T 2 • • • T i • • • (4)
where each term has the form

T i = ω i ρ a i 1 ρ b i 2 ρ 3 , with ω i ∈ L({ρ 4 , ρ 5
}) (possibly empty), and a i , b i ∈ {0, 1}.

(ii) Simplification: Suppose that in (4) there exists j ∈ N such that ω j = ωρ * 4 or ωρ * 5 for some ω ∈ L({ρ 4 , ρ 5 }), or that ρ 4 and ρ 5 alternate infinitely many times in ω j . Let k 1 = min{j : ω j = ωρ * 4 or ωρ * 5 }, and k 2 = min{j : ρ 4 and ρ 5 alternate infinitely many times in ω j }.

• If k 1 < k 2 , then R ∼ T 1 • • • T k 1 . • Otherwise, k 2 k 1 , and R ∼ T 1 • • • T ′ k 2 , where T ′ k 2 = (ρ 4 ρ 5 ) * ρ a k 2 1 ρ b k 2 2 ρ 3 .
Proof. Let R be a w.f.c.r. Then R is necessarily infinite, otherwise one can always construct a sequence σ such that R(σ) ∈ S \ S 0 . Also, ρ 3 necessarily belongs to R, otherwise the sequence σ with ψ(σ) = (2, 1) would not be made associative by R. Therefore, the word R can be cut into terms where ρ 3 acts as a separator, i.e., R = R

1 ρ 3 R 2 ρ 3 • • • , with R i ∈ L({ρ 1 , ρ 2 , ρ 4 , ρ 5 }
). Now observe that ρ 1 and ρ k 1 are equivalent for any k > 1, and the same holds for ρ 2 . Moreover, the order between ρ 1 , ρ 2 and ω i is unimportant because none of these symbols can make the sequence σ associative (i.e., the rule will not stop after applying these elementary rules), and each of them applies on a different symbol of σ. This proves that each term T i can be written in form [START_REF] Davey | Introduction to Lattices and Order[END_REF].

Observe that since R is infinite, there can be infinitely many factors T i or finitely many, provided one factor T i has an infinite ω i . In the first case, there is no last factor and the proof of (i) is complete. In the second case, it remains to prove that the last factor T l has the same form, i.e., it ends with ρ 3 . Suppose on the contrary that there are elementary rules ρ 4 , ρ 5 after ρ 3 . If σ is made associative after applying ρ 3 , then the rule stops and the remaining ρ 4 , ρ 5 are useless. If not, it is because ρ 3 has acted on a pair (p, p) with p > 0. But if the next pair is, say, (1,1), σ will not be made associative by the remaining ρ 4 , ρ 5 , contradicting the fact that R is well-formed.

Let us prove (ii). Suppose first that k 2 k 1 . Observe that any ω i where ρ 4 , ρ 5 alternate infinitely many times is equivalent to (ρ 4 ρ 5 ) * . Moreover, (ρ 4 ρ 5 ) * deletes all pairs after the current one. Therefore, it remains only the current pair, and ρ

a k 2 1 ρ b k 2 2 ρ 3 necessarily stops on it, for any value of a k 2 , b k 2 .
Suppose now that k 1 < k 2 , and ω k 1 = ωρ * 4 (the other case is similar). Then ρ * 4 deletes all pairs after the current pair of the form (p ′ , 0), and stops at the first pair of the form (p ′ , m ′ ) with m ′ > 0, which is transformed into (0, m ′ ). Then ρ

a k 1 1 ρ b k 1
2 ρ 3 makes the current pair either of the form (0, 0), or (p, 0) or (0, m). In the two last cases, R stops. In the first case, the current term is deleted, and the next pair encountered is (0, m ′ ), where the rule stops. The proof of (ii) is now complete.

Remark 10. Note that (ii) of Lemma 9 does not refer to every ω containing a ρ * 4 or a ρ * 5 . For instance, if ω = ρ 5 ρ * 4 ρ 5 , then the subsequent terms of R are relevant.

Remark 11. If T i = ω i ρ a i 1 ρ b i 2 ρ 3
, where ω i = (ρ 4 ρ 5 ) * , ωρ * 4 , ωρ * 5 , for any ω ∈ L({ρ 4 , ρ 5 }), then there is σ i such that T i (σ i ) = ε and T i (σ i σ) = σ for every σ ∈ S.

We refer to the compositions given in (ii) as factorized irredundant forms of computation rules. For instance, • + -can be factorized into two equivalent compositions

• + -= (ρ 4 ρ 5 ) * (ρ 1 ρ 2 ρ 3 ) * = (ρ 4 ρ 5 ) * ρ 1 ρ 2 ρ 3 .
but only the second is a factorized irredundant form. Note that our previous examples of w.f.c.r.'s are given in factorized irredundant forms. Now it is natural to ask whether two equivalent rules have necessarily the same factorized irredundant form. The next proposition shows that there is a unique factorized irredundant form for each equivalence class of computation rules.

Proposition 12. Let T = T 1 • • • T n and T ′ = T ′ 1 • • • T ′
m be two rules in factorized irredundant form, where n, m may be infinite. Then T ∼ T ′ if and only if n = m and for every 1 i n, T i = T ′ i .

Proof. Clearly, the conditions are sufficient. So let us prove that they are also necessary. First, we show that n = m. For a contradiction, suppose that n = m, say n < m. In particular, for every j < m, ω ′ j is not of the ωρ * 4 nor ωρ * 5 form for any ω ∈ L({ρ 4 , ρ 5 }), and ω ′ j = (ρ 4 ρ 5 ) * . Note that (a 1 , b 1 ) = (a ′ 1 , b ′ 1 ), otherwise T ∼ T ′ (just consider (2, 1), (2, 2), or (1, 2)). Thus, to verify that T 1 = T ′ 1 , it suffices to show that ω 1 = ω ′ 1 . Let p and p ′ be the number of times that ρ 4 and ρ 5 alternate in ω 1 and ω ′ 1 , respectively. It is easy to see that p = p ′ (just consider sequences of the form (1, 1)(1, 0) a (0, 1)[(1, 0)(0, 1)] q (1, 0)(0, 1) b , for suitable a, b ∈ {0, 1} and q ∈ N). Moreover, either both start with ρ 4 or both start with ρ 5 (just consider strings of the form (1, 1)[(1, 0)(0, 1)] p ).

So suppose both start with ρ 4 and p = 2t -1 (the case p = 2t is similar), say

ω 1 = ρ l 1 4 ρ r 1 5 • • • ρ lt 4 ρ rt 5 and ω ′ 1 = ρ l ′ 1 4 ρ r ′ 1 5 • • • ρ l ′ t 4 ρ r ′ t 5
where r t , r ′ t = 0, and let k = min{j : l j = l ′ j or r j = r ′ j }, say l k < l ′ k (the other cases are dealt with similarly). Then, for

σ = (1, 1)[(1, 0)(0, 1)] k-1 (1, 0) l k +1 (0, 1)[(1, 0)(0, 1)] t-k (T (σ)) > (T ′ (σ)), which contradicts T ∼ T ′ . Hence, ω 1 = ω ′
1 , and we conclude

T 1 = T ′ 1 .
In fact, following exactly the same steps, one can verify that

T i = T ′ i , for every i < n. Now, as in the case above (a n , b n ) = (a ′ n , b ′ n ), otherwise T ∼ T ′ . Moreover, by assumption, we have that ω n = ωρ * 4 or ωρ * 5 for some ω ∈ L({ρ 4 , ρ 5 }) \ {(ρ 4 ρ 5 ) * }, or that ω n = (ρ 4 ρ 5 ) * . Since ω ′ n = (ρ 4 ρ 5 ) * , ω n = (ρ 4 ρ 5 ) * .
Hence, ρ 4 and ρ 5 must alternate the same number of times, say

ω n = ρ l 1 4 ρ r 1 5 • • • ρ lt 4 ρ rt 5 and ω ′ n = ρ l ′ 1 4 ρ r ′ 1 5 • • • ρ l ′ t 4 ρ r ′ t 5 ,
where either l t = * = l ′ t and r t = r ′ t = 0, or r t = * = r ′ t and l t , l ′ t > 0. Without loss of generality, suppose that the latter holds. Then, for

σ = (1, 1)[(1, 0)(0, 1)] n-1 (1, 0)(0, 1) r ′ t +1
(T (σ)) < (T ′ (σ)), again a contradiction. Using Lemma 9 (ii), we see that all possible cases have been considered and, since each leads to a contradiction, we have n = m. Now, by making use of (concatenations of) sequences of the form

(1, 1)(1, 0) a (0, 1)[(1, 0)(0, 1)] q (1, 0)(0, 1) b (2, 1) c (2, 2) d (1, 2) e ,
if both have infinitely many terms T i , T ′ i , then T i = T ′ i for every i ∈ N, and if T and T ′ have the same (finite) number of terms, say n, then T i = T ′ i for every i < n, and (a n , b n ) = (a ′ n , b ′ n ). Thus, to complete the proof it remains to show that in the latter case, we have ω n = ω ′ n ; in fact, both ω n and ω ′ n are (ρ 4 ρ 5 ) * , or ωρ * 4 or ωρ * 5 for some ω ∈ L({ρ 4 , ρ 5 })\{(ρ 4 ρ 5 ) * }. For the sake of a contradiction, suppose first that ω n = (ρ 4 ρ 5 ) * but ω ′ n = ωρ * 4 or ω ′ n = ωρ * 5 where ρ 4 and ρ 5 alternate finitely many times in ω, say p times. Then

(T (σ(1, 1)[(1, 0)(0, 1)] p+2 )) < (T ′ (σ(1, 1)[(1, 0)(0, 1)] p+2 )),
where σ is the concatenation of the sequences σ i , 1 i < n, given in Remark 11. Now suppose that ω n = ωρ * 4 and ω ′ n = ω ′ ρ * 5 where ρ 4 and ρ 5 alternate finitely many times in ω and ω ′ , say p and p ′ times, respectively. (The remaining cases can be dealt with similarly.) Without loss of generality, suppose that p p ′ , then taking a as the ceiling of p 2 we have • (T (σ(1, 1)[(1, 0)(0, 1)] a (0, 1))) > (T (σ(1, 1)[(1, 0)(0, 1)] a (0, 1))), if ω and ω ′ both start with ρ 4 or ρ 5 , or ω and ω ′ start with ρ 5 and ρ 4 , respectively, and

• (T (σ(1, 1)(0, 1)[(1, 0)(0, 1)] a (0, 1))) > (T (σ(1, 1)(0, 1)[(1, 0)(0, 1)] a (0, 1))), if ω and ω ′ start with ρ 4 and ρ 5 , respectively, where again σ is the concatenation of the sequences σ i , 1 i < n, given in Remark 11. Since both cases yield the desired contradiction, the proof is now complete. [START_REF] Davey | Introduction to Lattices and Order[END_REF] The poset (R/ ∼ , ) of computation rules

The above considerations allow us to focus on the quotient R/ ∼ of equivalence classes rather than on the whole set of w.f.c.r.'s. Moreover, by making use of Lemma 9, we can focus on factorized irredundant forms.

We consider the following order on R/ ∼ , which was introduced in [START_REF] Grabisch | The symmetric Sugeno integral[END_REF]. Let R, R ′ be two computation rules in R/ ∼ and, for each sequence σ = (a i ) i∈I , let J σ and J ′ σ , J σ , J ′ σ ⊆ I, be the sets of indices of the terms in σ deleted by R and R ′ , respectively. Then, we write R R ′ if for all sequences σ ∈ S we have J σ ⊇ J ′ σ . To simplify our exposition, we use R(σ) ⊑ R ′ (σ) to denote the fact that J σ ⊇ J ′ σ . If J σ = J ′ σ , then we simply write R(σ) = R ′ (σ). Moreover, we may adopt the same notation to arbitrary substrings of w.f.c.r.'s.

It is easy to verify that is reflexive and transitive (but, as we will see, not linear). Also, it is antisymmetric: if two rules R, R ′ delete exactly the same terms, i.e., R R ′ and R ′ R, then they are equivalent. Conversely, it follows from Proposition 12 that if two rules are equivalent, then they have the same factorized irredundant form, therefore R R ′ and R ′ R. Thus, (R/ ∼ , ) is a poset (partially ordered set). In what follows, we make no distinction between w.f.c.r.'s and the elements of R/ ∼ , which will be always written in the factorized irredundant form.

Preliminary results

In the following, let ω, ω ′ ∈ L({ρ 4 , ρ 5 }), and a, b, c, d ∈ {0, 1}.

Lemma 13. Let T, T ′ ∈ R/ ∼ . If T T ′ , then ωρ a 1 ρ b 2 ρ 3 T ωρ a 1 ρ b 2 ρ 3 T ′ .
Moreover, if ρ 4 and ρ 5 alternate finitely many times in ω, then ωρ a

1 ρ b 2 ρ 3 T > ωρ a 1 ρ b 2 ρ 3 T ′ (resp. ωρ a 1 ρ b 2 ρ 3 T ωρ a 1 ρ b 2 ρ 3 T ′ ) if and only if T > T ′ (resp. T T ′ ).
Proof. From Lemma 9 (ii), if ρ 4 and ρ 5 alternate infinitely many times in ω, then

ωρ a 1 ρ b 2 ρ 3 T = (ρ 4 ρ 5 ) * ρ a 1 ρ b 2 ρ 3 = ωρ a 1 ρ b 2 ρ 3 T ′ .
(iii): Suppose that n = m, say 1 n < m. First we consider the case n = 1. Let σ = (1, 1)(0, 1)(1, 0). Then T (σ) = ε = T ′ (σ) and thus T T ′ . Let σ ′ = (1, 1)(0, 1) α (1, 1) m-1 (1, 0) where α = 0 if b 1 = 0, and α = 1 otherwise. Then T (σ ′ ) = ε = T ′ (σ ′ ) and thus T T ′ .

Suppose now that n > 1. Then, for σ = (1, 1)(0, 1)(1, 1) m-2 (1, 0), we have T (σ) = ε = T ′ (σ) and thus T T ′ .

To show that T T ′ , let σ ′ be given by

• σ ′ = (1, 1)(0, 1)(1, 1) n-1 (1, 1)(1, 1) m-n-1 (1, 0) if b n , b ′ m = 0, • σ ′ = (1, 1)(0, 1)(1, 1) n-2 (1, 0)(1, 1)(0, 1)(1, 1) m-n-1 (1, 0) if b n = 0 and b ′ m = 0, • σ ′ = (1, 1)(0, 1)(1, 1) n-1 (1, 1)(1, 1) m-n-2 (1, 0)(0, 1) if b n = 0 and b ′ m = 0, and • σ ′ = (1, 1)(0, 1)(1, 1) n-2 (1, 0)(1, 1)(0, 1)(1, 1) m-n-1 (1, 0) if b n , b ′ m = 0.
In each case we get T (σ ′ ) = ε = T ′ (σ), and thus T T ′ .

Remark 19. Note that the proofs of (i) and (ii) of Lemma 18 show that if

b n = b ′ n = 0 and (a j , b j ) = (a ′ j , b ′ j ) for 1 j < n, then T < T ′ if and only if a n > a ′ n . Similarly, if b n = b ′ n = 0, a n = a ′ n = 0, a n-1 = a ′ n-1 , and (a j , b j ) = (a ′ j , b ′ j ) for 1 j < n -1, then T < T ′ if and only if b n-1 > b ′ n-1 . Moreover, if b n = b ′ n , a n = a ′ n , and there exists 1 j < n such that a j > a ′ j or b j > b ′ j , then we have that ω ′ ρ 1 ρ 2 ρ 3 • + - ωρ a
1 ρ b 2 ρ 3 T for every T ∈ R and any a, b ∈ {0, 1}. To illustrate, suppose a j > a ′ j . Then consider σ given by

• σ = (1, 1)(0, 1)(1, 1) j-2 (1, 0) a ′ j +1 (0, 1)[(1, 0)(0, 1)] n-j-1 (1, 0) if 1 < j, and
• σ = (1, 1)(1, 0) a ′ j +1 (0, 1)[(1, 0)(0, 1)] n-1 (1, 0) otherwise.
Remark 20. By reasoning as in the proof of (iii) of Lemma 18 and taking ω and ω ′ as above with m < n, one can show that ω ′ ρ 1 ρ 2 ρ 3 • +

Maximal elements

We now focus on the maximal elements of R/ ∼ . In [START_REF] Grabisch | The symmetric Sugeno integral[END_REF], it was proved that • 0 is a maximal element of the set of well-formed computation rules. Proof. It suffices to show that for every

T ′ = T ′ 1 T ′ 2 • • • such that T ′ T = T 1 T 2 • • • , we have T ′ ∈ R 123 .
For the sake of a contradiction, suppose T ′ ∈ R 123 , and let i = min{j ∈ N : Let R ′ = (ρ 1 ρ 2 ρ 3 ) n R, and set T ′ = ρ a 1 ρ b 2 ρ 3 R ′ . Let γ = (1, 1)(1, 0)(0, 1). Then T (γ) = ε < (1, 0)(0, 1) = T ′ (σ), and thus T < T ′ . Hence, T is not maximal.

T ′ i ∈ L({ρ 1 , ρ 2 , ρ 3 })}. Note that T i = ρ a
As an immediate corollary we get the following necessary condition for maximality.

Corollary 34. Let T = T 1 T 2 • • • with T i = ω i ρ a i 1 ρ b i 2 ρ 3 .
If T is maximal, then for every i ∈ N, ω i ∈ L(ρ 4 ) ∪ L(ρ 5 ).

5 ) * . Claim 1 .

 51 Any way of parenthesing a word in L(Z) corresponds to a word (rule) in L({ρ ′ k 1 , . . . , ρ ′ k 5 } k∈N ), and conversely. Proof of Claim 1. Indeed, consider a word w ∈ L(Z): parentheses are put around 2 consecutive elements, like (a b), where a or b can be the result of a pair of parentheses too. Only three cases can occur: (i) either a = b, then (a b) = a = b. This corresponds to basic rules ρ ′ k 1 (if a > 0) or ρ ′ k 2 (if a < 0) for a suitable k; (ii) or a = -b, then (a b) = 0. This corresponds to the basic rule ρ ′ k 3 for a suitable k; (iii) otherwise |a| < |b| (or |a| > |b|). Then (a b) = b and this corresponds to the basic rules

- ωρ a 1 ρ b 2 ρ 3 T

 3 for every T ∈ R and any a, b ∈ {0, 1}.

4. 2 a 1 ρ b 2 ρ 3

 23 The subposet R 123 .Let R 123 = {R ∈ R/ ∼ : R ∈ L({ρ 1 , ρ 2 , ρ 3 })}. Writing these rules in factorized irredundant form, they read R = T 1 T 2 • • • where, for each i ∈ N, T i = ρ for some a, b ∈ {0, 1}. Note that from Proposition 12 it follows that each such expression is necessarily in R/ ∼ , is in the factorized irredundant form, and has infinite length.For T ∈ R 123 , and a, b ∈ {0, 1}, setI T ab = {i ∈ N : T i = ρ a 1 ρ b 2 ρ 3 }. Since T is of infinite length, (I T ab ) a,b∈{0,1} is a partition of N. Moreover, (I T ab ) a,b∈{0,1} uniquely determines T . Proposition 21. Let T, T ′ ∈ R 123 . Then (i) T T ′ if and only if I T 11 ⊇ I T ′ 11 and I T ab ⊆ I T ′ ab , for any (a, b) = (1, 1). In particular, (ii) T < T ′ whenever I T 11 ⊃ I T ′ 11 and I T ab ⊆ I T ′ ab , for any (a, b) = (1, 1);

Proposition 31. Let T = ωρ a 1 ρ b 2 ρ 3 T

 3 ′ . If T is maximal, then (i) ρ 4 and ρ 5 alternate finitely many times in ω, (ii) (a, b) < (1, 1), and (iii) T ′ is maximal. Proof. Conditions (i) and (ii) follow from Lemmas 17 and 16, respectively. Condition (iii) follows from Lemma 13. As it turns out, every maximal element of R 123 is also maximal in R/ ∼ . Proposition 32. Let T ∈ R 123 . If I T 11 = ∅, then T is a maximal element of R/ ∼ .

1 ρ b 2 ρ 3

 3 for (a, b) < (1, 1), for every i ∈ N. Since T ′ T , T ′ i = ωρ a 1 ρ b 2 ρ 3 where ρ 4 and ρ 5 alternate finitely many times in ω. Without loss of generality, supposeω = ρ 4 ω ′ . Consider σ = (1, 1) i-1 (1, 0) 2 . Then T (σ) = (1, 0) 2 > (1, 0) = T ′ (σ),thus yielding the desired contradiction. Hence, T ′ ∈ R 123 and, by Corollary 22, T ′ = T . Thus T is maximal in R. Now we consider the maximal elements T ∈ (R/ ∼ ) \ R 123 . Proposition 33. Let T = ωρ a 1 ρ b 2 ρ 3 R. If ω ∈ L(ρ 4 ) ∪ L(ρ 5 ), then T is not maximal. Proof. Let ω = ρ a 1 4 ρ b 1 5 • • • ρ an 4 ρ bn 5 , n 1. Without loss of generality, suppose that a i = 0, b i = 0, for every 1 i n. Assume also that a, b = 0; the other cases (a, b) < (1, 1) follow similarly.

Remark 35 .

 35 Let T = T 1 T 2 • • • where T i = ω i ρ a i 1 ρ b i 2 ρ 3 , with ω i ∈ L(ρ 4 ) ∪ L(ρ 5 ). If for some i ∈ N, ω i is ρ * 4 , then T = T 1 • • • T i . Otherwise, T = T 1 T 2 • • •, and for each i there is a string γ such that T i acts on γ.Proposition 36. Let T = T 1 T 2 • • • where T i = ω i ρ a i 1 ρ b i 2 ρ 3 , and T ′ = T ′ 1 T ′ 2 • • • where T ′ i = ω ′ i ρ a i 1 ρ b i 2 ρ 3 , with ω i , ω ′ i ∈ L(ρ 4 ) ∪ L(ρ 5). Then T T ′ if and only if one of the following holds:

It is noteworthy to observe that this framework is suitable for any nonassociative operation that satisfies (ii) and (iii) of Proposition

So we may assume that ω = ρ a 1 4 ρ b 1 5 • • • ρ an 4 ρ bn 5 , with a i , b i ∈ N ∪ { * }. We assume also that a i = 0 for 2 i n, and b i = 0 for 1 n -1. We treat the case a 1 = 0, b n = 0, the remaining cases follow similarly.

To see that ωρ a 1 ρ b 2 ρ 3 T ωρ a 1 ρ b 2 ρ 3 T ′ , just note that for every string γ = (p 1 , m 1 ) • • • (p k , m k ), (p 1 , m 1 ) ≥ (1, 1), we have

Hence, ωρ a 1 ρ b 2 ρ 3 T ωρ a 1 ρ b 2 ρ 3 T ′ , and by antisymmetry, the strict inequality occurs if and only if T > T ′ . Similarly, if T T ′ , then by taking

• σ > and σ < such that T (σ > ) ⊐ T ′ (σ > ) and T (σ < ) ⊏ T ′ (σ < ), respectively, and

• γ > = σσ > and γ < = σσ < , where σ is given in Remark 11 (for

we can verify that ωρ a 1 ρ b 2 ρ 3 T ωρ a 1 ρ b 2 ρ 3 T ′ . This completes the proof of the lemma. By repeated applications of Lemma 13, we have the following corollary.

Corollary 14. Let T, T ′ ∈ R/ ∼ , and let

T ′ , then RT RT ′ . Furthermore, if ρ 4 and ρ 5 alternate finitely many times in each ω i , then RT > RT ′ (resp. RT RT ′ ) if and only if T > T ′ (resp. T T ′ ).

Remark 15. In fact, by Corollary 14 it follows that if ρ 4 and ρ 5 alternate finitely many times in each ω i , then T T ′ (resp. T T ′ ) if and only if RT RT ′ (resp. RT RT ′ ).

Proof. To see that the condition in the first claim is sufficient, observe that if (a, b) = (c, d), then by Lemma 13 ωρ a

and hence ωρ a

showing that the condition of the second claim is also sufficient.

To verify that the conditions in the first and second claims are also necessary, it suffices to show that if (a, b), (c, d) = (1, 1) and (a, b) = (c, d), then ωρ a 1 ρ b 2 ρ 3 T ωρ c 1 ρ d 2 ρ 3 T . But this fact can be easily verified by making use of the strings (2, 1), [START_REF] Blyth | Lattices and Ordered Algebraic Structures[END_REF][START_REF] Baets | The quest for rings on bipolar scales[END_REF] or [START_REF] Baets | The quest for rings on bipolar scales[END_REF][START_REF] Baets | The quest for rings on bipolar scales[END_REF]. Lemma 17. If ρ 4 and ρ 5 alternate infinitely many times in ω but not in ω ′ , then

-, the following assertions hold:

Proof. We may assume that a i = 0 for 2 i n and b i = 0 for 1 n -1, and that a ′ j = 0 for 2 j m and b ′ j = 0 for 1 j m -1.

, we see that T T ′ and T T ′ , respectively. We prove necessity by counterposition. Observe first that if b

does not delete all terms of (p 1 , m 1 ), then T (σ) ⊑ T ′ (σ) since the "subrule" • + -in T and T ′ does not act on σ; hence, without loss of generality, we may further assume that (p 1 , m 1 ) = (1, 1). Now, if m 2 = 0, then T (σ) ⊑ T ′ (σ), and if p 2 = 0, then T (σ) = T ′ (σ); hence, we may assume m 2 = 0 and p 2 = 0. In fact, we may suppose that p 2 a ′ 1 since, otherwise,

Under the assumption that m 2 = 0 and p 2 a ′ 1 , and applying the same reasoning to (p 3 , m 3 ), we again derive that the only case to consider is when m 3 = 0 and 0 < p 3 a ′ 1p 2 . Proceeding in this way, we may eventually arrive at (p j , m j ) with m i = 0 and p i > 0 for i = 2, . . . , j -1, m j = 0 and

The only case to consider reduces then to p j = 0, hence (p j , m j ) = (0, 0), so this term disappears, and similarly all remaining terms until (p k , m k ). Otherwise, if

In any case we have T T ′ (hence, T T ′ ).

(ii): The proof of sufficiency in the case when (a j , b j ) = (a ′ j , b ′ j ), for 1 j < n, follows exactly the same steps as in the proof of (i), by adding (0, 1)[(1, 0)(0, 1)] n-2 (after the first (1, 1)) to the strings used above. We consider the case when b n = b ′ n = 0 and there exists 1

for some 1 j < n -1, follows similarly by interchanging the roles of ρ 4 and ρ 5 , and those of (1, 0) and (0, 1) (and a ′ j and b ′ j ) in the strings below. So let σ be given by

Then T (σ) = ε = T ′ (σ) and thus T T ′ . Now let σ ′ be given by

(1, 0) if 1 < j (with (1, 1) n-j-2 = (0, 0) whenever nj -2 0), and

Then T (σ ′ ) = ε = T ′ (σ ′ ) and thus T T ′ . The proof of necessity is similar to case (i). If none of the conditions of (ii) is satisfied, then we may assume that b n = b ′ n = 0, (a j , b j ) = (a ′ j , b ′ j ) for every 1 j < n, and focus on the case a n = a ′ n (for otherwise

, and (a j , b j ) = (a ′ j , b ′ j ) for every 1 j < n -1 follows similarly by the above mentioned substitutions.)

So suppose without loss of generality that a n > a ′ n = t. As in case (i), we show that T < T ′ . By making use of σ = (1, 1)(0, 1)(1, 1) n-2 (1, 0) a ′ n +1 , we see that

. By reasoning as in (i), we may assume that k > t + n and, since (a j , b j ) = (a ′ j , b ′ j ) for every 1 j < n, that (p 2 , m 2 ) = (0, 1), (p j , m j ) = (1, 1) for 3 j < n + 1, and that p j = 0 for each n + 1 j t + n; for otherwise we reach the same conclusion T (σ) ⊑ T ′ (σ).

If p t+n+1 = 0 or m t+n+1 = 0, then T (σ) = T ′ (σ) or T (σ) ⊏ T ′ (σ), respectively. If p t+n+1 = 0 and m t+n+1 = 0, then T (σ) ⊑ T ′ (σ).

(iii) T T ′ whenever I T ab I T ′ ab for some a, b ∈ {0, 1}. Proof. Clearly, (iii) follows from (i). Since (I T ab ) a,b∈{0,1} is a partition of N, (ii) also follows from (i).

To see that the conditions in (i) are sufficient, note that, if T acts on a string σ = (p 1 , m 1 ) • • • (p k , m k ), then its factor T i acts on the term (p i , m i ). Suppose that for some σ we have T (σ) ⊐ T ′ (σ). Then, using the above remark, for some i we have

So we may assume that I T 11 ⊇ I T ′ 11 . We treat the case I T 01 ⊆ I T ′ 01 ; the remaining cases follow similarly. Let i = min{j ∈ I T 01 :

As immediate corollaries we have the following results.

) is order-isomorphic to (P( (a,b) =(1,1) I R ab ), ⊆). From Corollary 24, it follows that (R 123 , ) embeds the power set of integers ordered by inclusion. Furthermore, for

Least element and atoms

We turn to the study of the atoms of R/ ∼ . The next proposition was presented in [START_REF] Grabisch | The symmetric Sugeno integral[END_REF].

Proposition 25. The rule • +

-is the least element of R/ ∼ . Proof. It follows immediately from the fact that • + -deletes every term of a nonassociative string.

Proposition 26. Let T = ωρ a 1 ρ b 2 ρ 3 T ′ be an element of R/ ∼ , where (a, b) = (1, 1). Then T is an atom if and only if ρ 4 and ρ 5 alternate infinitely many times in ω (and therefore

Proof. Note that if ρ 4 and ρ 5 alternate infinitely many times in ω, then T = ωρ a 1 ρ b 2 ρ 3 . By Lemma 16, the condition is sufficient.

To show that it is also necessary, let T be an atom, and for the sake of a contradiction suppose that ρ 4 and ρ 5 alternate finitely many times in ω. Let T ′′ = (ρ 4 ρ 5 ) * T . Then

Moreover, by Lemma 17 we have T > T ′′ , which contradicts the fact that T is an atom.

Consequently, for (a, b) < (1, 1), we have only 3 atoms, namely (ρ 4 ρ 5 ) * ρ 3 , (ρ 4 ρ 5 ) * ρ 1 ρ 3 and (ρ 4 ρ 5 ) * ρ 2 ρ 3 .

Proposition 27. If T = ωρ 1 ρ 2 ρ 3 T ′ is an atom, then ρ 4 and ρ 5 alternate finitely many times in ω.

Proof. If ρ 4 and ρ 5 alternate infinitely many times in ω, then T = • + -. Proposition 28. Let T = ωρ 1 ρ 2 ρ 3 T ′ such that ρ 4 and ρ 5 alternate finitely many times in ω. If T is an atom, then T ′ = • + -. Proof. Let T = ωρ 1 ρ 2 ρ 3 T ′ be an atom. Suppose for the sake of a contradiction that T ′ = • + -. By Proposition 25, T ′ > • + -, and by Lemma 17, T ′′ = ωρ 1 ρ 2 ρ 3 • + -> • + -. Moreover, by Lemma 13, T > T ′′ , which contradicts the fact that T is an atom.

for some 1 t i ∧ j. Proof. To see that the conditions in (i)-(iii) are necessary, observe that if T T ′ (T and T ′ in factorized irredundant forms), then we must have T = T ′ . Since each ω i and each ω ′ i is in L(ρ 4 ) ∪ L(ρ 5 ), one of (i)-(iii) must occur.

To show that (i) is sufficient, assume that each ω i , ω ′ i has finite length and, without loss of generality, suppose that ω 1 = ω ′ 1 . We consider 3 representative cases; the remaining cases follow similarly.

Suppose that ω 1 ∈ L({ρ 4 }) and ω ′ 1 ∈ L({ρ 5 }). Take σ = (1, 1)(0, 1) and

Suppose that ω 1 ∈ L({ρ 4 }) and ω ′ 1 = ε. Take σ = (1, 1)(1, 0) and

In all representative cases we conclude that T T ′ .

To show that (ii) is sufficient, suppose that

, then the proof of (i) can be used to show that T T ′ . So suppose that k = i and, without loss of generality, suppose that ω i = ρ * 4 and

, and again we have that T T ′ .

Finally, to show that (iii) is sufficient, suppose that

where neither ρ * 4 nor ρ * 5 occur in T l , 1 l i -1, nor in T ′ k , 1 k j -1, or ω t = ω ′ t , for some 1 t i ∧ j. Now, as case (i), we may assume that i < j (the case i > j is similar), and that ω i ∈ L({ρ 4 }) and ω ′ i = ρ m 4 , m > 0. But then, as in case (ii), we again have T T ′ , and thus the proof is now complete.

From Lemma 16, the above necessary condition and Propositions 32 and 36, we obtain the following explicit description of the maximal elements of R/ ∼ . Theorem 37. Let T ∈ R/ ∼ . Then T is maximal if and only if

) and (a i , b i ) < (1, 1).

5 Concluding remarks: An alternative ordering of R/ ∼ An alternative ordering of R/ ∼ was proposed in [START_REF] Grabisch | The symmetric Sugeno integral[END_REF], and which is defined as follows.

Given R ∈ R/ ∼ , let Ker(R) = {σ : R(σ) = ε}. For R, R ′ ∈ R/ ∼ , we write R Ker R ′ if Ker(R) ⊇ Ker(R ′ ). Clearly, Ker is a partial ordering of R/ ∼ , and if R R ′ , then R Ker R ′ ; see [START_REF] Grabisch | The symmetric Sugeno integral[END_REF]. As it turns out, the converse is also true.

Proposition 38. Let R, R ′ ∈ R/ ∼ . Then R R ′ if and only if R Ker R ′ . Proof. To prove Proposition 38 it remains to show that if R R ′ , then R Ker R ′ , i.e., R Ker R ′ and R ′ Ker R. So suppose that R R ′ , that is, there exist σ 1 and σ 2 such that R(σ 1 ) ⊏ R ′ (σ 1 ) and R(σ 2 ) ⊐ R ′ (σ 2 ).

Let σ ′ 1 the string be obtained from σ 1 by removing the indices in R(σ 1 ) such that R(σ ′ 1 ) = ε = R ′ (σ ′ 1 ). Hence, R ′ Ker R. Similarly, let σ ′ 2 the string be obtained from σ 2 by removing the indices in R ′ (σ 2 ) such that R(σ ′

2 ) = ε = R ′ (σ ′ 2 ). Hence, R Ker R ′ , and thus R Ker R ′ . We have presented a partial description of the poset R/ ∼ ; being uncountable, there is little hope of obtaining an explicit description as it was the case of the subposet R 123 , which was shown to be isomorphic to the power set of natural numbers.

Looking at directions of further research, we are inevitably drawn to the question in determining whether R/ ∼ constitutes a ∧-semilattice and, if that is the case, whether its closed intervals constitute lattices, as it was the case of the subposet R 123 .