From Knowledge to Sign Management: A Co-design Methodology for Biodiversity and Music Enhancement

. 1 When using Artificial Intelligence techniques for Knowledge management in decision support systems, the enhancement of knowledge should be based both on artificial machine learning methods and a natural human learning approach. Indeed, knowledge representation with ontologies and Case-Based Reasoning (CBR) is not enough for gaining qualitative results in decision support systems. We need to manage know-how, i.e. living knowledge. For example, enhancing biodiversity and music means teaching and learning the effectiveness of individual and living interpretations (how to observe a natural specimen, how to play a music sheet). The quality of descriptions is thus very important to correctly classify or identify marine or terrestrial organisms, or learn adequately an instrument such as the guitar or the piano. This paper introduces Sign management to tackle this qualitative learning problem in AI. Then, a Co-design methodology and a cooking method on a Creativity Platform are proposed: when dealing with such complex domains, we need to focus on the signification of knowledge construction that operates in co-designing an e-service that should be useful for reaching a more robust knowledge base. Our finding is that due to different interpretations of domain objects from subjects (persons), we need sign bases to move from written expert knowledge transmission to multimedia know-how sharing in the community for getting better results.

Introduction
Fifteen years ago at University of Reunion Island, some researchers of the mathematics and computer science team (LIM) decided to apply Knowledge Engineering and Human-Computer Interaction to the enhancement of biodiversity and music for educational purpose. Starting from a Knowledge management methodology in Systematics, a teaching tool called IKBS (Iterative Knowledge Base System) was codesigned between computer scientists and biological experts. The knowledge base was used for modeling and describing their collection of plant and coral specimens with written and structured knowledge. The objective was to help them classify species and transmit their knowledge to other biologists to allow the latters to identify new specimens. But this top-down teaching approach of describing biological objects with IKBS appeared to be a real bottleneck in the identification help process. The problem of interpretation of specimen characters made by specialists emerges when the knowledge base is put in the hands of other biologists: the latters are not able to observe and describe biological objects, characters and values with the same know-how and accuracy as experts when they are left alone, thus leading to wrong identifications. A new bottom-up learning strategy was then required based on sharing observation knowhow rather than transmitting knowledge.
The interpretation problem is identical when dealing with instrumental music. To learn an instrument such as the guitar or the piano, a course with a professor is the best way to perform pieces that are described on scores with musical objects. The teacher shows how he interprets the notes in front of the student. But after the course, the learner is left alone with the music sheet and has to remember all the fingerings and gesture details.
So, we decided to co-design a new type of e-service with teachers and learners called a sign base, dedicated to the formers, in order to show their know-how with multimedia content, and to the latters to reproduce the right fingering, movement, sound and play correctly a piece of music at home, and ask questions to the professor. This "teaching and learning" tool is needed to acquire and share gesture know-how.

From Knowledge to Sign management
Knowledge management is not sufficient for enhancing our biodiversity and music domains. The association of terms must be clarified because knowledge is difficult to manage on its own. Only information ('informatio' = to give a form) that is transmitted between subjects on objects can be captured and managed by computer scientists in information systems. Data are raw content elements (values of attributes) of information measured on objects. Knowledge is registered either between 1) the ears of somebody, i.e. in their head or 2) in books.
In the first case, it is the "subjective" sense or meaning, i.e. the sign-ification (construction of signs) of an object, made of tacit knowledge by a subject. This practical knowledge is the result of a long experience of some experts that have experimented a lot of cases in the fields, and formed their know-how by compiling them continuously in their mind. We consider that this living knowledge, which is made of performances, can be managed by acquiring multimedia contents in the form of annotations.
In the second case, it is the "objective" written result, the formalized representation or know-what that can be found in documents or books such as musical scores (notations) or species taxonomies (monographs). This explicit form made of descriptions is dead knowledge, but it can be updated if it is structured and formatted adequately.
In general, computer scientists manage the second type of knowledge by using Semantic Web in the linguistic semiotics tradition [1] rather than the first type that is more pragmatic [2]. Hence, Knowledge management is mostly viewed as representing objects with description logics and transmitting formal knowledge in knowledge bases as a result of classifying descriptions in a teaching linear mode.
For our part, we consider that both types of knowledge are central to manage for obtaining qualitative teaching and learning results. We advocate the importance of design (sign revelation) and signification (sign construction) for building e-services that really matter for end-users. In this user-centered approach, both artificial and natural, Knowledge management is embedded in Sign management (Fig. 1).

Fig. 1. Knowledge (left) and Sign management (right)
Consequently, the notion of Sign is more general than Knowledge for our purpose in music and biology. A Sign (Fig. 2 on the left) is represented by a tetrahedron with Data, Information, Knowledge and Interpreter at its corners. It is the interpretation of an Object by a Subject at a given time and place, which considers its content (data, fact, event), its form (information), and its sense or meaning (knowledge). What is exchanged on a support between Subjects is called Information and this digitized codification can be managed.
The Signification or semiosis ( Fig. 2 on the right) is the continuous process of using Signs in human thinking for acquiring Objects interpreted by Subjects (see arrows in Fig. 2). The Subject operates on Signs in two phases: reflection and action. These phases are inter-linked in an iterative cycle with a helical spiral shape including six moments: 1) to desire, 2) to do, 3) to know, 4) to interpret, 5) to know-how for oneself, 6) to communicate to others. The semiosis spiral is included in the tetrahedron of the Sign. The edges represent the three fundamental characteristics of a Subject 's interpretation on an Object, i.e. volition, action and cognition.
Sign management is based on the signification process (construction of signs) and comes from the pragmatic learning theories, i.e. umwelt [3], activity [4], and biosemiotics [5]. It is a human machine interaction process that follows the living beings' paradigm: signification or semiosis is to give sense to our perceptions, actions, and understanding of situations.

Fig. 2. The Sign tetrahedron representation and the signification process
Therefore, it is an ergonomic and qualitative approach that is mostly constructivist, reflexive and iterative, like in the natural ecosystems where living organisms use mostly the abduction principle (make hypotheses) to innovate continuously for surviving in the environment. Sign management is then more human-centred than Knowledge management: it places inductive and deductive methods and technologies at the service of human development and not the contrary. In this context, Design and Signification are the core elements of Semiotic Web for making e-services [6].
As such, ISBS (Iterative Sign Base System) will be a dynamic and iterative process between ontologies (definitions), instances (descriptions), generalizations (classifications) and performances (interpretations) that are shown in a sign base for them to be more robust in complex domains such as Biodiversity and Music enhancement [7].

Biodiversity and music enhancement
Starting from these two knowledge transmission problems in biology and music, a Codesign methodology based on Sign management is proposed in this paper. We will argue that the representation of objects for machine learning is necessary but not sufficient for capturing and transmitting knowledge: the ontology modeling for cases description is only the engineering and written business object activity of the process of Knowledge management, made by computer scientists and domain specialists. In fact, we need also the other Human Computer Interaction side for getting the signification of objects, called the design and usage object activity. It is dedicated to other end-users who are not experts. Indeed, the specialists must teach each biological or musical object with multimedia means (illustrations, 3D simulations, videos) in order that the users can reproduce them visually or kinesthetically ("show me your knowhow"). Learners who incorporate the meaning of objects by practicing it (embodiment) better understand them for solving their visual appreciation (right values of attributes in Systematics) or gestural interpretation (right melodies and rhythms in harmony for playing Music).

