Aïcha Bakki

Lahcen Oubahssi

Sébastien George

Design and Operationalization of Connectivist Activities: an Approach through Business Process Management

Keywords: TEL, MOOC, cMOOC, authoring tool, BPMN, connectivism. 1 Introduction: Motivation and Aims

The work presented in this paper focuses on massive open online course (MOOC) environments, and more specifically on the activity of designing and implementing pedagogical scenarios for a connectivist MOOC (cMOOC). This paper presents a research work, which aims to propose a model and tool to support the design of connectivist MOOC scenarios. The major contribution of this work is a visual authoring tool that is intended for the design and deployment of cMOOC-oriented scenarios. The tool is based on the BPMN notation that we have extended to suit our objectives. The tool was evaluated primarily from the point of view of utility and usability. The findings confirm that the tool can be used to design connectivist pedagogical scenarios and can provide all the necessary elements to operationalize such courses.

and the learner, the pedagogical aspects targeted and the openness and freedom granted to learners [START_REF] Bakki | MOOCAT: A visual authoring tool in the cMOOC context[END_REF]. Despite the potential benefits of cMOOCs, the literature review has shown that the most widely deployed types of MOOCs are xMOOCs. Based on an analysis of a panorama of 76 MOOCs, [START_REF] Toven-Lindsey | Virtually unlimited classrooms: Pedagogical practices in massive open online courses[END_REF] revealed that only 10% of these courses can be categorized as cMOOCs. This observation was addressed by [START_REF] Morrison | The ultimate student guide to xMOOCs and CMOOCs[END_REF] who explained this by pointing out that the majority of teachers do not feel confident and are lacking the technical skills to deal with connectivist environments that are mainly focused on the use of technology. We share this point of view, and believe that a limitation for the emergence of cMOOCs is the lack of methodologies, models and tools to support pedagogical scenario development [START_REF] Alario-Hoyos | Proposal for a Conceptual Framework for Educators to Describe andDesign MOOCs[END_REF] as the current literature provides a description of pedagogical practices in cMOOCs in a purely descriptive manner. Based on this observation, we have hypothesized that modeling a cMOOC scenario and reifying it in an information system that is easy to use by teachers with no computer expertise will help them to move toward this type of MOOC. Our objective is to assist the teacher-designer who desires to create a cMOOC to produce a pedagogical scenario that respects the specificity of this kind of learning environment. From a conceptual point of view, the major difficulties faced by teachers are, firstly, how to put in place a scenario that emphasizes the new roles played by the learner, and secondly, the lack of adequate tools and/or models for designing cMOOC scenarios without prior knowledge of the underlying pedagogical model. Indeed, in order to meet teachers' expectations, an idea is therefore to use the benefits of Business Process Model and Notation (BPMN). More especially as the latter has been able to stand out in the TEL field by its graphic notation easily understandable by different actors as it provides a set of generic business process elements, independently from a specific domain; its compliance with the standard and as it is intended for different audiences and especially for computer novice users [START_REF] Costa | BPMN 2.0 pour la modélisation et l'implémentation de dispositifs pédagogiques orientés processus[END_REF].

The remainder of the paper is structured as follow: in section 2, the cMOOC pedagogical scenario domain specifications are summarized. In section 3, we present overview of the BPMN and its benefits for connectivist context. In section 4, we present a brief description of the deployed extension design and method. Since the objective represents an artifact including extended notation and its technical implementation, section 5 present the proposed authoring tool. The section 6 highlights our proposal for the operationalization and deployment phase. The section 7 presents an evaluation of the proposed tool. The paper ends with a conclusion and an outlook on obtained results.

2

Characteristic of a cMOOC Pedagogical Scenario cMOOCs designate connectivist MOOCs driven by the principles of pedagogical innovation in a widely interconnected social learning mode. They are based on "a sophisticated and innovative design" of learning practices [START_REF] Clow | MOOCs and the funnel of participation[END_REF], and involves the promotion of learning through collaboration, production, sharing and connections between peers in quasi-total openness. The openness of cMOOCs might suggest that pedagogical scenario building is not essential, and that this would be contrary to the underlying principles of a connectivist course. However, we believe that connectivist course design can be enhanced by the implementation of scenario-building practices. Indeed, despite this openness, it is essential to create suitable conditions for the emergence of connectivist activities. In this sense, several solutions have been suggested to facilitate the implementation of such courses [START_REF] Adesina | Capturing and monitoring of learning process through a business process management (BPM) framework[END_REF][START_REF] Pettenati | Social Networking Theories and Tools to Support Connectivist Learning Activities[END_REF]. These studies focus on cMOOCs from a theoretical point of view, and aim to demonstrate the value of a methodology for the scenario development and implementation of connectivist courses. They also offer frameworks that describe the main axes of the design process and the implementation of a cMOOC course, but define the administrative aspects rather than the elements that should be contained by a cMOOC scenario [START_REF] Glance | The pedagogical foundations of massive open online courses[END_REF][START_REF] O'brien | Metaliteracy as Pedagogical Framework for Learner-Centered Design in Three MOOC Platforms: Connectivist, Coursera and Canvas[END_REF][START_REF] Pettenati | Social Networking Theories and Tools to Support Connectivist Learning Activities[END_REF]. These studies confirm that cMOOCs rely on a specific conceptual model to help teachers to conceive such courses, but they didn't provide neither a model to describe a cMOOC pedagogical scenario nor concrete and simple software tools to design and deploy connectivist MOOCs.

One of the major difficulties faced by teachers wanting to design such courses is to determine how to model educational activities within this connectivist context. The issue lies in creating pedagogical and monitoring scenarios to support learners so that they do not feel overwhelmed. Designing such scenarios is challenging, since it requires an effective collaboration between the teacher and learners throughout the course. Another difficulty involves setting up cMOOCs in order to respects the freedom of learners to define their own educational objectives. In this perspective, teachers should not establish a specific linear course plan, but should suggest resources and activities that can guide learners toward the main objective of the cMOOC and then encourage them to create, produce and collaborate. These complexities require some mechanisms and methods that can guide and support teachers in the design of the cMOOC.

Pedagogical questions have been raised and constitute one of the major criteria to characterize cMOOCs. In this sense, a study of the pedagogical practices of a connectivist course is essential to define the elements that regulate a cMOOC scenario and model them. That being said, we had to conduct a literature review on the pedagogical aspects of cMOOCs. In accordance with the theoretical grounding of the connectivist approach, we found that cMOOCs are structured into four essential activities [START_REF] Downes | Places to go: Connectivism & connective knowledge[END_REF][START_REF] Kop | The Challenges to Connectivist Learning on Open Online Networks: Learning Experiences during a Massive Open Online Course[END_REF]: Aggregating activities aim to encourage learners to read and consult the content and resources that are most relevant to their learning objectives. The learners are encouraged to read, choose and filter what is most relevant and appropriate to achieve their personal learning objectives. Remixing activities can be defined as interpreting the information collected during the aggregation phase and searching for relevant additional resources. Repurposing activities aim to support learners through an individual or group production process. Feed forwarding activities aim to encourage learners to share their products over the web. These are essentially transmission activities. We assume that a cMOOC scenario should contain all four groups of activities presented above. In the remainder of this paper, we will explain how we purposed to conceptualize this theoretical fundament through a technology-aware framework.

BPMN as Pedagogical Language in cMOOC Context

Before the advent of Learning Design (LD) tools, teachers used to create their scenarios using a narrative textual format. Such scenarios do not use a standardized template, meaning that it is difficult to disseminate and reuse them [START_REF] Katsamani | Orchestrating learning activities using the CADMOS learning design tool[END_REF], and thus the IMS-LD specification emerged [START_REF] Consortium | IMS learning design specification[END_REF]. IMS-LD is essentially a description language that allows to model the lesson plan and describes roles and activities without handling the implementation processes [START_REF] Costa | BPMN 2.0 pour la modélisation et l'implémentation de dispositifs pédagogiques orientés processus[END_REF]. Since IMS-LD is not an easy-to-understand process for the teachers [START_REF] Adesina | Capturing and monitoring of learning process through a business process management (BPM) framework[END_REF][START_REF] Morrison | The ultimate student guide to xMOOCs and CMOOCs[END_REF], the first generation of LD authoring tools was proposed. A significant number of research works has proposed tools and languages to help with the visualization of learning designs, and these works can be divided into two main groups. The first concerns solutions that provide specific notations for the creation of a pedagogical scenario, but that are not implemented in a tool. The second group concerns visual modeling tools that offer teachers more abstract languages; these are visual or graphical tools, and their use is more intuitive [START_REF] Barchino | Interoperability between visual UML design applications and authoring tools for learning design[END_REF]. Thus far, none of these tools have allowed teachers to design cMOOC and to automatically deploy them on a platform. In addition, some of these LD tools are directed toward a particular pedagogical approach, are specific to a particular platform, or meets the requirement of the IMS-LD standard which does not correspond to our needs because although it is a so-called pedagogically neutral standard, it has shown its limits for designing collaborative and constructivist situations [START_REF] Britain | A review of learning design: concept, specifications and tools[END_REF][START_REF] Ferraris | Handbook of visual languages for instructional design: Theories and practices[END_REF]. Other works were inspired by business modeling, and specifically by the workflow approach. In this sense, BPMN is offered as an alternative to LD languages. Several studies have been conducted [START_REF] Adesina | Capturing and monitoring of learning process through a business process management (BPM) framework[END_REF][START_REF] Costa | BPMN 2.0 pour la modélisation et l'implémentation de dispositifs pédagogiques orientés processus[END_REF] to illustrate and support the use of this workflow language within the LD process. BPMN has stood out in the educational field due to its advantages and in particular its expressiveness, its simplicity of use and the graphical representation of pedagogical scenarios.

The LD tools have advantages and disadvantages that influence their use and execution. Several studies have been carried out to specify the requirements and/or needs for LD tools and languages [START_REF] Botturi | A classification framework for educational modeling languages in instructional design[END_REF]25]. According to these works, from a techno-descriptive point of view, BPMN has several advantages that offer a teacher an intuitive tool, through its visual notation, its formal character and its level of stratification in layers that offers a different representation for each modeling element. From a pedagogical point of view, BPMN allows the representation of learning modalities by specifying the different activities, their dependencies and especially by offering the possibility to define a non-linear pedagogical scenario with several connections.

According to [START_REF] Ferraris | Handbook of visual languages for instructional design: Theories and practices[END_REF], when a learning environment model is confronted with significant variations in its initial conditions, the adaptation of the model that supposedly represents it becomes very difficult: this is the case of connectivism approach. Hence, to successfully cope with the complexity of the cMOOC learning process and its dynamics the targeted LD systems have to facilitate the cMOOC scenario design process in its entirety. Such support must include tools that provide a support for all components of the process, as well as possibilities to simply manage changes in that process. Based on all the points above, one possible approach to provide such a support might be a reuse of the experiences, and practices from business processes. Reusing the BPM notation and extending it with domain-specific concepts are expected to be less expensive than deploying a domain specific modeling language from scratch. However, in order to meet our objective to offer the teacher support in the design of cMOOC-oriented pedagogical scenarios, the use of BPMN is not directly conceivable. Since BPM notations are meta-modeling notations, a pedagogy-specific vocabulary based on these abstract elements should be constructed [START_REF] Helic | Technology-supported management of collaborative learning processes[END_REF]. In this sense, there are research developments that need to be realized for a successful application of BPMN in our context. Those developments aim to support the whole cycle of a cMOOC pedagogical scenario, i.e., first, facilities for conceiving cMOOC scenarios are addressed; and second, mechanisms for automatic mapping, deploying, and executing of pedagogical scenario within the available Learning Management Systems (LMS) are taken into account. To do so, we have to first propose an extension of the BPMN concept to take into account the specificities of a cMOOC-oriented pedagogical scenario (section 4). Then, we embed the extended meta-model and notation in an authoring tool (sections 5 and 6). Finally, we develop a mapping and automatic-deployment service to existing LMS (section 7).

BPM Notation and Meta-model Extension

In 2011, OMG introduced the latest version of BPMN: BPMN 2.0. The BPMN 2.0 specifications define the different graphical notations that form the basic set of BPMN elements. It is one of very few modeling languages that provides generic extension elements within the meta-model that enables the definition of domain-specific language extensions [START_REF] Omg | Business Process Model and Notation[END_REF]. Nevertheless, BPMN does not provide any methodological guidance or support to comply with domain-specific extension issues. In this sense, [START_REF] Stroppi | Extending BPMN 2.0: method and tool support[END_REF] [9] proposed an extension of [START_REF] Stroppi | Extending BPMN 2.0: method and tool support[END_REF] method by integrating the analysis of the domain and its conceptualization. The authors proclaim that for a domain-specific extension, a domain requirement analysis is important in order to explicit all the necessary concepts of the domain and its semantics, and to consider whether the domain-specific concept is semantically equivalent to an existing BPMN element or not. As our aim is to propose a cMOOC pedagogical scenario specific extension, we consider as necessary to integrate the equivalence check procedure proposed by the authors. For this purpose, we are illustrating essentially how the first two steps of the [START_REF] Stroppi | Extending BPMN 2.0: method and tool support[END_REF] procedure model will be applied. We also add an Equivalence Mapping according to Equivalence check procedure proposed by [START_REF] Braun | BPMN4CP: Design and implementation of a BPMN extension for clinical pathways[END_REF]. Referring to the presented process model (Fig. 1.) the design of the proposed extension is briefly presented below. Domain analysis. In order to conceptualize the targeted educational domain, we have analyzed the pedagogical concepts related to the connectivist approach, and we propose a model, named cORPS [START_REF] Bakki | A Model to Assist Pedagogical Scenario Building Process in cMOOCs[END_REF] , that allows expressing the structural properties specific to a connectivist environment as well as the temporal properties. Equivalence Mapping. The BPMN extension is based on specific domain concepts of our proposed Model. Each of these concepts are semantically compared to the BPMN concepts in order to define the needed extension in form of a new element or properties.

As result of equivalence mapping a classification of the connectivist element as BPMN element or as an extension concept is made. The first one refers to the elements of our model that has an equivalent BMPN concept and second one corresponds to the elements who have no equivalent or who had no obvious semantic matching with standard elements, but rather situational discussion is necessary in order to provide arguments for a possible mapping. [START_REF] Stroppi | Extending BPMN 2.0: method and tool support[END_REF] we define an extension model (BPMN+X) by applying a set of transformation rules. The semantics and the abstract syntax of the extension model are based on BPMN extension mechanism. Depending on several rules in this phase [START_REF] Stroppi | Extending BPMN 2.0: method and tool support[END_REF], we had defined for each element, according to the domain specification, if we will use an existing BPMN element, define a new one or extend the attributes of the original BPMN elements; and how this changes will occur on BPMN meta-model. With the respect of the limited space of the paper, the entire transformation rules cannot be presented. Proposed Graphical Notation. We proposed an advanced concrete syntax that defines the specific new graphical representation. As defined by the [START_REF] Omg | Business Process Model and Notation[END_REF], the following extension can be made by: adding new markers or indicators, coloring graphical elements or changing the line style of a graphical element. According to these rules, Task elements are specified by colored borders and new markers that vary depending on the activity type. A pedagogical resource is represented as Data Object with a marker that reflects the selected Resource Type of the element. Subprocess line shape was also changed in order to differentiate it from generic Activity Element. The concrete graphical notation of the extension is presented in section 5.2.

MOOC Authoring Tool: Elements and Architecture

As described in section 3, BPMN represent a good alternative to conceive and deploy pedagogical scenarios, nevertheless it need of several adjustments to fulfill our conceptual needs. These adjustments can occur at three levels, namely: (1) the definition of pedagogical components based on cMOOC pedagogical principles. (2) The proposition of an authoring component for the creation of cMOOC learning procedures.

(3) The development an automatic or semi-automatic mechanism for mapping learning procedures onto the online learning infrastructure (existing LMS). The first level corresponds to the domain analysis phase mentioned in the section 3. As a result, we had proposed a cMOOC Pedagogical Scenario Model, named cORPS [START_REF] Bakki | A Model to Assist Pedagogical Scenario Building Process in cMOOCs[END_REF]. It allows expressing the structural properties specific to a connectivist environment, as well as the temporal properties. To describe a cMOOC, the pedagogical scenario is based on a semantic description of the course. It consists of a description of the activities and resources it contains, but also of the properties of these entities, as well as their organization. The role of the pedagogical scenario as we perceive it is not merely to describe the actions that the learner must perform to complete a task. The teachers express the organization of pedagogical activities and their sequencing, bearing in mind that participants will participate in these learning activities in a non-linear context, in a conditional way [START_REF] Kopp | Do Moocs Need a Special Instructional Design?[END_REF][START_REF] Sergis | Educational design for moocs: Design considerations for technology-supported learning at large scale[END_REF]. When the teachers create a pedagogical scenario, they have explicit access to these concepts, by creating a pedagogical workflow and then defining a temporal sequence of the proposed activities. They can also define different execution paths within the pedagogical scenario. In fact, activities are not necessarily organized in a sequential way. We have defined the root element by the scenario class, which is the entity that aggregates the different components of the pedagogical scenario. It is composed of one or several Learning Unit often with a fixed duration, usually equal to a week and can be composed of one or multiple lessons, which structure learning and assessment activities. A given activity can be assigned to one of the four categories: Aggregation (consultation and cognition), Remixing (communication, sharing and metacognition), Repurposing (production and collaboration) and Feed Forwarding (production sharing). We propose to add a category to the four categories corresponding to Evaluation activities (referring to evaluation activities: e-evaluation, peer evaluation or self-evaluation). Once the model scenario was defined, the aim was to embed it in a tool to design cMOOC-oriented scenarios. It is the main objective of the steps 2 and 3 cited above and described in the remainder of this section.

cMOOC Authoring Tool Architecture

In Section 3, we discussed the advantages of BPMN as a pedagogical modeling language. We should point out that this language has also been used to design various pedagogical situations in several contexts (face-to-face, hybrid, collaborative, etc.) [START_REF] Britain | A review of learning design: concept, specifications and tools[END_REF][START_REF] Omg | Business Process Model and Notation[END_REF]. However, as explained in section 3, in order to meet our requirements to provide the teacher with support for designing cMOOC-oriented pedagogical scenarios, the use of BPMN is not considered as it stands. The objective is not to rebuild a new platform, but to start from an existing tool and extend it. We therefore selected the BPMN.io tool, which is an open source web application that uses BPMN 2.0. The architecture of the BPMN.io application is composed of three main modules, as follows: Bpmn-js is the principal module of the tool, and controls the simple and visual human-computer interface used for creating, visualizing and validating BPMN schemas. This module displays and operates the toolbox elements, the modeling rules specific to BPMN 2.0, and the main modeling interface. It provides a viewer element for visualizing BPMN diagrams, and a modeler module to create, to edit and validate BPMN workflows. In this module, we have incorporated changes relating to the extension of the BPM notation and redefined the behavior of each element toolbox elements via the embedded business model expressed as a set of rules that regulates the behavior of each element. Bpmn-moddle embeds the metamodel defined by the BPMN 2.0 standard, and allows for mapping between the graphical notation and the elements of the BPMN metamodel. This module provides the appropriate modeling rules to validate BPMN workflows, and also allows reading and writing of XML files according to BPMN 2.0. In this module, we have added the elements of the our model through an extension of the BPMN metamodel.

We have also modified the moddle-XML file to allow the identification of objects added to the toolbox (new elements specific to the building of cMOOC scenarios) and to indicate how these will be represented in the BPMN workflow. Finally, Diagram-js provides features that display and memorize changes in BPMN workflows during the conception process. In this module, we define the graphical aspect of the new notation.

We add the MOOCAT ElementFactory module, which describes the visual appearance of each new element added to the toolbox and allows a mapping between the graphical representation and bpmn-moddle.

Fig. 2. Authoring Tool architecture

MOOCAT: Features and Interfaces

MOOCAT is a web application accessible via a web browser that not requires any prior installation. Once the teachers are connected to MOOCAT, they can either create a new scenario or modify an existing one (Fig. 3,B). In the following, we consider that the teacher choose to create a new scenario (Fig. 3,B). After specifying the name of their scenario and choosing the blank model, the teacher is redirected to the conception page (Fig. 3,C). When starting a scenario conception with MOOCAT, the teachers start by creating a learning session. They had access to it via the toolbox (Fig. 3. F) on the left under the "Learning session" block. In order to support the teachers, we propose to ensure that the modeling space (Fig3. D) is not empty when creating a new scenario. A first learning session is thus created by default. Commonly in MOOCs, one session represents one week. The teachers are then provided with an interface containing a pool, which can be renamed or deleted. They can then use the "Properties" section (Fig3. E) to specify the duration of this session (start date and end date). After creating there first session and specifying roles, the teachers can start creating there different lessons. We assume that a lesson is an entity that encompasses a number of activities. The teachers can thus continue his modeling by dragging from the toolbox the activities they want to model. In order to facilitate the identification of activities according to the four principles of a connectivist course, we have classified them into four blocks with different color codes. The different types of activities in the toolbox have been explicated in section 2. Each of the activities has its own properties. For example, for a consultation activity, the teachers specify whether it is a resource or an HTML page describing the activities to be carried out or presenting a description of the activity's progress. If it is a resource, they specify its type and the link to access it. Once the scenario modeling is complete, the teachers can possibly save the scenario in different formats (Fig3. D) or deploy it on an online platform ("Export to..." button). This action activates the transformation of the BPMN file into a file that can be imported by learning platform.