Teaching and learning approach for Systematics
We have experienced the building of knowledge bases in biology for 30 years since the first expert system in agriculture in France for identifying tomato diseases, called TOM [8]. The knowledge acquisition bottleneck of gaining expert rules led us to adopt a machine learning and CBR approach in European projects [9,10]. We applied these symbolic and numeric induction techniques in the domains of marine Systematics for sponges and corals classification and identification purposes [11]. The IKBS Knowledge Base Management System that we designed for specialists could be used directly by them for defining characters (objects, attributes, values) and structure a descriptive model with descriptive logics, i.e. relational dependencies (parts, viewpoints, specializations), then describe cases in a questionnaire based on this ontology [12]. Then, descriptions were used to build a decision tree with ID3 information gain for identification of new observations, or dissimilarity measures (knearest neighbors) techniques to classify or compare supervised cases or unsupervised observations (Fig. 3).
The experimentation and validation process of classifications and identifications with biologists showed that the robustness of our knowledge bases (around 70% of good results) relies on 1) iterating on the definition of the descriptive model to better explain the signification of characters to end-users, 2) storing different subject descriptions of the same specimen in the case base (inter-observer variation), and 3) multiplying the number of specimen descriptions in the case-base to cover intra-specific variation.
The experts, aware of the importance of transmitting their knowledge to other biologists, postulates more precise and relevant characters that may be easier to observe and/or offer less ambiguous values (easier to interpret) in their descriptive model. For example, they will refine it based on mutually exclusive values, monosemic attributes, position of objects' attributes, glossary of terms, warning messages and observation help, enhanced illustrations and animations [13].
The biological Knowledge management that we have experienced with IKBS is mostly centered on the expert teaching of domain objects toward biological end-users. But building knowledge bases with AI techniques relies not only on explicit expert know-how. This living knowledge should be shared between practitioners of a community to be questioned and find a consensus. The fact is that we have always the specimen on the table, and every describer can come back to review it, better observe the characters and evaluate them.
Lastly, managing biodiversity is a complex multi-dimensional endeavor that uses specimen collections. We are at the beginning of digitalizing them in museums. Each specimen should have a morphological description of objects (components) that is conform to a common descriptive model of the parent taxa (Species, Genus, Family, etc.) and should be stored in knowledge bases of virtual museums for future retrieval. The building of knowledge bases in instrumental music began ten years ago with an idea: how to capture the know-how of artists and professors, i.e. their finger movements that reproduce the right and lovely sound of a music piece? Because when we are left alone at home with our instrument after the course with the professor, we are not able to remember all the fingerings that are written on the scores and how to play them correctly. So we started to answer this question with an instrumental e-learning project on the guitar [14] to collect master pieces in DVDs, showing a musical karaoke that binds the score with six multi-angle videos (Fig. 4 above).
The transmission of knowledge through this offline solution is a teaching (topdown) approach. The designed prototype was experimented twice on a Co-design Platform (see below) with learners and professors. The capability to learn a piece of music by reproducing the same gesture of the piece was emphasized by learners: for instance, they could choose to focus on the right hand and loop in slow motion on a part of the score. The DVDs gave good learning results but learners would have appreciated more feedbacks (pedagogical advices) from professors. So, we designed another glosses system on the Web called FIGS (Flash Interactive Guitar Saloon). It allows learners to ask questions to teachers from their webcam at home. Videos are indexed to a part of the track of the piece. The professor shows his technical solution or performance by filming himself also at home after receiving an email. He doesn't need to be connected synchronously to the system but the dialog is bidirectional.
This instrumental online e-learning solution was the start for another complementary project in 2009 on the piano [15]. The idea was to allow performers to show their fingerings by the means of using annotations of scores on tablets. @-MUSE (@nnotation platform for MUSical Education) aims at constituting a Musical Sign Base (MSB) rather than a Knowledge Base. Indeed, the focus for playing an instrument is more on the learning (bottom-up) of practices by sharing know-how with video annotations. @-MUSE stores MusicXML scores as written knowledge (notation) and allows each player to index his interpretation (know-how) as a filmed annotation in any part of the score (Fig. 4 right). Moreover, the annotations can be shared in the frame of a community of musicians playing the same sheet of music, and reused for similar pieces.
The learning method on tablets has not yet been tested in the field of music schools because of a lack of means to finalize the prototype. The coupling of @-MUSE with a musical editor such as MuseScore [16] was under consideration but this endeavor needs a partnership with a private company that has not been realized. We are here at the frontier of research and innovation, with a new ecosystem to build between our computer science laboratory, a private company and the targeted public (musicians). It is the reason why we try to promote the concept of Living Labs at our university to open to the outside world with a Co-design methodology.

A Co-design methodology for making e-services
In both application domains of biodiversity and music enhancement explained above, we had to deal with the problem of modeling qualitative interpretations of natural and cultural objects, observed by different types of agents (expert, novice), i.e. how to observe specimens for right identification of species names, and how to play nicely a piece of music with a musical instrument. The question is how ICT can help to achieve these aims, i.e. build e-services that facilitate the teaching and learning of such qualitative know-how. For this purpose, we emphasize 1) the use of design to reveal the signs of the ICT product or e-service to conceive, 2) a living lab for enhancing ideas and making projects, 3) a Co-design platform for processing collaborative design and experimenting mock-ups and prototypes and 4) an evaluation based on focus groups and questionnaires for assessing the results in terms of quality of e-services.

Designing for revealing signs
When designing a computerized solution for know-how management, we must concretize the signs that are the intention or purpose of an e-service that is useful for some individuals. The term design comes from the Latin word designo (with "de" meaning to reveal) and was popularized at the Renaissance period in Italy (disegno) [17]. Thus, the intention (sign) is at the beginning of the process of creativity. These signs characterize something that is desired in human mind. They are the ingredients of an idea that can evolve into a concept, take shape in a mock-up, and then become tested in prototypes before realizing an e-service.
For example, the desire of a beginner in classical guitar would be to play the famous piece "Forbidden Games" in the same way as a performer whom he admires.
In the instrumental e-learning concept, i.e. e-guitare, the request was to reproduce the performance of a piece, by watching a teacher's hands. The vision is as follows: Imagine, your guitar nicely sitting on your knee, you are listening to the guitar piece "Forbidden Games" and at the same time you are watching your guitar teacher's hands on your screen. Close-ups, slow motions, rewinding, and loops: many options are offered so that you can play at the same time as the teacher. To help you, the inset score lights up each note as it is played. All this is on high definition video, on full screen with real stereo sound! In addition, the teacher's advice, in visual and oral form, accompanies the notes and bars being played (see the DVD of Fig. 4). The problem is therefore to define the steps by which this vision may become real with products (DVDs) or e-services (FIGS, @-MUSE).
But as elsewhere, to fructify ideas, people who are involved in the de-sign process must find an ecosystem that helps them to concretize their motivation.

Enhancing ideas in a living Lab
As explained above for making e-services, the first step is to generate ideas and show concepts of e-services. This ideation process should be attractive for motivating some researchers to drive innovative projects.
Living Labs (LLs) are those desirable innovation ecosystems (breeding grounds) for enhancing experimental research, find user-centered-design solutions and go to the market, i.e. make ideas become alive (emergence of ideas) towards useful (usage value) and profitable (economic value) products and services.
Curley and Salmelin [18] consider LLs as a significant example of the open innovation 2.0 ecosystem where users are engaged in co-creating value together with all project stakeholders. In contrast, test-beds, usually technology driven, involve users as observed subjects. A LL combines the User eXperience (UX) quality in co-creating, exploring and experimenting with users a product or service that has the capacity to capture previous design experiences [19].
For enhancing ideas, a LL brings together public, private, companies, associations, individual actors, whose goal is to design, develop and test full-scale services, tools or new uses [20]. One aim is for example to out research labs and to move it down in the life of every day, often with a strategic view of the potential uses of these contents and technologies. All this happens in cooperation between local authorities, companies, research laboratories, as well as potential users through platforms offering the possibility to design innovative and analytical uses.
In Reunion Island, we found that in the innovation chain leading from idea to product/services used and marketable, there is a need to implement an important step, one that leads from idea to prototype, through the co-design of the concept, layout, and various drivers to experiment. The missing link that we have identified at University of Reunion Island is the insemination of ideas to prototype before incubation in an innovative company. Indeed, the production and use values of the designed solutions must be acknowledged before reaching their economic values, i.e. whether the prototypes are efficiently built by producers and editors, and if they will be adopted by their targeted users/citizens/consumers.
In this business and usage context, our LL aims to host content producers, i.e. researchers, teachers, entrepreneurs and users to help them develop projects of cocreation of e-services in the various fields that characterize the specificity and the advantages of the territory for its sustainable development.
We want to accompany the process of ideation-design of talented persons (lead users) who wish to develop tools to serve a definite purpose in an area. For example, the idea in biodiversity management is to "better understand our environment to better preserve it because one only protects what one knows and appreciates". The idea in instrumental music is to bring the teacher at home in proposing to mimic the gesture that produces good sound, to slow down, to loop over a passage, or to put oneself in the eyes of the teacher to have his own subjective view.
So, we conceived our LL in education as a real and virtual laboratory for Teaching and Learning Sciences and Arts by Playing [21]. Indeed, edutainment is one of the pillars of the future Web [22]. With game-based learning, we consider that we can play seriously to better know our natural and cultural environment and then better protect it.
As an example of edutainment in biodiversity protection, Fig. 5 shows a virtual ballad in the lagoon where learners can click on fishes to try to identify their name with a questionnaire and then access to information. This e-learning project proposed a 3D prototype for pedagogical access to information in a reef fishes' database. It involved an association [23] for enhancing marine contents to a large public. This virtual ballad is a 3D layer built upon the IKBS platform for accessing questions to identify fishes' names.
For edutainment in music, Fig. 6 shows our real and virtual laboratory in instrumental e-learning for playing the e-guitare DVDs with the iteration process between the production side of the DVD (Teaching) and its usage side (Learning). It makes use of the e-campus project for accessing music pieces through a metaverse and a Massive Multiplayer Online Role Playing Game [24,25]. Our University of Reunion island Living Lab in Teaching and Learning, called UR.LL.TL was certified by ENoLL, the European Network of Living Labs in 2011 [26]. It nurtures content engineering projects by using a methodology focused on the uses (User-Centered-Design) of these services to match with real expectations of users in a domain. This methodology is based on Sign management on a Creativity or Co-design Platform (CdP).

Experimenting and testing on a Creativity Platform
At the convergence of Teaching and Learning, there is the CdP (Fig. 7) for experimenting and testing, i.e. Playing (doing) the new products/services. It is an indispensable brick in the methodological plan of treating business and usage processes with a cooking method to acquire its usage value (see below).   The CdP includes a multimedia platform as the one that we find in television studios, but also includes a physical and virtual place to discuss ideas and projects, make models and prototypes, and experiment them in a synchronous (focus group) or asynchronous way (video forum on the Internet).
The potential for exchange and communication is improved by the implementation of spaces devoted to demonstration, as well as the proposition of innovative services: telepresence walls, spontaneous meeting spaces, exchange through virtual reality visits, etc. The meeting space model must be particularly adaptable to varying needs: from video and Web conferencing and interactive distance platform sessions, virtual cafés to interactive television platforms to netTV studios and distant and virtual reality sessions.
The aim of the CdP is to help to design collaboratively mock-ups and prototypes, and experiment them in a physical meeting place. Co-creation in communities of producers (teachers and content managers), editors (computer scientists and graphic designers) and prosumers (proactive consumers) is a significant characteristic of social and open innovation 2.0 that is part of the DNA of Living Labs for bringing trust between all these co-designers. Moreover, a solution cannot be found only with a small team of producers and editors who are the developers. We need also collaborative users (lead-users) as co-designers, and distributors (jurists, communicators and commercials) for marketing the product/service and define its economic value.
In this frame, the CdP instantiates the LL concept by bringing a Playing ground for practicing e-co-innovation [27,28]. the CdP is the Co-working, Co-learning and Communication Space for researchers and developers, entrepreneurs and users, aimed at defining Collectively the characteristics of e-services to ensure the most direct correspondence between expectations and use. In each case, the objective is to understand the use, achieved by using example platforms, demonstrations, models and simulations, without forgetting questionnaires and structured interviews. The CdP is a way to further understand the conditions of realizing future usages of the services that are analyzed.

Evaluating the solutions with focus groups and questionnaires
The next step is to assess the prototypes to formalize a solution that fits user needs.
In an information-based society, it is no longer acceptable to argue in favor of technology alone, ("techno push"), not even if it is backed up by market research ("market driven"): e-services must consider "User Centered Design" [29]. Indeed, innovation in e-services requires an ability to manage not only knowledge of the endusers (through the Knowledge Management design process), but also knowledge supplied by the end-users themselves (through the Customer Knowledge Management usage process) [30].
A first assessment is led early in the process with focus groups on a limited sample of end-users (< 10). This qualitative approach provides information on system usage. It is based on filmed scenarios, followed by individual and/or groups interviews of testers. The test will highlight the usability flaws, measure the popularity (or not) of features and discuss those that are missing. For the e-guitar project, the conditions of the experiment are expected to move closer to home use, but the presence of other actors and cameras introduced a bias even though it was acceptable: the volunteers found the approach useful and are generally willing to cooperate. Beyond that, this kind of operation is a strong sign of user involvement in the development because it is an evidence of ownership that is offered.
The second assessment arrives after the first one on a large set of end-users (>100). This semi-quantitative approach is based on questionnaires on paper or on the Web. It should allow to produce statistics on the types of users and their use of the system. But to be relevant, it assumes that we have a large enough sample of returns. For the eguitar project, the IKBS tool was used to determine user profiles and personalize the content delivered to each of them in accordance with his interests and experience.
As a conclusion for assessing the quality of e-services, both approaches are useful and should be undertaken in the evaluation process: focus groups allows to test the tool with end-users to bring qualitative development results, in order that the tool becomes an instrument (see below). Questionnaires and surveys allows to test end-users with the tool/instrument to make statistical analysis, i.e. to bring quantitative results about the qualitative learning of end-users.
At last, for making e-services that count for end-users, their active participation in the process is mandatory for them to adopt the product/service. It is why we emphasize the use of Co-design in our methodology, with a cooking method to pass the product/service from a tool to an instrument and get its usage value.
To resume, the five dimensions of Co-design are: The CdP helps to better understand the transformation of the tool (proposed offer) in an instrument (motivated request) necessary for the creation of the supply of the demand.

5
The cooking method of Co-design One of the goals of Sign management of expert via ICT is to improve the performance of the transfer of their knowledge to non-specialists and to facilitate e-services implementation adapted so that they are used. The CdP allows business developers and users to specify together the definition of these e-services to facilitate the emergence of their uses. Based on Activity Theory [31], the cooking method of Co-design aims to control the production process of the e-service by the usage process. To achieve Co-design, we implement iterative methodological processes both on the supply side (production process) and the demand side (usage process). They are based on an experimental approach, combining an inductive generalization step drawing on examples (service conception and elaboration), checking hypotheses (service experimenting) and inferential implementations (range of targeted products). At each stage of the process, between needs and resources, three questions are asked for managing the value of a product/service: 1) what is it good for? 2) what is enough to make it? 3) did we discuss with all stakeholders? These questions on usage value (1), economic value (2) and collaborative value (3), are fundamental to improve the proposed solution iteratively in the Co-design process [32], because it makes sense to reveal the signs of a useful and efficient solution for each stakeholder.
In our Co-design cooking method, usage objects (instrument use, appropriation process and confidence acquisition) of the e-service describe the usage approach of the users on the demand side while business objects (tool engineering, project management and skills acquisiton) describe the production approach of the professionals on the supply side [33] (Fig. 8).
Feedback on the proposed offers with iteration based on the usage objects helps users to express "usage needs" within the CdP. At the start, the proposed offer to be analyzed on the CdP corresponds to a product/service of which the viability remains to be confirmed by users' tests. The e-service definition will be at its height when its functions translate into a real use. We must move from a shared, intangible vision to a concrete and operational product/service, via varied stages of more tangible development (mock-ups and prototypes) to be confirmed.

Fig. 8. Interaction between production and usage approaches
The concept of a CdP links the convergence of ICT (production, edition, distribution) with a co-construction methodology (iteration between solutions and uses) within the meeting space of the key actors (researchers, businesses, users). Furthermore, the CdP is a truly experimental milieu, where all those involved actually contribute to future products/services, responding to users' needs and favoring the highest possible solution's quality.

Production and usage approach analogy
The facilitating role of the CdP between the world of business supply, and the corresponding world of users demand, manifests itself through the observation of behaviors, uses and the search for specificities that underlie usage. The search for these functions refers to the unconscious mechanism, which "pushes" the end-user to utilize e-services in activities by supplying a meaningful context. The CdP thus aims to classify and identify object uses by describing behavior, practice and specificity.
Conducting an analysis on the CdP requires a proposal of a product/service in its original version (idea, concept), which will be gradually transformed to its final version. The production approach leads to the tool's engineering, which is determined in advance based upon the project management (building process) and the know-how acquisition: For the building process of the project managementand all initial engineeringwe integrate the four traditional stages (see Fig. 8  These different levels of activity can be described with business objects, which illustrate the professional approach during the development of the product/service. Acquiring skills refers to both the long-term acquisition of knowledge, which also allows development of the know-how and the how-to of a designer's role [34], i.e. the business skills.
Alongside the production approach, on the usage side, the process takes place with the user, based on knowing how to use the e-service in its different forms: user guides, demonstration models, simulations, accompanying lessons, etc., in order to obtain its confidence. Acquiring this knowledge through learning allows the user to describe usage objects, in the same way as an engineer for describing business objects. The appropriation process of the product/service follows 4 stages (see Fig. 8

on the right):
 The desire of identity to the same level as that proposed in the vision of the project building process,  The activity definition, which is facilitated by the use of the product/service at the same level as stated in the project's objective,  The following up of tasks in accordance with the project plan,  Meaningful evaluation of the project's results.
These exchanges lead to debate, contrasting points of view, demonstrations and betatests. Depending on the context, all or some of the meetings may be organized in the form of a tele-visual platform with an animator and producer; exchanges are recorded and lead to a summary and analysis of appropriation processes.

The instrumented Activity Situation model
The interaction between the designer and the user is closely linked to the transformation of the product/service from a tool to an instrument. Drawing upon the Activity Theory [4,31,35,36], we may define the structure from which the uses will be established. For example, the Instrumented Activity Situation (IAS) model by Rabardel [37] aims to reveal the use of the instrument -a real object of activity that the user expects from the proposed product/service (Fig. 9).
This model defines two different parts within the instrument, the artifact and the use schemes. The artifact is constituted by the invariables of the product/service, with a certain capacity for adaptation, representing the technical and universal aspects, i.e. the tool. Use schemes are structures that have been elaborated by generalizing the invariables linked to action, prolonging the biological organization of the subject and having the capacity to assimilate and adapt variables in relation to the subject's outside environment.

Fig. 9. The IAS model
Each product/service is built by the designer through an initial proposal of an artifact, as well as use schemes, which are intended to ensure the emergence of a specific usage of the service-product. The confrontation between the proposed object and the future users on the CdP allows a greater understanding of the desired alterations by observing two types of relationships: that of the subject towards the artifact and that of the artifact towards the subject.
The first idea reflects the process of instrumentalization in which the subject gives meaning to the artifact and enriches it. Being based on the intrinsic characteristics of the artifact, the subject, by engaging in the activity, attributes a status and a function to the artifact. This process of attributing a function can be momentary (use) or persistent (usage). In this case, the functions we may refer to as constitutive of the artifact -those that have been imagined by the designer -are incorporated. This is the process of instrumentalization.
The second relationship reflects the process of instrumentation whereby the functions, which make up the artifact, represent constraints on the subject, a framework that structures the activity. They instigate a process of assimilation and adaptation on the subject's part. These two types of processes lead to the incorporation and reorganization of a part of the use schemes, producing a transformed collection that is more adapted to the actual situation.
The instrumental approach using the IAS model applies just as much to the design stage of a new product/service, as to the stage of recursive analysis of existing situations that make use of a product/service already in place (Fig. 10).
The Co-design process thus identifies constituted functions of the product/service being analyzed in order to implement operational modes at the earliest possible stage in the original design.
For Rabardel, the instrument is not only part of the subject's external world, but also the result of individual involvement of the subject in the action of appropriation which varies from the search for identity to accomplishing tasks. Appropriation refers to the process by which the subject reconstructs an artifact's use scheme during a meaningful activity. A tool becomes an instrument when it becomes the vehicle for specific actions for the subject: the user establishes the tool as an instrument for him/herself. The process of this transformation is more important than the result.