Fig. 3. Interfaces and features of proposed tool

MOOCAT Scenario Operationalization Service

In order to support the teacher, a service allowing the deployment of pedagogical scenarios carried out by MOOCAT has emerged. Operationalization represents an intermediate phase between learning and scenario design. It aims essentially to ensure that the scenario described by the teacher can be used and manipulated on a learning device while preserving the described pedagogical semantics [START_REF] Abedmouleh | Operationalization of learning scenarios on existent Learning Management Systems the moodle case-study[END_REF]. In the literature, there are two types of approaches to operationalize pedagogical scenarios: a manual approach and an automated approach. [START_REF] Abedmouleh | Operationalization of learning scenarios on existent Learning Management Systems the moodle case-study[END_REF] has classified these operationalization approaches into four categories: (1) Approaches based on the use of standards such as IMS-LD; (2) Approaches based on teachers' needs and practices [START_REF] Ferraris | Handbook of visual languages for instructional design: Theories and practices[END_REF][START_REF] Stylianakis | COLearn and open discovery space portal alignment: A case of enriching open learning infrastructures with collaborative learning capabilities[END_REF]; (3) Proprietary approaches proposed by platforms such as LAMS [START_REF] Dalziel | Visualising Learning Design in LAMS: A Historical View[END_REF]; (4) Hybrid approaches based on processes and tools inspired and/or applied by model-driven engineering [START_REF] Caron | Bricoles : une approche dispositive des applications Web 2.0 utilisables pour enseigner[END_REF]. Our contribution is based on the last one. Consequently, we have implemented an operationalization service that allows teachers to automatically deploy their pedagogical scenarios on a specific target platform. In line with our work, we have provided a solution that allows transforming the pedagogical workflow into a deployable scenario. In order to demonstrate the technical feasibility of our proposal, we have chosen to develop importation modules for OpenEDX and moodle platforms. We thus proposed the approach that goes through two phases: (1) Transformation -Pretreatment. The aim is to propose a confrontation between the two models, in order to resolve all ambiguities and to match each concept in the MOOCAT scenario with a concept in the chosen platforms. It is a surjective transformation, i.e. each MOOCAT element has at least one correspondence on the platform. The general idea of the transformation algorithm is to: (i) Generate the BPMN pedagogical workflow. (ii) Create the tree structure of files from the information specified in the BPMN file. (iii) Transform the scenario into the format required by OpenEDX or Moodle. ( 2) Deployment. The operationalization module acts as a communication gateway from our tool to a learning platform. In this phase, the service automatically connects to the platform and retrieves the list of available courses. The teacher can choose a course from existing ones or create a new course. Finally, the deployment process is automatically executed, using the platform import function.

An extension of the transformation and deployment module to other platforms remains possible, as long as the target-learning platform provides import/export functionality. Therefore, for a given platform, it is first necessary to go through the confrontation phase; the purpose is to find a correspondence between the elements of a MOOCAT scenario and the scenario model of the target platform. An illustration of the overall process can be found at the following link1 .

Evaluation

Objective and description. In this research, the contributions were evaluated and tested as they were specified through simulations and user tests, in order to confront them with the real needs of the target users. The final evaluation was established as part of an experimentation with 40 participants to evaluate the benefits of the extended notation and tool. Our objective is to evaluate the usability of MOOCAT as a cMOOCoriented pedagogical authoring tool and the expressivity of the proposed notation. In other words, we wanted to verify the ability of the proposed extension to express a cMOOC oriented pedagogical scenario. In order to reach the most diversified participants, a call for participation was broadcast to the TEL community through different mailing lists. We have also experimented our tool during a pedagogical scenario-building workshop with Master degree students that have previously designed pedagogical situations and manipulated different instructional design tools. Experimental Protocol. The evaluation protocol we have adopted consists of three steps, namely: (1) Preparation. We provided participants with a MOOCAT user guide that explains the MOOCAT philosophy and describes the functionalities of the tool and an experimentation guide that describes the different steps to be performed during this evaluation as well as the scenario to be deployed. ( 2) Conception. This step aims to design a pedagogical scenario for a cMOOC course according to the instructions provided during the preparation phase. (3) Results. For this step, we provided participants with a questionnaire that they could complete at the end of the evaluation in order to validate the utility and usability of some aspects of MOOCAT and to obtain more information on the participants' experience. Data collection. The methodology used to collect the data from this experimentation is based on two data sources, namely: (1) data derived directly from the work on MOOCAT, including produced scenarios; and (2) participant opinion data collected through questionnaires. The scenarios produced by the participants were analyzed using a rubric evaluation grid to assess, on a scale from one to three (1: low -3: high). We examined all the scenarios and assigned a score for each criterion, then calculated the average scores, which were then compared to the median of two. At the end of the experimentation, participants were asked to complete an online questionnaire contained 25 closed-ended questions, evaluated using a 6-point Likert scale (from Strongly Disagree to Strongly Agree). The first part of the questionnaire focused mainly on the expressivity of the notation. The second part concerns the measurement of the usability of the tool, for this part we used the SUS questionnaire System Usability Scale [START_REF] Bangor | Determining what individual SUS scores mean: Adding an adjective rating scale[END_REF]. Experimental results. All the scenarios created by the participants were collected and analyzed according to an evaluation grid that we defined. Table 1 presents the measured criteria and the average score for each criterion for all submitted scenarios. The criteria we have defined can be divided into two groups, qualifiable indicators that we have evaluated by observation (C2, C4 and C5), and quantifiable indicators that can be automatically calculated from the collected traces (C1 and C3). Criteria C2 and C4 shows that participants were able to create structured and organized pedagogical scenarios. This shows that teachers can easily create pedagogical workflows, proving the advantages of using BPMN as a pedagogical scenario language. The averages obtained for criteria C1 and C2 show that the majority of participants were able to create a wellstructured cMOOC scenario that contained all the essential connectivist elements. The analysis of the first part of the questionnaire aimed to determine whether the tool allowed for the simple design of a connectivist course. This section also assessed whether participants were satisfied with the tool and whether the tool's notation was easy to understand. Finally, it aimed to evaluate the potential of MOOCAT for designing a cMOOC course. In the first part of the questionnaire, 31 participants stated that the organization of the toolbox allowed them to identify the elements. In addition, 33 of the participants stated that the four connectivist activity blocks helped them to identify the activities and their usefulness. A total of 37 participants indicated that MOOCAT offered all the concepts required designing a cMOOC course, whereas only 3 of them did not agree with this statement. In addition, 34 indicated that the visual representation of a scenario was expressive and facilitated the course design. In the second part, the SUS questionnaire was used to measure the usability of MOOCAT.

SUS is a popular and effective tool for assessing the usability of various systems [START_REF] Bangor | Determining what individual SUS scores mean: Adding an adjective rating scale[END_REF]. It uses closed-ended questions with a Likert scale, which provides a 5-point gradation for each question ranging from"(1) totally disagree" to"(5) totally agree". Before calculating the SUS score, we pre-processed the participants' responses to remove any errors.

In order to detect these errors, we used the grid presented by [START_REF] Mclellan | The Effect of Experience on System Usability Scale Ratings[END_REF], which consists in considering all responses where the participant provided a score greater than 3 for all negative statements as incorrect. Of the 40 responses received, 6 were withdrawn. Overall, the average SUS score of all participants was 69.25 with a SD of 14.96. This score corresponds to the 55th percentile according to the standardization of [START_REF] Sauro | When designing usability questionnaires, does it hurt to be positive?[END_REF].

Fig. 4. SUS Score

In accordance with the empirical rule of interpretation of SUS scores [START_REF] Bangor | Determining what individual SUS scores mean: Adding an adjective rating scale[END_REF], systems with scores under 50 are considered unacceptable, products with a score between 50 and 70 are marginally acceptable and those with a score above 70 are acceptable. By positioning the score obtained on the acceptability scale and the rating proposed by [START_REF] Bangor | Determining what individual SUS scores mean: Adding an adjective rating scale[END_REF], the average SUS score of 69.25 indicates that MOOCAT is generally perceived as being close to the boundary between "marginally acceptable" and "acceptable" and between "OK" and "Good" for the notation.

Conclusion

The main objective of this research work is to support teachers in designing connectivist activities. We identify two steps leading from the design to the operationalization of a cMOOC-oriented scenario. The first consists of modeling the pedagogical scenario using a visual authoring tool; this editor is based on the BPMN graphical notation, and is aimed at teachers without specific technical knowledge or knowledge of the embedded model. We chose to adapt an existing open source BPMN modeling tool (BPMN. io) to embed our cMOOC scenario model. The second step consists of the automatic deployment of a scenario designed using MOOCAT on a MOOC platform. For this deployment phase, a web service solution was developed for the OpenEDX platforms. Our tool ensures that the mappings between the elements of its own scenario and those of the LMS (OpenEDX) are correct and comprehensible from both a semantic and a functionality point of view. These proposals were evaluated from utility and usability point of view. The findings confirm that MOOCAT can be used to design connectivist pedagogical scenarios and can provide all the necessary elements for the design of such courses. In our approach, the cMOOC is initially designed by the teacher, and learners are then encouraged to adapt the scenario according to their learning objectives. As a perspective of our work, we therefore consider that a methodology based on the codesign of a scenario that is currently in use would be a possible solution to this challenge, by giving access to the learners to MOOCAT with special and restricted roles and privileges. However, several scientific issues arise regarding the articulation of adaptation needs, the capitalization of these proposals, and the negotiation and validation of any changes carried out, especially in a massive environment.

  proposed a Method for the Development of BPMN Extensions that consists of the steps listed below: (1) Definition of a Conceptual Domain Model of the Extension (CDME) describing the concepts of the domain to be represented in extended BPMN models and their relationships with the concepts of the BPMN meta-model. (2) Definition of a BPMN plus Extensions model (BPMN+X) describing an extension based on the specification of the BPMN extension mechanism. (3) Transformation of the BPMN+X model into an XML Schema Extension Definition Model. (4) Transformation of the XML Schema Extension Model into an XML Schema Extension Definition Document.

Fig. 1 .

 1 Fig. 1. Process for the development of domain specific BPMN extension BPMN Metamodeling Extension. Based on the model transformation rules proposed by[START_REF] Stroppi | Extending BPMN 2.0: method and tool support[END_REF] we define an extension model (BPMN+X) by applying a set of transformation rules. The semantics and the abstract syntax of the extension model are based on BPMN extension mechanism. Depending on several rules in this phase[START_REF] Stroppi | Extending BPMN 2.0: method and tool support[END_REF], we had defined for each element, according to the domain specification, if we will use an existing BPMN element, define a new one or extend the attributes of the original BPMN elements; and how this changes will occur on BPMN meta-model. With the respect of the limited space of the paper, the entire transformation rules cannot be presented. Proposed Graphical Notation. We proposed an advanced concrete syntax that defines the specific new graphical representation. As defined by the[START_REF] Omg | Business Process Model and Notation[END_REF], the following extension can be made by: adding new markers or indicators, coloring graphical elements or changing the line style of a graphical element. According to these rules, Task elements are specified by colored borders and new markers that vary depending on the activity type. A pedagogical resource is represented as Data Object with a marker that reflects the selected Resource Type of the element. Subprocess line shape was also changed in order to differentiate it from generic Activity Element. The concrete graphical notation of the extension is presented in section 5.2.