Fig. 10. Stages of transformation: from tool to instrument
The usage of a product/service is significant for a user in that he was able to gradually transform the tool into an instrument. We will now illustrate this cooking method with the design and implementation of an instrumental e-learning service for playing guitar music pieces, the E-guitare project. Note that the E-piano project which followed E-guitare uses the same principles, but we don't illustrate it in this paper. For this instrument, we can notice that the tablet is an artifact that cooresponds to the use scheme of putting a score on a music stand (Fig. 4 below). But the question of using fingers for triggering actions on this support is an IHM concern that needs ergonomic studies for evaluating the adaptation of the musician to this artifact.

E-guitar example
This project, initiated in 2003, aims to create intuitive learning systems to help people play guitar pieces through multimedia means. This research project lasted four years until the solicitation of the incubator for the creation of a start-up. E-guitare was the support of a computer science PhD [38]. It was conducted in partnership with the Region's National Conservatory (CNR) [39] and two teachers, Patrick Sida and David Hoarau, who supplied the pieces in classical guitar with their pedagogy. The starting point is the presentation of a course with a teacher. We sought to reproduce the flow of information involved in their lessons, adding the interactive dimension. Compared to the technological context of the time, it appeared that the DVD medium was the most suitable, both in terms of capacity, standardization, or cost of access.

Business and usage objects instantiation
The vision in the building process is to "bring the teacher at home" to play classical guitar pieces. It results in the following objectives: The system should provide multi-angle viewing of the teacher who plays the piece. At any time, the learner can switch from one view to another in real time and in full screen, the principle being to learn by imitation, looking at the model and replicating the gestures. Another fundamental feature should be added to facilitate this process: a pre-calculated and contextual slow-motion mode allowing to halve the execution speed while maintaining an excellent audiovisual quality. Then, stepping into the piece is done segment by segment relative to a reference that is the score or the musical structure (intro, verse, chorus, ...). Learning occurring through repetition, a double loop system (pre-set by the designers or customized by the user) must be implemented.
The question of identity in the appropriation process arises from the start of the project: indeed, as the place of the user is central in the development, he must be involved in the construction of e-services (co-design). It turns out that the team members are themselves guitarists and early adopters. This feature is fundamental to the adequacy of the proposed vision and the problem to solve. The origin of the project is also the finding of a gap: even if the learners follow a course with a teacher, it is difficult for them to get help to solve technical problems in deciphering between courses, when left to one's own, resulting in a waste of time.
The activities for solving a music piece are conducted in the order shown in Fig. 11.   Fig. 11. The different activities for learning a piece of guitar We realize that the technical difficulties involved most of the student work time. The E-guitare project aims to the acquisition and transmission of knowledge of conservatory teachers and music schools (gestures, fingering of the right hand and left hand techniques and tips for delicate passages, etc.) on pieces they interpret. The project responds to a need for students and guitar enthusiasts to understand how to execute the parts of a repertoire of Spanish guitar, Brazilian, etc. in an academic and professional manner. There is a large unmet demand for guitar lessons and "good practices" for enthusiasts who are not teachers to support them in their learning. The conservatory is the place that guarantees quality of education to progress in learning the right techniques, i.e. the independence of the fingers of the right hand, etc.
Tool development tasks have focused on technical assistance for the student to correctly solve the difficult passages of the piece (karaoke, slow motion, looping, advice, etc.). They are then strung together naturally by dividing the sub-tasks within the project team composed of graphic designers and computer scientists.
The peculiarity of the designer/user has had a very positive impact on the rate of progression of tasks to be solved with a plan, because the first feedbacks have been very fast. The iterative development process could be very quick at the beginning and transparently (orally) with this internal evaluation. Subsequently, we logically opened the tool to new testers to conduct a more systematic external evaluation. Students of classical guitar class of CNR were naturally involved (teachers are our experts), but also independent people who represent our second type of public.
The evaluation was based on two constructs: the semi-quantitative approach, on the one hand, was based on questionnaires (either on paper or online). This allowed us to produce statistics relating to the types of users and their use of the system. For it to be significant, it necessitated the return of a large sample of questionnaires. The use of the IKBS tool [40], allowed us to determine user profiles (Fig. 12). It is therefore possible to personalize the content to be delivered to each user in accordance with their interest and experience. The qualitative approach, on the other hand, produced information regarding system usage. It was based on actual situations and filmed focus groups on the CdP (see Fig. 6) and was followed up with interviews of individuals and/or testing groups. The test highlighted faults in ergonomics, evaluated the popularity of the applications and discussed deficiencies. The conditions of the experiment were supposed to resemble home use, but the presence of others as well as cameras clearly represented a bias, but one that was accepted in the end.
The sense of appreciation was much more apparent in focus groups, as opposed to the reaction to the questionnaire which was rather tedious. Volunteers found the process useful and were generally willing to cooperate. Beyond the above considerations, this type of operation was a strong sign of the users' implication in the development as it bears witness to the appropriation process proposed to them.
A communication infrastructure was then set up as a community Website, to organize exchanges between the various stakeholders: development team (researchers, engineers, graphic designers, video professionals, webmaster) guitar teachers, students and external consultants. The CdP gathering all these stakeholders first took the form of the Canter theater that served as a place of guitar pieces' registration, and offered the frame of reference for our Website [41]. Later, it also took the form of a work room putting testers in situation, and a virtual meeting of avatars in the e-campus project (Fig.  6).

E-guitar IAS instantiation
To illustrate the passage of the tool to the instrument with the IAS model, we take the example of conversion of the tool over time (CD-ROM, DVD-TV, DVD-ROM, FIGS) for some justified reasons related to its use. First, here is the cycle of evolution of the e-service until 2009 (Fig. 13).
Reflection on the E-guitar project began in 2002 with the design of a simulated model in QuickTime video that was later improved in 2003 (screens 1 and 2 in Fig. 13) and summarily implanted to make it interactive (CD -ROM).
This work was the basis of a request for financing E-guitar at the end of that year under the FEDER DOCUP 2000-2006 ICT funds. After acceptance of the application, the first DVD prototype was designed in 2004. The project leader has been trained in production tools (Final Cut Pro and DVD Studio Pro, Fig. 6 on the right) which enabled him to improve the interface thanks to feedback from designers/users (internal evaluation) for one year (screen 3 of Fig. 13).
The year 2005 was the beginning of the first public iteration (external evaluation). The first prototype implanted all the features (karaoke, time stretching, looping) and received a near trade dress. It was pressed at 500 copies. The test campaign that followed was spread over six months, to allow sufficient time for users to practice the DVD.
The semi-quantitative approach with the external questionnaire made with IKBS has not had the desired impact because of lower return rate than expected (one questionnaire on four was returned). After a quick survey of a selection of people, it appeared that the main causes of demotivation were the length of the questionnaire (up to 130 questions based on the experience of the tester, see Fig. 12) and its unpleasing and impersonal aspect. And yet, the DVD was a gift in return of the questionnaire! On the contrary, the qualitative approach was used to check that the features we developed were helpful, except for a hypothesis that could not be maintained: the choice to develop a DVD only on TV with the navigation remote control (Fig. 6 below). Indeed, the users work with this DVD to learn the pieces, and this usage value needs concentration. Television is a way for a family gathering around a movie in the living room and not a way to work its instrument, which is better done in a bedroom.
The proposed artifact with DVD-TV is not in line with the use scheme, so it had to evolve to go to the DVD-ROM media that can be run on a computer. This has had consequences on the ergonomics of the e-service which had to be reworked seriously in the prototype number 2 (clickable objects). In 2005, an economic and legal study was also conducted to find out the DVD market situation in France and the USA, actors and trends in costs (evaluation of the exchange value), intellectual property rights applicable, the types of contracts to be negotiated in the marketing phase [42].
Our DVD was then compared to a commercial product presented as similar. The testers were unanimous in confirming that our e-learning experience was far better than the commercial solution [38]. Points to review were at the level of ergonomics to simplify access based on the media (television or computer) and the lack of pedagogical speech from the teacher. Similarly, the public wanted greater diversity of styles and even other instruments.  Fig. 13), incorporating a dual control interface, with the remote control or with the mouse for a better return on your selection. Oral explanations sequences, called teaching tips were added contextually to the most complex passages, to offer problemsolving strategies. This version was distributed and evaluated on a large scale quantitatively, after a period of adjustments carried out internally by the designers/users. The project of incubation of a start-up for DVD production in instrumental e-learning was launched in early 2007 [43].
Typically, users are fond of communication, both from students to teachers or between learners themselves. The DVD is a medium suitable for transmission of knowledge from teachers to students. But when pressed or engraved, it is not possible to update it easily. Hence the idea of coupling it to an online service, which would restore a two-way dialogue between teachers and learners (screen 5 in Fig. 13). We developed a web application called FIGS (Flash Interactive Guitar Saloon, Fig. 4) playing the role of an audio-video forum suited to musical learning: the conceptual specificity comes from the ability to locate each contribution to a passage of the piece [44].
This period marks a transformation of the E-guitar tool on DVD (offline) to the Eguitar Web tool (Online). The community site is the living part of the project: it gives a support for DVD video, as an interactive service feedback when learning is made at home. With FIGS, we initialize a true collective work in music Teaching and Learning by Playing. Indeed, the Teaching mode is when the professor is distributing his interpretation of a piece on DVD. The Learning mode is when a student is working this piece at home with the quality of video and sound on DVD, and is asking questions to the professor by filming himself with his webcam. Note that video recordings of professors from different angles that were recorded in the DVD are also available in smaller format in FIGS. To ask a question about a passage, learners perform a marking (beginning -end) on the time slider and record video at home with their camera on the passages they want to show to the teacher. The community Web site will have to include a new usage value with the system of video glosses dedicated to learning musical pieces, as currently shown by services 2.0 of YouTube or Daily Motion for video.
The evaluation of the third public iteration therefore concerned an overall system consisting of two solutions, offline (DVD) and online (FIGS). The feedback was very positive because FIGS complements the DVD and enriches itself with discussions. It provides an accessible information service on guitar pieces based on natural media for the practice of the instrument. This new situation has not stopped investigations into each solution taken separately. The DVD video is thus the core of the e-service for Teaching and Learning pieces of music. The video glosses system complements the device to allow the exchange of techniques and interpretations of difficult passages. We thus move from an expert vision centered on the transmission of knowledge to a community vision centered on shared signs.
As shown in Fig. 4, the iterative process of development of an e-learning solution went on between 2009 and 2013 with another PhD in computer science based on playing the piano [45]. @-MUSE introduced the possibility for teachers and learners to annotate musical scores on tablets with personal videos explanations, for getting technical interpretations of signs thanks to the MusicXML representation format.

Conclusion
At the beginning of this work on Sign management, there was the term of gloss for discussing instrumental techniques, as we wanted to implement a video interpretations management system for FIGS with our teachers. That device revealed a new form of possible dialogue between learners and teachers in the field of music. Sign management is the new ecosystem of Knowledge management that we want to promote on our CdP. All areas of e-learning requiring visualization of know-how (gestures, hand, tips and tricks, glances) are concerned. Besides music, this can touch the culinary arts, dance, visual arts, crafts, observation guides, etc. In our case, the music domain was privileged because we are also musicians. As we know our limits in learning a musical instrument, we would like to benefit from such a service for ourselves. Experts are content producers that show their performance and explain their fingerings and gestures. We are computer scientists and editors who want to offer an ergonomic e-learning service to play efficiently musical pieces.
So we have to switch from the domain of Knowledge management focused on experts' representation of objects to the domain of Sign management dedicated also on the signification of objects from different subjects. Signification is the key psychological and constructivist process that makes sense for finding a consensus between people by sharing data, information and knowledge, i.e. Signs. And that's why the concept of Sign is more relevant than the one of Knowledge for biodiversity and music enhancement, because it includes the interpreter in the process of description of objects. To find shared usage values, we need to deal with living knowledge for making e-services with people and not only with specialists.
Sign management is also a bi-directional dialogue between teachers and learners. It stresses the interest of sharing subjects' interpretations by edutainment, i.e. Teaching and Learning by Playing with subjective know-how (glosses) of end-users, on top of transmission of fossilized objects, i.e. explicit knowledge of experts found in documents or books. This new framework tries to give sense to collaboration between all stakeholders (specialists, end-users, lead users) acting in their communities. When playing together, they can show their interpretations, explain why some are better than others, and find a consensus for being more objective, i.e. by confronting subjectivities ("show me how you do it!").
Sign management emphasizes the signification of objects by different subjects, i.e. the inscription of objects by subjects or the description of signed objects (sobjects?). It would allow each user to show their interpretations of objects with multimedia content (audio, video) annotated in textual descriptions.
The interest of Sign management is: 1) to share know-how between practitioners of a community who can play together 2) to emphasize the engineering and use of data, information and knowledge from the viewpoint of a subject 3) this personalized approach is more user-centered-design.
Thus, our next step will be to develop a Sign Base Management System with its ISBS platform (Iterative Sign Base System) to share Signs (interpretations) on the Web in a collaborative way. The principle would be to increase IKBS semantic functionalities (ontologies, descriptions, classifications, identifications) with groupware, multimedia content annotation and geo localized immersion, so that both experts and amateurs can describe their interpretations in the form of inscriptions in signs bases.
These audio-visual inscriptions are the objects of human interpretation we seek to extract and manage because they coincide with a real demand [46]. The Co-design methodology that we propose for Sign management is based on the identification, extraction and conversion of these multimedia objects to know how to make things in signs bases and not only to know what are these things in knowledge bases. ISBS will be built as a new virtual platform in our Teaching and Learning by Playing Living Lab and tested on a Creativity Platform to handle activities in both artistic and scientific areas. It aims to produce innovative e-co-education services for managing signs collaboratively.


Proving Correctness of Imperative Programs by Linearizing Constrained Horn Clauses

We present a method for verifying the correctness of imperative programs which is based on the automated transformation of their specifications. Given a program prog, we consider a partial correctness specification of the form $\{\varphi\}$ prog $\{\psi\}$, where the assertions $\varphi$ and $\psi$ are predicates defined by a set Spec of possibly recursive Horn clauses with linear arithmetic (LA) constraints in their premise (also called constrained Horn clauses). The verification method consists in constructing a set PC of constrained Horn clauses whose satisfiability implies that $\{\varphi\}$ prog $\{\psi\}$ is valid. We highlight some limitations of state-of-the-art constrained Horn clause solving methods, here called LA-solving methods, which prove the satisfiability of the clauses by looking for linear arithmetic interpretations of the predicates. In particular, we prove that there exist some specifications that cannot be proved valid by any of those LA-solving methods. These specifications require the proof of satisfiability of a set PC of constrained Horn clauses that contain nonlinear clauses (that is, clauses with more than one atom in their premise). Then, we present a transformation, called linearization, that converts PC into a set of linear clauses (that is, clauses with at most one atom in their premise). We show that several specifications that could not be proved valid by LA-solving methods, can be proved valid after linearization. We also present a strategy for performing linearization in an automatic way and we report on some experimental results obtained by using a preliminary implementation of our method.

Introduction
One of the most established methodologies for specifying and proving the correctness of imperative programs is based on the Floyd-Hoare axiomatic approach (see (Hoare 1969), and also (Apt et al. 2009) for a recent presentation dealing with both sequential and concurrent programs). By following this approach, the partial correctness of a program prog is formalized by a triple {ϕ} prog {ψ}, also called partial correctness specification, where the precondition ϕ and the postcondition ψ are assertions in first order logic, meaning that if the input values of prog satisfy ϕ and program execution terminates, then the output values satisfy ψ.
It is well-known that the problem of checking partial correctness of programs with respect to given preconditions and postconditions is undecidable. In particular, the undecidability of partial correctness is due to the fact that in order to prove in Hoare logic the validity of a triple {ϕ} prog {ψ}, one has to look for suitable auxiliary assertions, the so-called invariants, in an infinite space of formulas, and also to cope with the undecidability of logical consequence.
Thus, the best way of addressing the problem of the automatic verification of programs is to design incomplete methods, that is, methods based on restrictions of first order logic, which work well in the practical cases of interest. To achieve this goal, some methods proposed in the literature in recent years use linear arithmetic constraints as the assertion language and constrained Horn clauses as the formalism to express and reason about program correctness (Bjørner et al. 2012;De Angelis et al. 2014a;Grebenshchikov et al. 2012;Jaffar et al. 2012;Peralta et al. 1998;Podelski and Rybalchenko 2007;Rümmer et al. 2013).
Constrained Horn clauses are clauses with at most one atom in their conclusion and a conjunction of atoms and constraints over a given domain in their premise. In this paper we will only consider constrained Horn clauses with linear arithmetic constraints. The use of this formalism has the advantage that logical consequence for linear arithmetic constraints is decidable and, moreover, reasoning within constrained Horn clauses is supported by very effective automated tools, such as Satisfiability Modulo Theories (SMT) solvers (de Moura and Bjørner 2008;Cimatti et al. 2013;Rümmer et al. 2013) and constraint logic programming (CLP) inference systems (Jaffar and Maher 1994). However, current approaches to correctness proofs based on constrained Horn clauses have the disadvantage that they only consider specifications whose preconditions and postconditions are linear arithmetic constraints.
In this paper we overcome this limitation and propose an approach to proving general specifications of the form {ϕ} prog {ψ}, where ϕ and ψ are predicates defined by a set of possibly recursive constrained Horn clauses (not simply linear arithmetic constraints), and prog is a program written in a C-like imperative language.
First, we indicate how to construct a set PC of constrained Horn clauses (PC stands for partial correctness), starting from: (i) the assertions ϕ and ψ, (ii) the program prog, and (iii) the definition of the operational semantics of the language in which prog is written, such that, if PC is satisfiable, then the partial correctness specification {ϕ} prog {ψ} is valid.
Then, we formally show that there are sets PC of constrained Horn clauses encoding partial correctness specifications, whose satisfiability cannot be proved by current methods, here collectively called LA-solving methods (LA stands for linear arithmetic). This limitation is due to the fact that LA-solving methods try to prove satisfiability by interpreting the predicates as linear arithmetic constraints.
For these problematic specifications, the set PC of constrained Horn clauses contains nonlinear clauses, that is, clauses with more than one atom in their premise.
Next, we present a transformation, which we call linearization, that converts the set PC into a set of linear clauses, that is, clauses with at most one atom in their premise. We show that linearization preserves satisfiability and also increases the power of LA-solving, in the sense that several specifications that could not be proved valid by LA-solving methods, can be proved valid after linearization. Thus, linearization followed by LA-solving is strictly more powerful than LA-solving alone.
The paper is organized as follows. In Section 2 we show how a class of partial correctness specifications can be translated into constrained Horn clauses. In Section 3 we prove that LA-solving methods are inherently incomplete for proving the satisfiability of constrained Horn clauses. In Section 4 we present a strategy for automatically performing the linearization transformation, we prove that it preserves LA-solvability, and (in some cases) it is able to transform constrained Horn clauses that are not LA-solvable into constrained Horn clauses that are LA-solvable. Finally, in Section 5 we report on some preliminary experimental results obtained by using a proof-of-concept implementation of the method.