Table 1 .

 1 Average scores per evaluation criterion for all submitted pedagogical scenarios

	n °	Criterion	score/3
	C1 Number of designed weeks		2,7
	C2 Expressiveness of the scenario representation	2,7
	C3 Use of all connectivist scenario concepts		2,5
	C4 Relevance of the proposed learning resources and activities related to the course topic.	2,5
	C5 Visual representation and organization of the scenario	2,7

https://youtu.be/JwRSyFxATUc


V M Gonçalves

C A Maia

L Hardouin

On Max-plus Linear Dynamical System Theory: the Observation Problem

Keywords: Max-Plus algebra, Tropical algebra, Observer, Control

In this paper, we are interested in the general problem of estimating a linear function of the states for a given Max-Plus linear dynamical system. More precisely, using only the current and past inputs and outputs of the system, we want to construct a sequence that converges in a finite number of steps to the value given by a linear function of the states for all initial conditions of the system. We provide necessary and sufficient conditions to solve this general problem. We also define and study a Max-Plus version of the well-known Luenberger observer, which is a subclass of the general problem that we are interested in, and we also provide necessary and sufficient conditions to solve this particular problem of observer synthesis. Finally, we show that there are important connections between results in the Max-Plus domain and associated results in the standard linear systems theory.

Introduction

Max-Plus algebra is an algebraic formalism for modeling a special class of discrete event dynamical systems, namely the Timed Event Graphs (see [START_REF] Baccelli | Synchronization and Linearity[END_REF] for the connection between Max-Plus and Discrete Event Systems). Recently, a considerable amount of work has been dedicated in obtaining results for dynamical systems which are linear in this algebra, especially regarding state control (see [START_REF] Gonçalves | On the steady-state control of timed event graphs with firing date constraints[END_REF] and the references therein).

In the context of controlling max-plus systems, it is often assumed that all the states are measured (see [START_REF] Gonçalves | On maxplus linear dynamical system theory: The regulation problem[END_REF] for example and [START_REF] Jacob | Output feedback control of discrete processes under time constraint: application to cluster tools[END_REF] for an exception). Frequently, to compensate the lack of measurement, an alternative is to use an observer in order to estimate the state variable by using both measured outputs and inputs.

In the max-plus setting, not much research was done in the subject. Indeed, to the best of authors' knowledge, few published papers studied problems related to observability in max-plus setting. To cite some exam-ples, in [START_REF] Spacek | Max-plus algebra for discrete event systems-some links to structural controllability and structural observability[END_REF], we have conditions for structural observability of Max-Plus systems, which are necessary, but not sufficient, conditions to be able to reconstruct exactly the real state of the system . In [START_REF] Gazarik | Reachability and observability of linear systems over max-plus[END_REF], we have conditions for computing what the authors call the Latest Event-Time State, which is the greatest state that is compatible with the system observations. The authors in [START_REF] Di Loreto | Duality between invariant spaces for max-plus linear discrete event systems[END_REF] propose an observer for a descriptor system, which can model uncertainties in the parameters, that has no inputs. Hence, given that the initial condition of the system x[0] is known, it is possible to find at a given step k all possible values of the state x[k] that could be reached by the system under uncertainties. Although interesting, and indeed the concepts presented there were fundamental for the developments in this paper, the proposed observation problem of that paper does not fit the main objective of this work. In this paper we are interested in reconstructing a linear combination of the states for a system, possibly with inputs, using only the information of the current and past inputs and outputs, assuming that the initial state is unknown.

Alternatively, the works in [START_REF] Hardouin | Observer design for (max,plus) linear systems[END_REF][START_REF] Abdesselam | Observer design and feedback controller synthesis with observer in idempotent semiring[END_REF][START_REF] Hardouin | Observer-based controllers for max-plus linear systems[END_REF], for example, have used transfer series methods to devise Luenbergerinspired observers that reconstruct the greatest estimated state x[k] that is less than or equal to the real state x[k], whose bounds for the error between the real and reconstructed state can be seen in [START_REF] Hardouin | Max-plus linear observer: Application to manufacturing systems[END_REF]. The work of [START_REF] Ferreira | Particle filters for max plus systems[END_REF] also considers an observation problem for Max-Plus systems. It considers probabilistic uncertainty in the model, proposing a particle-filter approach for solving the problem. However, it differs from the problem analyzed in this paper because it assumes information (probability density) of the initial state of the system.

Unlike those previously related works found in literature, with the exception of the authors' preliminary work [START_REF] Gonçalves | An observer for tropical linear event-invariant dynamical systems[END_REF], in this paper we are interested in the following problem, to be stated formally in Section 3: using only the current and past values of the system outputs y[k] and inputs u[k], construct a sequence that converges in a finite number of steps to a linear function s[k] = W x[k], for a given matrix W , for all initial conditions x[0] and all possible inputs u[k] of the system. This approach of computing only a linear combination of the states -instead of the complete information -using the outputs was already explored in the control literature for traditional linear systems since the 60's and was pioneered by Luenberger [START_REF] Luenberger | Observers for multivariable systems[END_REF]. The observers are then denominated functional observers (see [START_REF] Trinh | Functional Observers for Dynamical Systems[END_REF] and the references therein).

Estimating W x[k] directly, instead of first estimating x[k] and then computing W x[k], as it is considered in this paper, can be very beneficial since it is a weaker problem and usually requires weaker conditions. For example, if W is chosen as a linear state feedback gain matrix F , then this approach can be used to compute u[k] = F x[k], and thus the control problem would be solved using only output feedback, instead of state feedback. The results in this paper can also be used, for instance, to perform system diagnosis (see [START_REF] Di Loreto | Duality between invariant spaces for max-plus linear discrete event systems[END_REF][START_REF] Hardouin | Observer design for (max,plus) linear systems[END_REF]). Necessary and sufficient conditions for solving this observation problem will be provided, extending the results in the previous paper [START_REF] Gonçalves | An observer for tropical linear event-invariant dynamical systems[END_REF], which presents only sufficient conditions and no comparisons with similar results in the traditional linear systems theory. Furthermore, our derivations in this paper are heavily based on Max-Plus analogues of geometrical control ideas ( [START_REF] Wonham | Linear Multivariable Control: A Geometric Approach[END_REF], see also [START_REF] Di Loreto | Duality between invariant spaces for max-plus linear discrete event systems[END_REF] for the specific Max-Plus case).

We consider two variations of the observation problem: i) a weaker form, in which we are not interested in the specific way the reconstruction of W x[k] is done, and ii) a stronger form, not presented in [START_REF] Gonçalves | An observer for tropical linear event-invariant dynamical systems[END_REF], in which the desired signal should be obtained using a Luenberger-like observer. In addition, we will show how the Max-Plus results can be compared to their counterparts in the traditional linear dynamical systems theory. For that, we will present also some results in the traditional algebra. Although these results are not contributions of this paper, they will be presented for the sake of comparison. We establish that our results are, up to some point, analogous, but the Max-Plus case becomes more complex since the subtraction operation does not exist.

Basic Definitions

We will now make some basic definitions contextualized in the Max-Plus algebra, but sometimes we will also use the same notation for its traditional counterpart in the algebra of real numbers, and we expect that the specific interpretation should be clear from the context. For example, AB can denote the Max-Plus matrix product or the traditional product of real matrices, depending on the context. Further, the matrix I can denote the Max-Plus or the traditional identity matrix, also depending on the context. More technically Max-Plus algebra is the dioid (an idempotent semiring)

Z max = (Z ∪ {-∞}, ⊕, ⊗) (1)
in which ⊕ is the maximum and ⊗ is the traditional sum. It has been also called Tropical Algebra. The symbol ⊗ will be frequently omitted, so ab reads as a ⊗ b = a + b.

We denote the element -∞ by the symbol ε, and it will also be occasionally called "the null element". For two matrices A and B of appropriate dimensions, A ⊕ B and A ⊗ B will be interpreted as the matrix sum and product, respectively, with + being replaced by ⊕ and × by ⊗. Elements in this algebra that have n rows and m columns will be considered to belong to Z n×m max , while an element with m rows and 1 column will belong to Z m max . Thus, all vectors are column vectors. The symbol A T denotes the transpose of the matrix A. A vector or matrix of appropriate dimensions whose elements are all equal to ε will also be denoted by ε. A matrix without any ε entries is said to be full. The symbol I will denote the Max-Plus identity matrix of an appropriate order, that is, a matrix in which each diagonal element is 0 and ε off-diagonal. For a natural number k, the matrix power A k will be defined recursively as

A k+1 = A k A, with A 0 = I. If λ is a scalar not equal to ε, then λ -1
in the Max-Plus algebra results in -λ in the traditional algebra.

If J is a set of natural numbers and x is a vector, {x} J is a sub-vector of x formed only with the entries whose indexes are in J . The Kleene closure of a square matrix A is equal to

∞ i=0 A i .
The spectral radius of this matrix, ρ(A), is the greatest scalar λ for which there exists a vector v = ε in which Av = λv. Generally, even though the entries of the matrix A lie in Z or are equal to ε, the spectral radius can be a rational number. However, since the units of the problem can be redefined, the entries of the matrix (and thus the spectral radius) can be rescaled so the spectral radius is either an integer or is equal to ε. Thus, hereafter we can assume, without loss of generality, that ρ(A) ∈ Z max . In the traditional setting, ρ(A) is the eigenvalue of A with the largest absolute value. For two scalars a and b, we define a∧b = min(a, b). We also denote the point-wise minimum of two matrices A and B as A ∧ B.

Residuation theory [START_REF] Baccelli | Synchronization and Linearity[END_REF] deals with the conditions for the existence of the greatest element x for the inequality f (x) y, which means that every element of f (x) ∈ Z n×m max is less than or equal to every corresponding element of y ∈ Z n×m max . The symbol • / denote the (right) residuation operator and is defined as follows: given the inequality LP Q with matrices P ∈ Z n×m max , Q ∈ Z s×m max , there exists the greatest solution L max = Q• /P , whose entries can be computed by: (Q A semimodule, over a given dioid, is similar to a vector space over a semiring, that is, a set of elements x together with a scaling operation, i.e. (λ, x) → λx; and a summation operation; i.e. (x, y) → x ⊕ y; which preserve some properties in the context of this given dioid (See [START_REF] Katz | Max-plus (A; B)-invariant spaces and control of timed discrete-event systems[END_REF] for a formal definition). In addition, we denote Im M as the image of M . The image of M is the semimodule generated by the Max-Plus column span of the matrix

• /P ) ij = m l=1 (Q il -P jl ),
M , that is, if M ∈ Z n×m max then Im M = {M v | v ∈ Z m max }.
A congruence, over a given dioid, is an equivalence relation on Z n max with a semimodule structure formed with pairs (x, x ) of vectors which preserve some properties in the context of this given dioid. See [START_REF] Di Loreto | Duality between invariant spaces for max-plus linear discrete event systems[END_REF] for the formal definition. Then, Ker M , the kernel of M , is the congruence induced by the equality M v = M v in the Max-Plus context, which has a correspondence in the traditional algebra with the statement that (v -v ) is in the "null space" of the matrix