Translating Partial Correctness into Constrained Horn Clauses
We consider a C-like imperative programming language with integer variables, assignments, conditionals, while loops, and goto's. An imperative program is a sequence of labeled commands (or commands, for short), and in each program there is a unique halt command that, when executed, causes program termination.
The semantics of our language is defined by a transition relation, denoted =⇒, between configurations. Each configuration is a pair ℓ : c, δ of a labeled command ℓ : c and an environment δ. An environment δ is a function that maps every integer variable identifier x to its value v in the integers Z. The definition of the relation =⇒ is similar to that of the 'small step' operational semantics presented in (Reynolds 1998), and is omitted. Given a program prog, we denote by ℓ 0 : c 0 its first labeled command.
We assume that all program executions are deterministic in the sense that, for every environment δ 0 , there exists a unique, maximal (possibly infinite) sequence of configurations, called computation sequence, of the form: ℓ 0 : c 0 , δ 0 =⇒ ℓ 1 : c 1 , δ 1 =⇒ · · ·. We also assume that every finite computation sequence ends in the configuration ℓ h : halt, δ n , for some environment δ n . We say that a program prog terminates for δ 0 iff the computation sequence starting from the initial configuration ℓ 0 : c 0 , δ 0 is finite.

Specifying Program Correctness
First we need the following notions about constraints, constraint logic programming, and constrained Horn clauses. For related notions with which the reader is not familiar, he may refer to (Jaffar and Maher 1994;Lloyd 1987).
A constraint is a linear arithmetic equality (=) or inequality (>) over the integers Z, or a conjunction or a disjunction of constraints. For example, 2 ·X ≥ 3 ·Y − 4 is a constraint. We feel free to say 'linear arithmetic constraint', instead of 'constraint'. We denote by C LA the set of all constraints. An atom is an atomic formula of the form p(t 1 , . . . , t m ), where p is a predicate symbol not in {=, >} and t  , . . . , t m are terms. Let Atom be the set of all atoms. A definite clause is an implication of the form A ← c, G, where in the conclusion (or head ) A is an atom, and in the premise (or body) c is a constraint, and G is a (possibly empty) conjunction of atoms. A constrained goal (or simply, a goal ) is an implication of the form false ← c, G. A constrained Horn clause (CHC) (or simply, a clause) is either a definite clause or a constrained goal. A constraint logic program (or simply, a CLP program) is a set of definite clauses. A clause over the integers is a clause that has no function symbols except for integer constants, addition, and multiplication by integer constants.
The semantics of a constraint c is defined in terms of the usual interpretation, denoted by LA, over the integers Z. We write LA |= c to denote that c is true in LA. Given a set S of constrained Horn clauses, an LA-interpretation is an interpretation for the language of S that agrees with LA on the language of the constraints. An LA-model of S is an LA-interpretation that makes all clauses of S true. A set of constrained Horn clauses is satisfiable if it has an LA-model. A CLP program P is always satisfiable and has a least LA-model, denoted M (P ). We have that a set S of constrained Horn clauses is satisfiable iff S = P ∪G, where P is a CLP program, G is a set of goals, and M (P ) |= G. Given a first order formula ϕ, we denote by ∃(ϕ) its existential closure and by ∀(ϕ) its universal closure.
Throughout the paper we will consider partial correctness specifications which are particular triples of the form {ϕ} prog {ψ} defined as follows.
We say that a functional Horn specification {ϕ} prog {ψ} is valid , or prog is partially correct with respect to ϕ and ψ, iff for all environments δ 0 and δ n , if M (Spec) |= pre(δ 0 (z 1 ), . . . , δ 0 (z s )) holds (in words, δ 0 satisfies pre) and ℓ 0 : c 0 , δ 0 =⇒ * ℓ h : halt, δ n holds (in words, prog terminates for δ 0 ) holds, then M (Spec) |= f (δ 0 (z 1 ), . . . , δ 0 (z s ), δ n (z k )) holds (in words, δ n satisfies the postcondition). The relation r prog computed by prog according to the operational semantics of the imperative language, is defined by the CLP program OpSem made out of: (i) the following clause R (where, as usual, variables are denoted by upper-case letters): where: (i.1) initCf (C 0 ,P 1 ,. . . ,P s ) represents the initial configuration C 0 , where the variables z 1 ,. . .,z s are bound to the values P 1 ,. . .,P s , respectively, and pre(P 1 ,. . .,P s ) holds, (i.2) reach(C 0 , C h ) represents the transitive closure =⇒ * of the transition relation =⇒, which in turn is represented by a predicate tr (C 1 , C 2 ) that encodes the operational semantics, that is, the interpreter of our imperative language, by relating a source configuration C 1 to a target configuration C 2 , (i.3) finalCf (C h , Z k ) represents the final configuration C h , where the variable z k is bound to the value Z k , and (ii) the clauses for the predicates pre(P 1 , . . . , P s ) and tr(C 1 ,C 2 ). The clauses for the predicate tr(C 1 ,C 2 ) are defined as indicated in (De Angelis et al. 2014a), and are omitted for reasons of space.
Example 1 (Fibonacci Numbers) Let us consider the following program fibonacci, that returns as value of u the n-th Fibonacci number, for any n (≥ 0), having initialized u to 1 and v to 0. 0: while (n>0) { t=u; u=u+v; v=t; n=n-1 } fibonacci h: halt The following is a functional Horn specification of the partial correctness of the program fibonacci: {n=N, N>=0, u=1, v=0, t=0} fibonacci {fib(N,u)} ( ‡) where N is a parameter and fib is defined by the following CLP program: For reasons of conciseness, in the above specification ( ‡) we have slightly deviated from Definition 1. In particular, we did not introduce the predicate symbol pre, and in the precondition and postcondition we did not introduce the parameters which have constant values.
The relation r fibonacci computed by the program fibonacci according to the operational semantics, is defined by the following CLP program: where: (i) firstCmd(LC) holds for the command with label 0 of the program fibonacci; (ii) env((x,X),E) holds iff in the environment E the variable x is bound to the value of X; (iii) in the initial configuration C0 the environment E binds the variables n, u, v, t to the values N (>=0), 1, 0, and 0, respectively; and (iv) haltCmd(LC) holds for the labeled command h: halt.

Encoding Specifications into Constrained Horn Clauses
In this section we present the encoding of the validity problem of functional Horn specifications into the satisfiability problem of CHC's.
For reasons of simplicity we assume that in Spec no predicate depends on f (possibly, except for f itself), that is, Spec can be partitioned into two sets of clauses, call them F def and Aux , where F def is the set of clauses with head predicate f, and f does not occur in Aux. Theorem 1 (Partial Correctness) Let F pcorr be the set of goals derived from F def as follows : where Z is a new variable, and (3) goal G is replaced by the following two goals: The proof of this theorem and of the other facts presented in this paper can be found in the online appendix. In our Fibonacci example (see Example 1) the set F def of clauses is the entire set Spec fibonacci and Aux = ∅. According to Points (1)-(3) of Theorem 1, from Spec fibonacci we derive the following six goals: Thus, in order to prove the validity of the specification ( ‡) above, since Aux = ∅, it is enough to show that the set PC fibonacci = {G1,. . . , G6} ∪ OpSem fibonacci of CHC's is satisfiable.

A Limitation of LA-solving Methods
Now we show that there are sets of CHC's that encode partial correctness specifications whose satisfiability cannot be proved by LA-solving methods. A symbolic interpretation is a function Σ : Atom −→ C LA such that, for every A ∈ Atom and substitution ϑ, Σ(Aϑ) = Σ(A)ϑ. Given a set S of CHC's, a symbolic We say that a set S of CHC's is LA-solvable if there exists an LA-solution of S . Clearly, if a set of CHC's is LA-solvable, then it is satisfiable. The converse does not hold as we now show.

Theorem 2
There are sets of constrained Horn clauses which are satisfiable and not LA-solvable.
Proof. Let PC fibonacci be the set of clauses that encode the validity of the Fibonacci specification ( ‡). PC fibonacci is satisfiable, because r fibonacci(N, F) holds iff F is the N-th Fibonacci number, and hence the bodies of G1, . . . , G6 are false. (This fact will also be proved by the automatic method presented in Section 4.) Now we prove, by contradiction, that PC fibonacci is not LA-solvable. Suppose that there exists an LA-solution Σ of PC fibonacci . Let Σ(r fibonacci(N, F)) be a constraint c(N, F). To keep our proof simple, we assume that c(N, F) is defined by a conjunction of linear arithmetic inequalities (that is, c(N, F) is a convex constraint), but our argument can easily be generalized to any constraint in C LA . By the definition of LA-solution, we have that: Property (P 1) follows from the fact that, in particular, an LA-solution satisfies goal G5. Property (P 2) follows from the fact that an LA-solution satisfies all clauses of OpSem fibonacci and M (OpSem fibonacci ) defines the least r fibonacci relation that satisfies those clauses.
From Property (P 2) and from the fact that r fibonacci(N, F) holds iff F is the N-th Fibonacci number (and hence F is an exponential function of N), it follows that Figure 1. The relation r fibonacci(N,F) and the convex constraint c(N,F).
By replacing c(N1,F1), c(N2,F2), and c(N3,F3) by the corresponding conjunctions of atomic constraints of the forms (A) and (B), and eliminating the occurrences of F1, F2, N2, and N3, from (P 1) we get: where, for i = 1, . . . , n, p i is a linear polynomial in the variable N1. Then, the constraint N1≥0, F3 > p 1 , . . . , F3 > p n is satisfiable and Property (P 3) is false. Thus, the assumption that PC fibonacci is LA-solvable is false, and we get the thesis.

Increasing the Power of LA-Solving Methods by Linearization
A weakness of the LA-solving methods is that they look for LA-solutions constructed from single atoms, and by doing so they may fail to discover that a goal is satisfiable because a conjunction of atoms in its premise is unsatisfiable, in spite of the fact that each of its conjoint atoms is satisfiable. For instance, in our Fibonacci example the premise of goal G5 contains three atoms with predicate r fibonacci and our proof of Section 3 shows that, even if the premise of G5 is unsatisfiable, there is no constraint which is an LA-solution of the clauses defining r fibonacci that, when substituted for each r fibonacci atom, makes that premise false. Thus, the notion of LA-solution shows some weakness when dealing with nonlinear clauses, that is, clauses whose premise contains more than one atom (besides constraints). In this section we present an automatic transformation of constrained Horn clauses that has the objective of increasing the power of LA-solving methods.
The core of the transformation, called linearization, takes a set of possibly nonlinear constrained Horn clauses and transforms it into a set of linear clauses, that is, clauses whose premise contains at most one atom (besides constraints). After performing linearization, the LA-solving methods are able to exploit the interactions among several atoms, instead of dealing with each atom individually. In particular, an LA-solution of the linearized set of clauses will map a conjunction of atoms to a constraint. We will show that linearization preserves the existence of LA-solutions and, in some cases (including our Fibonacci example), transforms a set of clauses which is not LA-solvable into a set of clauses that is LA-solvable.
Our transformation technique is made out of the following two steps: (1) RI: Removal of the interpreter, and (2) LIN: Linearization. These steps are performed by using the transformation rules for CLP programs presented in (Etalle and Gabbrielli 1996), that is: unfolding (which consists in applying a resolution step and a constraint satisfiability test), definition (which introduces a new predicate defined in terms of old predicates), and folding (which redefines old predicates in terms of new predicates introduced by the definition rule).

RI: Removal of the Interpreter
This step is a variant of the removal of the interpreter transformation presented in (De Angelis et al. 2014a). In this step a specialized definition for r prog is derived by transforming the CLP program OpSem, thereby getting a new CLP program OpSem RI where there are no occurrences of the predicates initCf, finalCf, reach, and tr, which as already mentioned encodes the interpreter of the imperative language in which prog is written. (See online appendix for more details.) By a simple extension of the results presented in (De Angelis et al. 2014a), it can be shown that the RI transformation always terminates, preserves satisfiability, and transforms OpSem into a set of linear clauses over the integers. It can also be shown that the removal of the interpreter preserves LA-solvability. Thus, we have the following result.

Theorem 3
Let OpSem be a CLP program constructed starting from any given imperative program prog. Then the RI transformation terminates and derives a CLP program OpSem RI such that: (1) OpSem RI is a set of linear clauses over the integers; ( In the Fibonacci example, the input of the RI transformation is OpSem fibonacci . The output of the RI transformation consists of the following three clauses: where r is a new predicate symbol introduced by the RI transformation. As stated by Theorem 3, OpSem RI is a set of clauses over the integers. Since the clauses of the specification Spec define computable functions from Z s to Z, without loss of generality we may assume that also the clauses in Aux ∪ F pcorr are over the integers (Sebelik and Stepánek 1982). From now on we will only deal with clauses over the integers, and we will feel free to omit the qualification 'over the integers'.

LIN: Linearization
The linearization transformation takes as input the set OpSem RI ∪ Aux ∪ F pcorr of constrained Horn clauses and derives a new, equisatisfiable set TransfCls of linear constrained Horn clauses.
In order to perform linearization, we assume that Aux is a set of linear clauses. This assumption, which is not restrictive because any computable function on the integers can be encoded by linear clauses (Sebelik and Stepánek 1982), simplifies the proof of termination of the transformation.
The linearization transformation is described in Figure 2. Its input is constructed by partitioning OpSem RI ∪ Aux ∪ F pcorr into a set LCls of linear clauses and a set NLGls of nonlinear goals. LCls consists of Aux, OpSem RI (which, by Theorem 3, is a set of linear clauses), and the subset of linear goals in F pcorr . NLGls consists of the set of nonlinear goals in F pcorr .
When applying linearization we use the following transformation rule.  It is easy to see that, since LCls is a set of linear clauses, only a finite number of new predicates can be introduced by any sequence of applications of Definition & Folding, and hence the linearization transformation terminates. Moreover, the use of the unfolding, definition, and folding rules according to the conditions indicated in (Etalle and Gabbrielli 1996), guarantees the equivalence with respect to the least LA-model, and hence the equisatisfiability of LCls ∪ Gls and TransfCls. Thus, we have the following result.

Theorem 4 (Termination and Correctness of Linearization)
Let LCls be a set of linear clauses and Gls be a set of nonlinear goals. The linearization transformation terminates for the input set of clauses LCls ∪ Gls, and the output TransfCls is a set of linear clauses. Moreover, LCls ∪ Gls is satisfiable iff TransfCls is satisfiable.
Let us consider again the Fibonacci example. We apply the linearization transformation to the set {E1,E2,E3} of linear clauses, and to the nonlinear goal G5. For brevity, we omit to consider the cases where the goals G1, . . . ,G4,G6 are taken as input to the linearization transformation.
After Initialization we have that NLCls = {G5}, Defs = ∅, and TransfCls = {E1,E2,E3}. By applying the Unfolding step to G5 we derive: The transformation terminates when all clauses derived by unfolding can be folded using clauses in Defs, without introducing new predicates. The output of the transformation is a set of linear clauses (listed in the online appendix) which is LA-solvable, as reported on line 4 of Table 1 in the next section.
In general, there is no guarantee that we can automatically transform any given satisfiable set of clauses into an LA-solvable one. In fact, such a transformation cannot be algorithmic because, for constrained Horn clauses, the problem of satisfiability is not semidecidable, while the problem of LA-solvability is semidecidable (indeed, the set of symbolic interpretations is recursively enumerable and the problem of checking whether or not a symbolic interpretation is an LA-solution is decidable). However, the linearization transformation cannot decrease LA-solvability, as the following theorem shows. Theorem 5 (Monotonicity with respect to LA-Solvability) Assume that by applying the linearization transformation to a set LCls ∪ Gls of CHC's, we obtain a set TransfCls. If LCls ∪ Gls is LA-solvable, then TransfCls is LA-solvable.
Since there are cases where LCls ∪ Gls is not LA-solvable, while TransfCls is LA-solvable (see the Fibonacci example above and some more examples in the following section), as a consequence of Theorem 5 we get that the combination of LA-solving and linearization is strictly more powerful than LA-solving alone.

Experimental Results
We have implemented our verification method by using the VeriMAP system (De Angelis et al. 2014b). The implemented tool consists of four modules, which we have depicted in Figure 3. The first module, given the imperative program prog and its specification Spec, generates the set PC of constrained Horn clauses (see Theorem 1). PC is then given as input to the module RI that removes the interpreter. Then, the module LIN performs the linearization transformation. Finally, the resulting linear clauses are passed to the LA-solver, consisting of VeriMAP together with an SMT solver, which is either Z3 (de Moura and Bjørner 2008) or MathSAT (Cimatti et al. 2013) or Eldarica (Rümmer et al. 2013). We performed an experimental evaluation on a set of programs taken from the literature, including some programs from (Felsing et al. 2014) obtained by applying strength reduction, a real-world optimization technique 1 . In Table 1 we report the results of our experiments 2 .
One can see that linearization takes very little time compared to the total verification time. Moreover, linearization is necessary for the verification of 14 out of 19 programs (including fibonacci), which otherwise cannot be proved correct with respect to their specifications. In the two columns under LA-solving-1 we report the results obtained by giving as input to the Z3 and Eldarica solvers the set PC generated by the RI module. Under LA-solving-1 we do not have a column for MathSAT, because the version of this solver used in our experiments (namely, MSATIC3) cannot deal with nonlinear CHC's, and therefore it cannot be applied before linearization. In the last three columns of Table 1 we report the results obtained by giving as input to VeriMAP (and the solvers Z3, MatSAT, and Eldarica, respectively) the clauses obtained after linearization.
Unsurprisingly, for the verification problems where linearization is not necessary, our technique may deteriorate the performance, although in most of these problems the solving time does not increase much.

Conclusions and Related Work
We have presented a method for proving partial correctness specifications of programs, given as Hoare triples of the form {ϕ} prog {ψ}, where the assertions ϕ and ψ are predicates defined by a set of possibly recursive, definite CLP clauses. Our verification method is based on: Step (1) a translation of a given specification into a set of constrained Horn clauses (that is, a CLP program together with one or more goals), Step (2) an unfold/fold transformation strategy, called linearization, which derives linear clauses (that is, clauses with at most one atom in their body), and Step (3) an LA-solver that attempts to prove the satisfiability of constrained Horn clauses by interpreting predicates as linear arithmetic constraints.
We have formally proved that the method which uses linearization is strictly more powerful than the method that applies Step (3) immediately after Step (1). We have also developed a proof-of-concept implementation of our method by using the Ver-iMAP verification system (De Angelis et al. 2014b) together with various state-ofthe-art solvers (namely, Z3 (de Moura and Bjørner 2008), MathSAT (Cimatti et al. 2013), and Eldarica (Rümmer et al. 2013)), and we have shown that our method works on several verification problems. Although these problems refer to quite simple specifications, some of them cannot be solved by using the above mentioned solvers alone.
The use of transformation-based methods in the field of program verification has recently gained popularity (see, for instance, (Albert et al. 2007;De Angelis et al. 2014a;Fioravanti et al. 2013;Kafle and Gallagher 2015;Leuschel and Massart 2000;Lisitsa and Nemytykh 2008;Peralta et al. 1998)). However, fully automated methods based on various notions of partial deduction and CLP program specialization cannot achieve the same effect as linearization. Indeed, linearization requires the introduction of new predicates corresponding to conjunctions of old predicates, whereas partial deduction and program specialization can only introduce new predicates that correspond to instances of old predicates. In order to derive linear clauses, one could apply conjunctive partial deduction (De Schreye et al. 1999), which essentially is equivalent to unfold/fold transformation. However, to the best of our knowledge, this application of conjunctive partial deduction to the field of program verification has not been investigated so far.
The use of linear arithmetic constraints for program verification has been first proposed in the field of abstract interpretation (Cousot and Cousot 1977), where these constraints are used for approximating the set of states that are reachable during program execution (Cousot and Halbwachs 1978). In the field of logic programming, abstract interpretation methods work similarly to LA-solving for constrained Horn clauses, because they both look for interpretations of predicates as linear arithmetic constraints that satisfy the program clauses (see, for instance, (Benoy and King 1997)). Thus, abstract interpretation methods suffer from the same theoretical limitations we have pointed out in this paper for LA-solving methods.
One approach that has been followed for overcoming the limitations related to the use of linear arithmetic constraints is to devise methods for generating polynomial invariants and proving specifications with polynomial arithmetic constraints (Rodríguez-Carbonell and Kapur 2007a;Rodríguez-Carbonell and Kapur 2007b). This approach also requires the development of solvers for polynomial constraints, which is a very complex task on its own, as in general the satisfiability of these constraints on the integers is undecidable (Matijasevic 1970). In contrast, the approach presented in this paper has the objective of transforming problems which would require the proof of nonlinear arithmetic assertions into problems which can be solved by using linear arithmetic constraints. We have shown some examples (such as the fibonacci program) where we are able to prove specifications whose post-condition is an exponential function.
An interesting issue for future research is to identify general criteria to answer the following question: Given a class D of constraints and a class H of constrained Horn clauses, does the satisfiability of a finite set of clauses in H imply its D-solvability? Theorem 2 provides a negative answer to this question when D is the class of LA constraints and H is the class of all constrained Horn clauses.

Acknowledgments
We thank the participants in the Workshop VPT '15 on Verification and Program Transformation, held in London on April 2015, for their comments on a preliminary version of this paper. This work has been partially supported by the National Group of Computing Science (GNCS-INDAM).

Removal of the Interpreter
Here we report the variant of the transformation presented in (De Angelis et al. 2014a) that we use in this paper to perform the removal of the interpreter. In this transformation we use the function Unf (C , A, Cls) defined as the set of clauses derived by unfolding a clause C with respect to an atom A using the set Cls of clauses (see the unfolding rule in Section 4.2).
those atoms have no recursive clauses, (ii) by the definition of the semantics of the imperative program, the repeated unfolding of an atom of the form reach(cf 1 , cf 2 ) eventually derives a new reach(cf 3 , cf 4 ) atom where cf 3 is either a final configuration or a configuration associated with a while or goto command, and in both cases unfolding terminates. The termination of the Definition & Folding step follows from the fact that SpC is a finite set of clauses. The outer while loop terminates because a finite set of new predicate definitions of the form newp(V ) ← reach(cf 1 , cf 2 ) can be introduced. Indeed, each configuration cf is represented as a term cf(LC,E)), where LC is a labeled command and E is an environment (see Example 1). An environment is represented as a list of (v , X ) pairs where v is a variable identifier and X is its value, that is, a logical variable whose value may be subject to a given constraint. Considering that: (i) the labeled commands and the variable identifiers occurring in an imperative program are finitely many, and (ii) predicate definitions of the form newp(V ) ← reach(cf 1 , cf 2 ) abstract away from the constraints that hold on the logical variables occurring in cf 1 and cf 2 , we can conclude that there are only finitely many such clauses (modulo variable renaming).
Point 1: OpSem RI is a set of linear clauses over the integers. By construction, every clause in OpSem RI is of the form H ← c, B , where (i) H is either r prog (P 1 , . . . ,P s ,Z k ) or newp(V ), for some new predicate newp and tuple of variables V , and (ii) B is either absent or of the form newp(V ), for some new predicate newp and tuple of variables V . Thus, every clause is a linear clause over the integers.
Suppose that OpSem ∪ Aux ∪ F pcorr is LA-solvable, and let Σ be an LA-solution of OpSem ∪ Aux ∪ F pcorr . Now we construct an LA-solution Σ RI of OpSem RI ∪ Aux ∪ F pcorr . To this purpose it is enough to define a symbolic interpretation for the new predicates introduced by RI.
For any predicate newp introduced by RI via a clause of the form: we define a symbolic interpretation as follows: Σ RI (newp(V )) = Σ(reach(cf 1 , cf 2 )) Moreover, Σ RI is identical to Σ for the atoms with predicate occurring in OpSem.
Now we have to prove that Σ RI is indeed an LA-solution of OpSem RI ∪ Aux ∪ F pcorr . This proof is similar to the proof of Theorem 5 (actually, simpler, because RI introduces new predicates defined by single atoms, while LIN introduces new predicates defined by conjunctions of atoms), and is omitted.