M ; i.e. if M ∈ Z n×m max then Ker M = {(v, v ) ∈ Z m max × Z m max | M v = M v }.
If Z is a congruence and A a square matrix we define the set AZ = {(Az , Az ) , (z , z ) ∈ Z}, which is, by the way, not a congruence, in general. It is worth to recall that in the traditional setting,

Ker M = {v ∈ R m | M v = 0}.

Two observation problems

Consider the max-plus linear event-invariant dynamical system S(A, B, C, D):

x[k + 1] = Ax[k] ⊕ Bu[k]; y[k] = Cx[k] ⊕ Du[k] (2) in which x[k] ∈ Z n max , u[k] ∈ Z m max , y[k] ∈ Z r max , A ∈ Z n×n max , B ∈ Z n×m max , C ∈ Z r×n max and D ∈ Z r×m max .
It is maxplus linear because its equations can be written in a linear way using the max-plus operators ⊕ and ⊗. It is event-invariant because the matrices A, B, C, D do not depend on the event k.

In the sequel we define the observation problems that we are interested in:

• The Max-Plus observer problem, henceforth denoted by TO(S, W ) (or simply TO when the parameters are clear) can be defined as follows: given a max-plus linear event-invariant dynamical system S as in Equation (2) and a matrix W ∈ Z s×n max , assuming, at step k = l, the knowledge of the inputs u[k], 0 ≤ k ≤ l -1 and of the outputs y[k], 0 ≤ k ≤ l -1 construct a sequence s[k] such that there exists a finite k in which s[k] = W x[k] for all k ≥ k and for all initial conditions x[0].

• The Max-Plus Luenberger observer problem, henceforth denoted by TO L (S, W ) (or simply TO L , when the parameters are clear) has a similar statement to TO(S, W ), but with a very specific form of obtaining W x[k]: there must exist matrices P, Q, R, S, T and an integer k such that the dynamical system

z[k] = P z[k -1] ⊕ Qy[k -1] ⊕ Ru[k -1] (3)
for any initial condition z[0] has the equalities z

[k] = Sx[k] and T z[k] = T Sx[k] = W x[k] for all k ≥ k .
This means that the observer variable z[k] must converge to a linear function of

x[k] (z[k] = Sx[k]
) and this function must allow the observation of

W x[k] (T z[k] = W x[k]).
We also define, by straightforward analogy, traditional counterparts to all the aforementioned problems. We will denote by RO and RO L the traditional (in the field of Reals) analogous of TO and TO L (in Max-Plus, or Tropical Algebra), respectively. In this case, we have state-space equations as in Equation 2, but with ⊕ swapped to the traditional + operations and all the matrix multiplications interpreted in the traditional sense. The entries of x, y and u are now in R instead of Z max .

A non-analogous difference in the definition is that, in RO and RO L , we now allow k to be ∞, i.e, we allow asymptotic convergence. Note that, since the entries of the vectors and matrices in the Max-Plus are either integers or ε, there is no sense in considering k = ∞ because there does not exist asymptotic convergence in this case (a sequence of integers either converges in a finite number of steps or does not converges at all). In the field of reals, asymptotic convergence makes sense.

In the sequel we will see that, if the observation problem is solvable, s[k] can be reconstructed as a (Max-plus) non-recursive linear combination of past outputs and inputs. In the traditional setting, the analogous result also holds, and the Luenberger observer is preferred over the non-recursive linear combination of outputs and inputs because the latter can amplify measurement noises, whereas the former can act as a low-pass filter and thus attenuate the sensor noise. We will see that in the Max-Plus case a similar analysis can be done: the linear combination of past outputs may demand a very delayed information (example, information at k -4 at the step k), and if there is a perturbation of the output at a given k this error may influence the reconstruction of s[k] in the next events k. The Luenberger observer, on the other hand, only demands current information.

The traditional counterparts of the observation problems have been studied before (see [START_REF] Trinh | Functional Observers for Dynamical Systems[END_REF] and the references therein) and necessary and sufficient conditions have been derived to solve them. We will compare in this paper how these results compare with the ones obtained in this paper for the Max-Plus case. We start the presentation of the results with the following lemma. Lemma 1. There is a solution to TO (resp RO) if there is a solution to TO L (resp RO L ).

This lemma simply states that the Luenberger observation problems are at least as harder to solve as the non-Luenberger ones.

We make the following assumptions: Assumption 1. for TO and TO L : We assume, without loss of generality, that no column of B and no row of C is ε. Furthermore, we assume, with a negligible loss of generality, that A is full. Indeed, we can set a reasonably high number h and enforce that

|x i [k] -x j [k]| h for all k. This implies that x[k] = Hx[k]
for a matrix H whose all entries are -h except the diagonal ones. Thus, we can swap A by AH, and if A has no column full of ε we can see that AH has no ε entries. We can always assume that no column is null, since we can always assume that

x i [k + 1] ≥ x i [k] (since x i [k]
represents the time in which the i th state event happened for the k th time) and thus the diagonal entries of A can be chosen to be at least 0. This assumption implies also that A has only one eigenvalue, equal to ρ(A), and that this value is not ε.

We also assume that x[0] is not the ε vector, which is reasonable because in practical situations, it represents firing times. This way, for all k > 0, x[k] Ax[k -1] is a full vector and all its entries grow with a rate of at least ρ(A). Finally, we assume, without loss of generality, that no row of the matrix W is ε. Otherwise, we want to estimate a signal s i [k] that is either ε or completely determined by u[k], rendering the observation problem for this variable trivial.

In summary, the highlights of this paper are as follow:

• The necessary and sufficient conditions for TO (Proposition 1) are obtained. They reduce to the solvability of at least one of the collections of infinite one-sided Max-Plus affine equations (Equation 10). Checking whether or not one of the Max-Plus affine equations has a solution can be done in strong polynomial time (Fact 3).

• If the problem TO is solvable, it is solvable using a (Max-plus) linear moving filter of the past u[k] and y[k] (Proposition 1, Equation 11). The same holds, analogously, for RO .

• The necessary and sufficient conditions for RO depend solely on the system matrix A and output matrix C. This is a classical result: for traditional linear systems, observability is independent of the input. In contrast, the necessary and sufficient conditions for solving TO do depend also on the control matrices B and D. This happens because there is no subtraction in the Max-Plus case, since we are working with semirings.

• Necessary and sufficient conditions for TO L (Proposition 2) are obtained. They reduce to the solvability of at least one of the collections of non-linear Max-Plus equations with a spectral radius constraint (Equation 13). We show how we can derive from this condition a solely sufficient but easy-to-verify condition.

• If RO has solution, so does RO L . Thus, in the light of Lemma 1, RO and RO L are equivalent (see Fact 5). In the Max-Plus case, TO may have a solution whereas TO L does not (Proposition 3).

4 Solving TO

Preliminary definition and results

First of all, before discussing the proposed problems, we will present some definition and basic results. Definition 1. (t th Max-Plus observability matrix) the t th Max-Plus observability matrix (or simply observability matrix, when the context is clear), Ôt (A, C) is defined

recursively as Ôt+1 (A, C) = C T ( Ôt (A, C)A) T T be- ing Ô-1 (A, C) the empty matrix.
The observability matrices itselves are not as important as their kernels, Ker Ôt (A, C). This t th kernel has all the pairs of states x [k], x [k] of the system in Equation 2, with u[k] = ε, which are indistinguishable after observing t outputs: y[k] to y[k + t -1]. An analogous observation holds for the traditional counterparts of the t th observation matrix.

In the traditional setting, the observability matrix of a linear dynamical system of n states is the traditional counterpart of Ôn-1 (A, C). Thanks to the Cayley-Hamilton theorem -which states that A n is a linear combination of smaller powers of A -we can conclude that Ker Ôn-1 (A, C) = Ker Ôk (A, C) for all k ≥ n -1. Since when discussing observability we are mainly interested in the kernel of the observability matrix, and not in the matrix itself, this implies that there is no sense, in the traditional setting, in considering observability matrices for k ≥ n -1.

In the Max-Plus setting the analysis is a bit more complex. Indeed, for general matrices A, there is a weaker form of Cayley-Hamilton theorem, (see [START_REF] Olsder | Cramer and Cayley-Hamilton in the max algebra[END_REF]), but it is not as useful because we cannot, in general, infer from it that A n is a Max-Plus linear combination of past powers of i. Moreover, there are matrices A for which A t can never be written as a Max-Plus linear combination of past powers of A (take, for instance, any diagonal matrix with different diagonal entries). This implies that we can have a sequence of decreasing Kernels Ker Ôt+1 (A, C) Ker Ôt (A, C) that does not stabilizes for a finite t.

Fortunately, for a very wide and useful class of matrices there is a Cayley-Hamilton-like result. Theorem 1. (See [START_REF] Baccelli | Synchronization and Linearity[END_REF]) Let A be a full square matrix. Then, there exist two natural numbers τ (A), denoting the coupling time 1 and σ(A), denoting the cyclicity, for which A τ +kσ = ρ(A) kσ A τ for all k.

The previous theorem implies that, if A is full,

Ker Ôτ+σ-1 (A, C) = Ker Ôk (A, C) for any k ≥ τ +σ-1.
The major problem lies in that the constant τ (A) can be very large even for matrices of small dimensions, since it depends on the entries of the matrix A.

Example : Consider the matrix

A = 0 -p 0 -1 (4)
for a natural number p ≥ 0. It is easy to verify that

A k = 0 -p 0 -k if 0 < k ≤ p; 0 -p 0 -p if k > p.
Thus ρ(A) = 0, τ (A) = p and σ(A) = 1. Consequently, even for 2 × 2 matrices, the coupling time can be very large (take, for instance, p = 100).

The observability matrix is related to another important concept of geometrical control: of (A, C)-conditioned invariant spaces. As was done in [START_REF] Di Loreto | Duality between invariant spaces for max-plus linear discrete event systems[END_REF], we generalize this concept to Max-Plus in a straightforward way. Definition 2. ( Max-Plus (A, C)-conditioned invariant congruence, see [START_REF] Di Loreto | Duality between invariant spaces for max-plus linear discrete event systems[END_REF]).

A congruence H is said to be Max-Plus (A, C)-conditioned invariant ( (A, C)-MPCI, henceforth) if A(H ∩ Ker C) ⊆ H, the operations being interpreted in Max-Plus sense. A congruence H = Ker H is (A, C)-MPCI if, consid- ering system 2 with input u[k] = ε, for any two states x [k], x [k] inside the congruence (i.e Hx [k] = Hx [k]), if they produce the same outputs (i.e Cx [k] = Cx [k]) then the pair x [k + 1], x [k + 1] is also inside the con- gruence, (i.e HAx [k] = HAx [k]).
The following results are important.

1 Since τ is a number of events, not a duration of time, perhaps a better name is coupling event Theorem 2. (see [START_REF] Di Loreto | Duality between invariant spaces for max-plus linear discrete event systems[END_REF]) If H = Ker H is (A, C)-MPCI then there exist matrices M, N such that M H ⊕ N C = HA. Theorem 3. (in analogy with the results in [START_REF] Wonham | Linear Multivariable Control: A Geometric Approach[END_REF])

Ker Ô∞ (A, C) is an (A, C)-MPCI invariant congru- ence. Indeed, it is the largest (A, C)-MPCI invariant congruence inside Ker C.
The previous results have straightforward traditional analogues (see [START_REF] Wonham | Linear Multivariable Control: A Geometric Approach[END_REF]), i.e, if the null space H is (A, C) conditioned invariant then there exist matrices M and N such that M H + N C = HA and Ker Ô∞ (A, C) is the largest (A, C) -conditioned invariant null space contained inside Ker C. As discussed before, owing to the Cayley-Hamilton theorem, Ker Ô∞ (A, C) can be replaced, in the traditional case, by Ker Ôn-1 (A, C). In the Max-Plus case, thanks to Theorem 1, we can state that, for full matrices, Ker Ô∞ (A, C) = Ker Ôτ+σ-1 (A, C).

In the traditional linear setting, we do not need to consider the input or the input matrices B and D in the observation problem. This, as it will be clear soon, is due to the fact that in the traditional setting, which is based on field of reals, we can subtract. Since this is not true in the Max-Plus setting, we need to introduce definitions concerning inputs. Definition 3. (t th Max-Plus controllability matrix) the t th Max-Plus controllability matrix, Kt (A, B) (or simply controllability matrix when the context is clear) is defined recursively as Kt+1 (A, B) = (A Kt (A, B) B), being K-1 (A, B) the empty matrix.

Note that a similar discussion to the one that was done for observability matrix, but with images instead of kernels, can be made for controllability matrices.

0 ≤ k 1 ≤ k 2 , we define z[k 1 : k 2 ] recursively as the vector (z[k 1 ] T z[k 1 + 1 : k 2 ] T ) T , being z[k 1 : k 1 -1] the empty matrix.
And then, we can easily deduce the following. Fact 1. Considering the dynamical system in Equation 2, it is easy to see that

x[k+t] = A t x[k]⊕ Kt-1 (A, B)u[k : k + t -1].
A similar result as Fact 1 holds for outputs. For that, we need another definition. Definition 5. (k th mixed matrix) the k th mixed matrix, Mk (A, B, C, D) is defined recursively as

Mt+1 (A, B, C, D) = D ε Ôt B Mt (A, B, C, D) (5)
being M -1 (A, B, C, D) the empty matrix.

And then: Fact 2. It is easy to see that, considering the dynamical system in Equation 2, that y[k :

k + t] = Ôt (A, C)x[k] ⊕ Mt (A, B, C, D)u[k : k + t].

Necessary and sufficient conditions for TO

We will present necessary and sufficient conditions for solving TO. We will also discuss on how these derivations compare to the classical ones for RO.

We can derive the following result.

Furthermore, k can be taken to be equal to t + 1, i.e, convergence happens in at most t + 1 steps.

Proof. The proof is an extension of classical geometrical control arguments (see [START_REF] Wonham | Linear Multivariable Control: A Geometric Approach[END_REF]).

Necessity:

Suppose k = t +
: t] = y [0 : t] as Ôt x [0] ⊕ Mt u[0 : t] = Ôt x [0] ⊕ Mt u[0 : t]. (7)
We can rewrite this equation in a more convenient form: create two variables u [0 : t] and u [0 : t] and rewrite Equation 7as

Ôt x [0] ⊕ Mt u [0 : t] = Ôt x [0] ⊕ Mt u [0 : t]; u [0 : t] = u [0 : t]. (8)
Thus, if y [0 : t] = y [0 : t] with the same control inputs, which is equivalent to Equation 8, we need to have the same

W x[t + 1], thus W x [t + 1] = W x [t + 1]
and, in the light of Fact 1

W (A t+1 x [0]⊕ Kt u [0 : t]) = W (A t+1 x [0]⊕ Kt u [0 : t]). (9)
Consequently, Equation 8 implies Equation 9. This statement is equivalent to Equation 6.

Sufficiency:

The condition Ker G ⊆ Ker H is equivalent to the existence of a matrix L such that LG = H (See [START_REF] Di Loreto | Duality between invariant spaces for max-plus linear discrete event systems[END_REF].). Thus, Equation 6 implies that there exists matrices L y and L u such that

L y Ôt = W A t+1 , L y Mt ⊕ L u = W Kt . (10)
Let k ≥ t + 1. Post-multiplying the first equation in Equation 10 by x[k -(t + 1)], the second equation by u[k -(t + 1) : k -1], summing up both equations and using Facts 1 and 2, we conclude that The result derived in Proposition 1 can be compared to our previous result in [START_REF] Gonçalves | An observer for tropical linear event-invariant dynamical systems[END_REF]. In that paper, it was proposed sufficient conditions -also a set of Max-Plus onesided affine equations with increasing complexity-for solving the observation problem TO. It turns out that these equations are a special case of Equation 10. Furthermore, in that paper only sufficient conditions were presented, whereas in the present one we also established the necessity.

W x[k] = L y y[k -(t + 1) : k -1] ⊕ L u u[k -(t + 1) : k -1]. ( 11
The following lemma is clear, since Equation 6 is a necessary and sufficient condition for finding a solution in t + 1 steps and, if we can find a solution in t + 1 steps, we can also find in t + 1 steps for t ≥ t. Lemma 2. If the condition in 6 (or equivalently Equation 10) holds for a t, it holds for any t ≥ t.

Connection with Classical Results

We will now discuss the connection between the result obtained in Proposition 1 and the result for the traditional counterpart of RO. Indeed, exactly the same reasoning can be made for the traditional counterpart problem, and, additionally, in traditional algebra simplifications can be made. The traditional counterpart of Equation 10, which is equivalent to the traditional counterpart of Equation 6, can be simplified since the second equation, L y Mt-1 + L u = W Kt-1 , is trivially satisfied as we can always choose L u = W Kt-1 -L y My . Note that we can only do this because we can subtract, something which is impossible in the Max-Plus case.

With this simplification, the traditional counterpart of Equation 6 reduces to the condition Ker Ôt-1 ⊆ W A t . This implies that the observability problem in the traditional case is independent of the input matrices B and D, a result which is well known in the control literature. Such simplification is not always possible in Max-Plus algebra, since subtraction does not exists, and then the second equation in 10 may render the problem unsolvable if L y Mt-1 W Kt-1 is not true. This implies that, in the Max-Plus setting, the control matrices influence the observation problem.

It is easy to check whether Equation 10 has, for a given t, a solution or not and, in the case of a positive answer, obtain it. This is thanks to the following fact. Fact 3. (see [START_REF] Baccelli | Synchronization and Linearity[END_REF]) There exists a solution L for a Max-Plus one-sided affine equation of the form LV = U if and only if (U • /V )V = U , and furthermore L = U • /V is the greatest solution. Additionally, if V ∈ Z a×b max and U ∈ Z c×b max , this equality can be checked in O(abc) time.

Thus, for a given t, the solvability of Equation 10 can be checked in polynomial time. The only problem is that, in principle, we need to check for all t's and then, in general, the obtained condition can never be used to decide that the problem is unsolvable (it works only as a sufficient condition). A natural question then arises: Is there a maximum finite t for which we need to check?. Or, equivalently: Is there a t such that if there is no solution for t = t we can guarantee that there is no solution for all t ≥ t ?

We will answer this question first for the traditional problem RO. In this setting an analogous result in Proposition 1 holds. As mentioned before, in this case the condition in Equation 6 reduces to Ker Ôt-1 ⊆ Ker W A t . Considering Lemma 2 (which is also true in the traditional setting), the weaker condition happens when t goes to ∞. In this case, thanks to the Cayley-Hamilton theorem, Ker Ôt-1 reduces to Ker Ôn-1 , in which n is the size of the square matrix A. Hence the Kernel cannot change from t ≥ n -1 in comparison to Ker Ôn-1 , which only has powers of A below n.

We will also simplify the term Ker W A t . In order to do that, we need the following lemma. Lemma 3. Let J be a matrix with only non-stable eigenvalues (|λ| ≥ 1). Then lim k→∞ W J k x = 0 ⇒ W x = 0.

Proof. Suppose J ∈ R n×n . Since J is invertible, apply Cayley-Hamilton theorem in J -k to conclude that

J -nk = n-1 i=0 α i [k]J -ik for constants α i [k]
. Since all the eigenvalues of J -k for k > 0 are inside or on the border of the unit circle, these coefficients α i [k] all converge to a finite value as k → 0. This is true because they are the coefficients of the characteristic polynomial of J -k , and hence, thanks to the Vieta's formulas, they are sum of products of the eigenvalues of J -k , i.e, the eigenvalues of J to the (-k) th power, which all are finite as k → ∞. Thus, multiplying the equation for J -nk by J nk we see that

I = n-1 i=0 α i [k]J (n-i)k
Now, since lim k→∞ W J k(n-i) x = 0 for all n > i ≥ 0 and lim k→∞ α i [k] is finite, we have that lim k→∞ W (α i [k]J (n-i)k )x = 0. Summing up these statements and applying the derived equation for I, we conclude that W x = 0, as we wished to prove.

We also need the important definition. Definition 6. (Stable annihilator matrix) Consider the matrix A ∈ R n×n with Jordan canonical form

A = Q J s 0 0 J u Q -1
in which J s is the Jordan block related to stable eigenvalues (|λ| < 1) and J u the remaining ones (|λ| ≥ 1). The stable annihilator matrix is the matrix Π(A) obtained from A by replacing J s by the zero matrix and J u by the identity matrix I.

And then, we can use the Jordan decomposition of A to obtain the following corollary of Lemma 3.

Corollary 1. (of Lemma 3) It holds that lim t→∞ W A t x = 0 ⇒ W Π(A)x = 0 or, equivalently, as t → ∞ , Ker W A t ⊆ Ker W Π(A).
With Corollary 1, we see that as t → ∞, the condition Ker Ôt-1 ⊆ Ker W A t implies that Ker Ôn-1 ⊆ Ker W Π(A). Consequently, the latter therefore is a necessary condition for solving RO. It is also sufficient, because it implies that there exists L y such that L y Ôn-1 = W Π(A). Post-multiplying by A t and using the fact that L y Ôn-1 A t = Ly Ôn-1 for a matrix Ly (thanks to the Cayley-Hamilton theorem), taking the limit to t → ∞ in both sides and noting that lim t→∞ (A t -A t Π(A)) = 0, we see that it also implies that, as t → ∞, the condition Ker Ôt-1 ⊆ Ker W A t holds.

Thus, we arrive at a very nice condition for solving RO.

Ker Ôn-1 (A, C) ⊆ Ker W Π(A) ( 12
)
which is a weaker form of traditional detectability (indeed, if W = I we recover the traditional meaning of detectability).

For the Max-Plus case, TO, the situation is not so easy.

There is no straightforward simplification, as it was done for RO, for the condition 6 as t → ∞. Indeed, for t → ∞, we have an infinite system of equations which is therefore impossible to be checked. For a finite t, even for small systems, it may be the case that the observation problem TO has a solution but a very large t must be considered.

Example : Consider the problem TO(S, W ) with matrices A as in Equation 4, B = ε, C = (0 0), D = ε and W = (0 ε). In the case that B and D are null matrices, Equation 6 reduces to Ker Ôt-1 ⊆ Ker W A t . The Kernel of Ôt-1 can be seen to be, using the expression for A k in Equation 5, spanned by the row vectors (0 -k) for 0 ≤ k ≤ t -1 if t -1 ≤ p, and spanned by the row vectors (0 -k) for 0 ≤ k ≤ p if t -1 > p. Thus, for t -1 > p the kernel of Ôt-1 does not change.

Now, we can calculate that W A t = (0 -p) for all t. It is easy to see, then, that it is impossible for Ker Ôt-1 to be contained in Ker W A t for t -1 < p, and for t -1 ≥ p it is possible, and thus the observation problem has solution. This example shows that, even for an inputless small system, the observation problem may be solved only after a high number of steps t (in the example take, for instance, p = 100).

It remains an open question how to obtain the greatest t that we need to consider condition in 6. That is, a t such that if there is no solution for this t we can declare that there is no solution for any t ≥ t either.

5 Solving TO L

Necessary and sufficient condition for TO L

We will now study the Luenberger problem TO L (S, W ). Proposition 2. Let Kt-1 = Kt-1 (A, B) and J ⊆ {1, 2, ..., s} be the set of all j such that for all k the j th row of P k is not ε. Then, the problem TO L (S, W ) has a solution if and only if there exist a finite t and matrices P, Q, R, S and T solving the following system of conditions

(i) : SA t+1 = P SA t ⊕ QCA t ; (ii) : W A t = T SA t ; (iii) : SA Kt-1 = P S Kt-1 ⊕ QC Kt-1 ; (iv) : W Kt-1 = T S Kt-1 ; (v) : SB = QD ⊕ R; (vi) : ρ(P ) < ρ(A);
(vii) : For all j ∈ J , there must exists i(j) such that the j th row in

P i Q is not null. ( 13
Sx[k] = P (Sx[k -1]) ⊕ Qy[k -1] ⊕ Ru[k -1] (14)
which is of the form in Equation 3 with z

[k] = Sx[k] for k ≥ t + 1.
[k] = T z[k] = W x[k]
for k ≥ t + 1. This implies that, for k ≥ t + 1 and with the initial condition z

[0] = Sx[0], Equation 3 is such that T z[k] converges to W x[k].
We will now establish that the initial condition z[0] can be any vector other than the vector that guarantees convergence, z[0] = Sx[0]. This implies convergence for all z[0]. Indeed, we will see that Equation 13-(vi,vii) guarantee that the system state z

[k] is, eventually, indepen- dent of z[0].
To establish that, note that Equation 13-(vii) guarantees that there exists a map i : J → N such that the j th row in P i(j) Q is not null. Now, let k ≥ max j∈J i(j) and write, expanding Equation 3

z[k] = P k z[0] ⊕ j∈J P i(j) Qy[k -i(j)] ⊕ f (15)
in which f is the remaining term in the expansion that is independent of z[0]. Now, since y[k] grows with a rate at least equal to ρ(A) (see Assumption 1) , each of the entries of each one of the signals y[k -i(j)] grow with this rate. Furthermore, for each row j ∈ J the j th row of P i(j) Q is not null, and therefore we conclude that the signal g[k] = j∈J P i(j) Qy[k -i(j)] is such that all its entries in J grow with a rate of at least ρ(A). To conclude, due to the Equation 13-(vi), there exists a finite k ≥ max j∈J i(j) such that eventually {g

[k]} J {P k z[0]} J for all k ≥ k and z[0]. Consequently, for k ≥ k {z[k]} J = {P k z[0] ⊕ g[k] ⊕ f } J = {g[k] ⊕ f } J (16)
which is independent of z[0]. Then for the entries in J the signal z[k] is, in steady state, independent of z[0]. For the entries not in J , that is, in J , this is also true since {P k z[0]} J = ε for at least a k = k. Since P k+s = (P k)P s , we have that

{P k z[0]} J = ε for any k ≥ k.
Consequently, it is also true that the steady-state signal will be independent from z[0] in the entries j ∈ J. Thus, as k grows the initial condition z[0] is immaterial for the state z[k].

Necessity: Condition (i,iii,v): Suppose there is a t such that the dynamical system in Equation 3 is such that z

[k] = Sx[k] and T z[k] = T Sx[k] = W x[k] for all k ≥ t. Hence, for k ≥ t, z[k] = SA k x[0] ⊕ S Kk-1 u[0 : k -1].
In special, we can take k = t and k = t + 1 and plug into Equation 3 to conclude that

SA t+1 x[0] ⊕ S Kt u[0:t] = P S t x[0] ⊕ P S Kt-1 u[0:t-1] ⊕QCA t x[0] ⊕ QC Kt-1 u[0:t-1] ⊕ QDu[t] ⊕ Ru[t].( 17
)
Equation 17 must hold for all x[0] and vector u[0 : t].

Take u[0 : t] = ε and x[0] the columns of the identity matrix of same dimension of x[0] to conclude the necessity of Equation 13-(i). Take

x[0] = ε, u[t] = ε and u[0 : t-1]
the columns of the identity matrix of the same dimension of u[0 : t -1] to conclude the necessity of Equation 13-(iii). Finally, take

x[0] = ε, u[0 : t -1] = ε and u[t]
the columns of the identity matrix of the same dimension of u[t] to conclude the necessity of Equation 13-(v).

Condition (ii,iv): For Equation 13-(ii,iv), it suffices to consider that the equation

T Sx[k] = W x[k] must hold for k ≥ t. Take k = t. Then, substitute x[t] = A t x[0] ⊕ Kt-1 u[0 : t -1].
Noticing that it must hold for all x[0] and u[0 : t -1] and using the same strategy of considering the columns of the identity matrix as before we can conclude the necessity of 13-(ii,iv).

It remains to establish the necessity of Equation 13-(vi,vii). For that, consider a trajectory x[k] generated with an initial condition x[0] and u

[k] = ε for all k, so y[k] = CA k x[0]
. Then, we can write, expanding Equation 3

z[k] = P k z[0] ⊕ k i=0 P i QCA k-i x[0]. (18)
Condition (vii): Suppose then Equation 13-(vii) does not hold. Then, there exists a ĵ ∈ J such that the ĵth entry of

k i=0 P i QCA k-i x[0]
is ε for all k. These statements, together with Equation 18, imply that for any k the ĵth entry of z[k] is equal to the ĵth entry of P k z[0], which is not ε (by the definition of J ) as long as we choose z[0] without ε entries. This implies that this entry does not depend on x[0] and can be made arbitrarily large by choosing z[0] arbitrarily large. Thus, the required convergence z[k] = Sx[k] in that entry can never be achieved for all z[0]. This implies the necessity of .

Condition (vi):

The necessity of Equation 13-(vi) comes with a similar argument by studying Equation 18. Suppose Equation 13-(vi) it does not hold, then there exists a entry of P k which grows with a rate of at least ρ(A). Suppose this entry lies in the j th row. Thus, we can choose z[0] sufficiently large so

{P k z[0]} j ≥ { k i=0 P i QCA k-i x[0]} j ,

Equivalence between observation problems

We will now establish an interesting result. From Lemma 1, we know that TO L is at least as hard to solve as TO.

We will now establish that TO L is strictly harder to solve. Proposition 3. There exists a system S and a matrix W for which the problem TO(S, W ) has a solution but TO L (S, W ) does not.

Proof. We will prove this result presenting an example. Consider the problem in which S is given by

x[k + 1] = 0 0 0 0 x[k] ⊕ u[k]; y[k] = (0 ε)x[k]
and W is equal to (0 0). The problem TO(S, W ) has a solution because Equation 6 holds for t = 1. We will now show that TO L (S, W ) is not solvable.

Consider the necessary and sufficient conditions in Equation 13, presented in Proposition 2. We will prove that the conditions in Equation 13can not hold simultaneously, and thus TO L (S, W ) does not have a solution. Indeed, Equation 13-(iii) has, for all t > 0, the subequation SAB = P SB ⊕ QCB. Since B = I, this reduces to SA = P S ⊕ QC. For t = 0, this same equation appears in Equation 13-(i). So, for any t, the equation SA = P S ⊕ QC must have a solution.

Let pT be a left-eigenvector of P associated with the greatest eigenvalue γ, that is, γ = ρ(P ). Pre-multiply SA = P S ⊕ QC by pT and let p T = pT S and q = pT Q. Then, if SA = P S ⊕ QC has a solution, so does p T A = γp T ⊕qC for p, q, γ. In our case, this equation reduces to, considering p T = (p 1 p 2 ), the scalar equations (a) : p 1 ⊕ p 2 = γp 1 ⊕ q and (b) : p 1 ⊕ p 2 = γp 2 . Now, considering Equation 13-(vi), we have that the greatest eigenvalue γ is smaller than ρ(A). Thus, the scalar equations (a) and (b) must have a solution for p 1 , p 2 , q, γ, with γ < ρ(A) = 0. It is easy to see that the equation is only solvable with p 1 = p 2 = q = ε. In particular, this implies then that p T = ε.

To conclude, note that we can assume, without loss of generality, that no row of S is null. Indeed, in Equation 13, it can be seen that if it has a solution with a S with a null row, it also have a solution for the S obtained removing the same row. Thus, since pT is an eigenvector, and thus not null, and S has no null row, p T = pT S cannot be the ε vector, which is a contradiction. And the proof is complete.

Proposition 3 is quite relevant because of the following fact: Fact 5. The problems RO(S, W ) and RO L (S, W ) are equivalent.

That is, in the traditional case, both the observer and Luenberger observer problems are equivalent, whereas in the Max-Plus case this is not true (Proposition 3).

To establish the result in Fact 5, owing to Lemma 1, we simply need to establish that if RO has a solution, so does RO L .

An analogous of Proposition 2, with an analogous proof, can be derived for RO L . In this case, the necessary and sufficient conditions are analogous to the ones in Equation [START_REF] Katz | Max-plus (A; B)-invariant spaces and control of timed discrete-event systems[END_REF], but with (a) the operators interpreted in the traditional algebra, (b) with ρ(A) replaced by 1 in (vi) and (c) without (vii).

It will be established now that S = ( ÔT n-1 (I -Π(A)) T ) T solves the traditional analogue of Equation 13-(i,iii,vi) for t = 0, that is, with this S there exist matrices P, Q solving all these three conditions. For that, we will need to use the traditional analogue of Theorems 2 and 3, that is, there exist matrices P , Q such that Ôn-1 A = P Ôn-1 + QC. It turns out that an even stronger result holds. Lemma 4. In the equation Ôn-1 A = P Ôn-1 + QC, the matrix P can be chosen so ρ(P ) < 1.

Proof. Let A ∈ R n×n . For the solution of Ôn-1 A = P Ôn-1 + QC, it is clear that we can choose an arbitrary

Q = (Q T 0 Q T 1 ... Q T n-1 ) T and P =          -Q 0 I 0 ... 0 -Q 1 0 I ... 0 -Q 2 0 0 ... 0 ... ... ... ... ... -Q n-1 +α 0 I α 1 I α 2 I ... α n-1 I          (19)
in which A n = n-1 i=0 α i A i due to Cayley-Hamilton Theorem. It is a well known fact that, in this configuration, we can choose Q so ρ(P ) < 1. This is true because, considering the matrices

à =          0 1 0 ... 0 0 0 1 ... 0 0 0 0 ... 0 ... ... ... ... ... α 0 α 1 α 2 ... α n-1          (20)
and C = (1 0 0 ... 0), the pair ( Ã, C) is clearly observable. Thus, there exists Q = (q 1 q 2 ... q n ) T so ρ( Ã -Q C) < 1 (see [START_REF] Wonham | Linear Multivariable Control: A Geometric Approach[END_REF]). Let ⊗ denote the Kronecker product of matrices and choose Q = Q ⊗ I. As P = ( Ã -Q C) ⊗ I, we can see that ρ(P ) < 1, because the eigenvalues of the Kronecker product U ⊗ V are all possible combinations of products of eigenvalues of U and V (see [START_REF] Horn | Topics in Matrix Analysis[END_REF]). Lemma 4 establishes that Ôn-1 A = P Ôn-1 +QC can be solved with ρ(P ) < 1. We will now derive, from Lemma 4, a related result. Lemma 5. Let S = ( ÔT n-1 (I -Π(A)) T ) T . So, in the equation SA = P S + QC, the matrix P can be chosen so ρ(P ) < 1.

Proof. Considering the matrices P and Q in Lemma 4, choose

P = P 0 0 A(I -Π(A)) , Q = Q 0 . (21)
We can see by straightforward verification that SA = P S + QC and that ρ(P ) < 1, since both ρ(P ) < 1 and ρ(A(I -Π(A))) < 1 hold.

Lemma 5 establishes that, with S = ( ÔT n-1 (I -Π(A)) T ) T , we can solve SA = P S + QC with ρ(P ) < 1.

We will now construct a solution to the traditional analogue of Equation 13. Equation 13-(v) is trivial to solve in the traditional algebra since we can subtract and R does not appear in other equations: R = SB -QD. Now, we can solve Equation 13-(i,iii,iv,vi) with t = 0 (so Equations 13-(iii,iv) are trivialized), S = ( ÔT n-1 (I -Π(A)) T ) T and the P, Q induced in Lemma 5. It remains to show that, if we consider these parameters t, S, P, Q, there is a corresponding T that solves Equation 13-(ii).

The additional condition that guarantees this is the solvability of RO. Indeed, suppose RO has a solution. From Fact 4, Ker Ôn-1 ⊆ Ker W Π(A). Thus, there exists a matrix L such that L Ôn-1 = W Π(A). Choose T = (L W ). Note that T S = L Ôn-1 + W (I -Π(A)) = W Π(A) + W (I -Π(A)) = W . With this choice of T and S, we have that 13-(ii) can also be solved for t = 0, establishing Fact 5.

Someone could argue why we can not use the same strategy to solve Equation 13 (for TO L ) that we used in Equation 13 (for RO L )? Is it possible to take S = Ôp , for a p, in the Max-Plus case and derive an analogous of Lemma 4? That is, can we solve Ôp A = P Ôp ⊕ QC with ρ(P ) < ρ(A)? Unfortunately, we cannot proceed because we do not have subtractions in the Max-Plus case, which is fundamental in the construction in Equation 19.

Simplification strategy

For a fixed t, Equation 13 is a nonlinear Max-Plus equation with spectral radius constraints, which is, in general, hard to solve. However, if we fix the matrix S (for instance, inspired in the last developments for the traditional case, take S = Ôp for a p such that Ker Ô∞ = Ker Ôp ), it can actually be solved (or shown to have no solution) very easily. For that, we need the following lemma, which is a slight extension of the well known result in Fact 3. Lemma 6. There is a solution L for a Max-Plus onesided affine equation of the form LV = U with the constraint L L max if and only if

(U • /V ∧ L max )V = U . Furthermore L = (V • /U ∧ L max ) is the greatest solution.
Proof. It follows immediately as a corollary of Fact 3 by noting that LV = U and L L max can be rewritten as the one-sided Max-Plus affine system of equations LV = U , L ⊕ F = L max for the unknown variables L, F . Applying Fact 3 in this new equation, the result becomes clear.

We then replace the condition of ρ(P ) < ρ(A) with the constraint P P max , in which P max is a matrix for which all the entries are h < ρ(A) for a fixed h. Note that P P max implies that ρ(P ) < ρ(A), but the converse is not true (that is, there may exist matrices P such that ρ(P ) < ρ(A) but P P max ), so this condition is stronger. Nevertheless, Equation 13with S and t fixed and this modified condition Equation 13-(vi) is a Max-Plus one-sided affine equation with bound constraints (Q,R and T have no bound constraints, and thus we can say that Q Q max , R R max T T max , in which Q max , R max , T max are matrices with very large entries). Thus, we can write Equation 13 as LV = U , L ≤ L max , in which L = (P Q T R). We can then try to solve it using the result in Lemma 6. Note that, due to the fact that we find the greatest solution of the constrained affine equation in the strategy described in Lemma 6, Equation 13-(vii) will be satisfied, if possible, because the matrix will be as less sparse as possible. We will now compare the two solutions. For that, we will use an input signal u[k] generated by the expression u[k] = k i=0 û[i] in which û[i] are random integer variables distributed uniformly on [0, 8], so the mean is ρ(A) = 4 and u[k] grows, on average, with the same rate as ρ(A). We used a random initial condition for x[0] and z[0] = (0 0 0 0) T . We then computed the error in the two approaches between the desired signal s[k] = W x[k] and the constructed sequences s lc [k] (linear combination from Equation 13) and s lue [k] (Luenberger observer) for k ranging from 0 to 40. If we measure the signal perfectly, eventually both approaches converge to the real signal s[k]. To test the influence of errors in the measurement, at k = 0, 10, 20, 30 we generated a random error in the output y[k] (used by boath approaches) by adding to it an integer random number between 0 and 10. The results, the difference between the real s[k] and the sequences s lc [k] and s lue [k], can be seen in Figure 1. We note that the Luenberger approach is better at rejecting the perturbation. This happens because the approach based in Equation ( 11) uses delayed information, up to y[k -4], so when there is an error in the measurement at the event k, it can influence negatively the sequence s lc [k] in the next four events.

Conclusion

In this paper, we were interested in Max-Plus observation problems, which were formulated in a general way as a problem of estimating a desired linear function of the state of the system. We have provided necessary and sufficient conditions for solving the problems, as well as comparisons with the analogous problem that appears in classical linear system theory. We showed that, due to the nonexistence of subtraction in the Max-Plus case, the observation problems are more difficult to solve and that we need to carefully take into account the input behaviour to solve the problems. For future works, it would be interesting to investigate how to quickly compute a maximum t that we need to check for a solution in Equation 6 (and Equation 13), and also develop an efficient method for solving the system of conditions in Equation 13.

  with the definition -= ∞. The operator • / has precedence over ∧, thus A• /B ∧ C reads as (A• /B) ∧ C.

Proposition 1 .

 1 Let Ôt = Ôt (A, C), Kt = Kt (A, B) and Mt = Mt (A, B, C, D). The problem TO(S, W ) has a solution if and only if there exists a finite t such that Ker Ôt Mt ε I ⊆ Ker W (A t+1Kt ).

  ) And then we can, for k ≥ t + 1, retrieve the values of W x[k] using only the past outputs y[k -(t + 1) : k -1] and inputs u[k -(t + 1) : k -1].

Fact 4 .

 4 RO(S, W ) is solvable if and only if

)

  Proof. Sufficiency: Let k ≥ t + 1. Post-multiply Equation 13-(i) by x[k -(t + 1)], Equation 13-(iii) by u[k -(t + 1) : k -2] and Equation 13-(v) by u[k -1]. Sum all these statements and use Fact 1 to conclude that

  because the right side of this inequality grows with a rate of at most ρ(A).So {z[k]} j = {P k z[0]} j . This implies that it is impossible to have the equality {z[k]} j = {Sx[k]} j for any z[0]because z[0] can be sufficiently large and independent of x[0].

  k] = (ε ε ε 0)x[k] and W = (0 ε ε 0). The problem TO(S, W ) has a solution, because Equation 10 has a solution with t = 3 (and for t < 3 it is not solvable): L y = (16 12 8 4) and L u = (12 8 4 0). Thus, the sequence in Equation (11) can be used to recovers[k] = W x[k]. Note that we use the delayed informations y[k -1], y[k -2], y[k -3] and y[k -4] in this approach.In addition, TO L (S, W ) has a solution as well. Using S = I and considering a stronger condition on the spectral radius bound, P ij ≤ 0 < ρ(A) = 4, we can use the simplification strategy proposed in Subsection 5.3. For t = 0 we have a solution to the modified Equation13with these considerations, which generate the following Luenberger observer in which s[k] = T z[k] = (0 ε ε 0)z[k] eventually converges to W x[k].

Fig. 1 .

 1 Fig. 1. Error between the real s[k] = W x[k] and reconstructions for both approaches.

  Consider, again, k ≥ t + 1. Now, postmultiply Equation 13-(ii) by x[k -t] and Equation 13-(iv) by u[k -t : k -1]. Sum these statements, and use again Fact 1 to conclude that T Sx

thank the brazilian agencies CNPQ, CAPES and FAPEMIG for funding this research.