Proof of Theorem 4
Let LCls be a set of linear clauses and Gls be a set of nonlinear goals. We split the proof of Theorem 4 in three parts: Termination: The linearization transformation LIN terminates for the input set of clauses LCls ∪ Gls; Linearity: The output TransfCls of LIN is a set of linear clauses; Equisatisfiability: LCls ∪ Gls is satisfiable iff TransfCls is satisfiable.
(Termination) Each Unfolding and Definition & Folding step terminates. Thus, in order to prove the termination of LIN it is enough to show that the while loop is executed a finite number of times, that is, a finite number of clauses are added to NLCls. We will establish this finiteness property by showing that there exists an integer M such that every clause added to NLCls is of the form: newp(X 1 , . . . , X t ) ← A 1 , . . . , A k ( †2) where: (i) k ≤ M , (ii) for i = 1, . . . , k , A i is of the form p(X 1 , . . . , X m ), and (iii) {X 1 , . . . , X t } ⊆ vars(A 1 , . . . , A k ).
Indeed, let M be the maximal number of atoms occurring in the body of a goal in Gls, to which NLCls is initialized. Now let us consider a clause C in NLCls and assume that in the body of C there are at most M atoms. The clauses in the set LCls used for unfolding C are linear, and hence in the body of each clause belonging to the set U (C ) obtained after the Unfolding step, there are at most M atoms. Thus, each clause in U (C ) is of the form H ← c, A 1 , . . . , A k , with k ≤ M . Since the body of every new clause introduced by the subsequent Definition & Folding step is obtained by dropping the constraint from the body of a clause in U (C ), we have that every clause added to NLCls is of the form ( †2), with k ≤ M . Thus, LIN terminates.
(Linearity) TransfCls is initialized to the set LCls of linear clauses. Moreover, each clause added to TransfCls is of the form H ← c, newp(X 1 , . . . , X t ), and hence is linear.
(Equisatisfiability) In order to prove that LIN ensures equisatisfiability, let us adapt to our context the basic notions about the unfold/fold transformation rules for CLP programs presented in (Etalle and Gabbrielli 1996).
Besides the unfolding rule of Section 4.2, we also introduce the following definition and folding rules.
Definition Rule. By definition we introduce a clause of the form newp(X ) ← G, where newp is a new predicate symbol and X is a tuple of variables occurring in G.
Folding Rule. Given a clause E : H ← c, G and a clause D : newp(X ) ← G intro-duced by the definition rule. Suppose that, X = vars(G) ∩ vars(H,c). Then by folding E using D we derive H ← c, newp(X ).
From a set Cls of clauses we can derive a new set TransfCls of clauses either by adding a new clause to Cls using the definition rule or by: (i) selecting a clause C in Cls, (ii) deriving a new set TransfC of clauses using one or more transformation rules among unfolding and folding, and (iii) replacing C by TransfC in Cls. We can apply a new sequence of transformation rules starting from TransfCls and iterate this process at will.
The following theorem is an immediate consequence of the correctness results for the unfold/fold transformation rules of CLP programs (Etalle and Gabbrielli 1996).
Theorem 6 (Correctness of the Transformation Rules) Let the set TransfCls be derived from Cls by a sequence of applications of the unfolding, definition and folding transformation rules. Suppose that every clause introduced by the definition rule is unfolded at least once in this sequence. Then, Cls is satisfiable iff TransfCls is satisfiable. Now, equisatisfiability easily follows from Theorem 6. Indeed, the Unfolding and Definition & Folding steps of LIN are applications of the unfolding, definition, and folding rules (strictly speaking, the rewriting performed after unfolding is not included among the transformation rules, but obviously preserves all LAmodels). Moreover, every clause introduced during the Definition & Folding step is added to NCls and unfolded in a subsequent step of the transformation. Thus, the hypotheses of Theorem 6 are fulfilled, and hence we have that LCls ∪ Gls is satisfiable iff TransfCls is satisfiable.
Linearized clauses for Fibonacci. The set of linear constrained Horn clauses obtained after applying LIN is made out of clauses E1, E2, E3, and C3, together with the following clauses: