Jean-Michel Dalle
email: jean-michel.dalle@upmc.fr

Matthijs Den Besten
email: matthijs.den-besten@polytechnique.edu

Voting for bugs in Firefox: A voice for Mom and Dad?

In this paper, we present preliminary evidence suggesting that the voting mechanism implemented by the open-source Firefox community is a means to provide a supplementary voice to mainstream users. This evidence is drawn from a sample of bug-reports and from information on voters both found within the bug-tracking system (Bugzilla) for Firefox. Although voting is known to be a relatively common feature within the governance structure of many open-source communities, our paper suggests that it also plays a role as a bridge between the mainstream users in the periphery of the community and developers at the core: voters who do not participate in other activities within the community, the more peripheral, tend to vote for the more user-oriented Firefox module; moreover, bugs declared and first patched by members of the periphery and bug rather solved in "I" mode tend to receive more votes; meanwhile, more votes are associated with an increased involvement of core members of the community in the provision of patches, quite possibly as a consequence of the increased efforts and attention that the highly voted bugs attract from the core.

Introduction

Firefox is an open source project that explicitly tries to cater to the needs of a mainstream audience. Judging by its market share, as estimated for instance by the firm StatCounter (http://gs.statcounter.com), Firefox is succeeding. What might explain this success? To a large extent it is due to the leadership of people like Blake Ross, Dave Hyatt and Asa Dotzler and to their apparently correct judgement in deciding which features and bugs deserve the highest priority for development. In addition, however, we expect that the success is due to explicit mechanisms that have been put in place in order to make sure that the needs of mainstream users are assessed and addressed correctly. Voting for bugs in the Bugzilla bug tracking system is one such mechanism.

Voting for bugs is of course not unique to Firefox. It is a feature of the Bugzilla bug tracking system that has been activated by many of the projects who use it. Moreover, it is generally assumed that some sort of voting is a standard element of the open source software development model (see, e.g., [START_REF] Siobhán | The governance of open source initiatives: what does it mean to be community managed[END_REF]). Yet, apart from the governance of Apache [START_REF] Mockus | Two case studies of open source software development: Apache and mozilla[END_REF] and Debian [START_REF] Siobhán | The emergence of governance in an open source community[END_REF], there are to our knowledge surprisingly few explicit analyses or even descriptions of voting procedures in free/libre open source software communities.

In her analysis of the emergence of voting procedures in Debian, O'Mahony focuses on the greater efficiency and transparency that is provided by voting compared to consensus based collective decision making usually dominant in small groups and presents the introduction of voting as a reaction to the increases in scale and scope of the Debian enterprise. Voting can however be useful even in small groups: see for example the seminal paper on collective problem identification and planning by Delbecq and Van De Ven [START_REF] Delbecq | A group process model for problem identification and program planning[END_REF], who propose a model of an effective group process in which the first phase of problem exploration is concluded with a vote. This, they note, serves to make the results of the exploration explicit and create pressure for change on the people who will be responsible for resolving the problem. Here voting is not just about representation, it is also about "getting heard".

In this context it might be useful to ponder the framework that Hirschman [START_REF] Hirschman | Exit, voice, and loyalty[END_REF] developed on the means by which patrons can influence their organizations. Patrons have basically two options: either they leave the organization and buy or produce with a competitor ("exit"), or they express their concerns more explicitly through channels that might be provided by the organization ("voice"). In open source software development, the primary mechanism for "exit" is forking [START_REF] Mateos | Applying the open source development model to knowledge work[END_REF] and the primary mechanism for "voice" is to "show code" by proposing patches [START_REF] Cox | Cathedrals, bazaars and the town council[END_REF]. For mainstream users such as "mom and dad", however, neither forking nor patching is a realistic option, as they typically do not have the skills to do either. Since Firefox precisely wants to be a product for mom and dad [START_REF] Livingston | creator, Firefox[END_REF], other options have to be found: "exit" can be implemented by switching to other browsers like Internet Explorer, Safari, Opera, and Chrome. For "voice", voting might be an appropriate answer.

In what follows, we present circumstantial evidence to support our conclusion that voting for bugs in Firefox is a means to provide a voice to mainstream users. This evidence is drawn from a sample of bug-reports maintained by Mozilla's Bugzilla and from explicit information on voters found at the same site. We present results regarding voters and bugs in sections 4 and 5, respectively. We present some more background information on our research in section 2 and describe our sampling strategy in section 3.

Background

This paper is number four in a succession of papers that we have presented at OSS conferences. In the first paper, presented in Limerick in 2007 [START_REF] Dalle | Different bug fixing regimes? A preliminary case for superbugs[END_REF], we analyzed bug reports from Mozilla and found that there are some bugs that take exceedingly long to resolve and that part of the reason for the existence of these "superbugs", as we named them, could be related to the insufficient provision of contextual elements such as screenshots in the bug threads. The second paper, presented in Milan in 2008 [START_REF] Dalle | Channelling Firefox developers: Mom and dad aren't happy yet[END_REF], analyzed bug reports that are associated with the Firefox branch and exploited the existence of the so-called "CanConfirm" privilege -the privilege to declare bugs as "new" given that the initial status of bugs is "unconfirmed" by default -to distinguish between core and peripheral participants within bug resolution processes and inquired whether various variables could influence the speed at which new and unconfirmed bugs were patched. In the third and latest paper, presented in Skövde in 2009 [START_REF] Masmoudi | Peeling the onion: The words and actions that distinguish core from periphery in Firefox bug reports, and how they interact together[END_REF], we used text mining techniques to arrive at a further characterization of participants within the core and the periphery of the Firefox community, stressing notably the fact that members of the core tend to use to pronoun "We" disproportionately while members of the periphery, conversely, seem to prefer to use "I".

By focusing on voters this paper tries to exploring an additional layer of the onion model of the Firefox community. To echo the language we used in our 2008 paper, while the likes of Blake Ross and Dave Hyatt clearly belong to the inner core, the periphery is probably mostly populated by "alpha-geek" users -that is, exactly by those people who Ross and Hyatt professed to ignore in Firefox development [START_REF] Livingston | creator, Firefox[END_REF]. "Mom and dad" are not there. If at all, they are more likely to be among the outer periphery of people who are simply voting and contributing very little otherwise.

This line of inquiry obviously owes a lot to the pioneering work by Mockus et al. [START_REF] Mockus | Two case studies of open source software development: Apache and mozilla[END_REF] and also to subsequent work by Ripoche [START_REF] Gabriel Ripoche | Sur les traces de Bugzilla[END_REF], who established bug reports as an object of study. Together with others, e.g. [START_REF] Diederik | How shallow is a bug?[END_REF], we continue to exploit this extremely rich source of information. Conceptually we have been inspired by the analysis of MacCormack at al. [START_REF] Maccormack | Exploring the structure of complex software designs: An empirical study of open source and proprietary code[END_REF], who argue that it was necessary to make the existing code that was left by Netscape more modular before Mozilla could attract patches from the periphery. We wonder here whether votes could constitute another element which could help to explain how Firefox could turn the unwieldy open source project that Mozilla had become into the sleek browser for the mainstream market that we have now.

Sampling Method

For our analysis we constructed two types of data-sets. The first type relates to bugs, which may or may not have attracted votes, and concerns the history of the bug resolution process as it is recorded by Bugzilla as well information about the bugs that can be found in the logs of the cvs code repository. The second type concerns information that is stored in Bugzilla about the activities of the people who have voted for one or more bug. For each type we have obtained several sets and sub-sets of data based on three criteria: first of all, we are interested in bugs for which we can assume that they have had an impact on the Firefox code-base in the sense that they are mentioned in the commitcomments and the cvs repository; secondly, we are interested in bugs that have received votes; and finally, we are interested in bugs that Bugzilla associates with the Firefox project. Similarly, we are interested in people who voted for bugs which eventually found their way into the cvs; we are also interested in the other bugs they voted for; and we are interested in the people who voted with them on Firefox bugs. Figure 1 is a Venn diagram which illustrates this admittedly somewhat complex constellation of sets. Our main interest is in the intersection of bugs from cvs that have been voted on and are also officially associated with Firefox as well as in the people who have voted for this particular set of bugs. Other than that we also have some interest in the other subsets formed by the intersection of the three criteria in order to be able to compare and contrast with what we find in our main set. In practice we followed a procedure similar to snowball sampling in order to obtain our sets and subsets of bugs and voters. We started with the bugs that we found in the logs of our copy of the Mozilla's cvs archive concerning the code for Firefox up until version 2.0. Only a small subset of these bugs, some 10%, has ever attracted a vote. Associated with those bugs is a list of all people who have cast a vote (people can also retract there vote later; in that case they fall through our net). Our next step was to retrieve all those lists and compile a list of cvs voters constituted by union of all sets of voters contained in these lists -we found 11826 of them. The list of voters that is attached to the bugreports in Bugzilla also contains, for each voter, a link to a voter-page that lists all the bugs the voter in question has voted for split according to the project with which Bugzilla associates the bug. As far as we can tell, this "project" field is a new data element in the bug-reports that was not yet displayed in the original bug-reports that constitute the cvs-set of bugs. That is why we do not have such project-data for most of the bugs. Nevertheless via the voter-pages we can determine the project for those bugs for which at least one vote was cast. Contrary to what one might assume just a fraction of the bugs that we associate with code in the Firefox-branch of the Mozilla cvs are associated with Firefox by Bugzilla as well. Partly, this may be due to misattribution from our part, but mostly this seems to be a reflection of the fact that Firefox shares code with other applications and the fact that it is based on code that was developed earlier for other projects. In addition to the project affiliation of cvs bugs the voter-pages also give the project affiliation for bugs that did not make it into that set -that is, bugs that did get votes but where not mentions in the commit-comments we looked at. The union of all these bugs constitutes the voter-set of bugs. We did not retrieve the complete Firefox-set of bugs, but we do not which part of the voter-set overlaps with it and that another part of the cvs-set should do as well. Finally, our set of Firefox-voters is by looking at the voter-lists of all bugs in the voter-set that are associated with Firefox through Bugzilla and taking the union of the sets of voters listed in those lists. Table 1 gives a short summary of the manner in which we obtained our sets described above.

Table 1. Summary indication of source of the main sets of bugs and voters.

Bugs Voters

CVS

Bugs associated with Firefox code before version 2.0.

Union of lists of voters on bugs in set defined in previous column.

Votes

All bugs that received one or more votes by voters on the cvs bugs.

As above, ceteris paribus.

Firefox

All the bugs associated with Firefox in the listing of bugs per voter.

" "

Another and, for now, final detail about the data preparation concerns the way we link voter-identities with other activities by the same people in the bug resolution process. For this we rely on the fact that up until recently the voters as well as participants to the bug forum discussions, bug-reporters, bugassignees, etcetera, were identified by their email address. Hence we could assign various bug-activities to the voters by matching these email addresses. This method works fine for the bugs that we focus on for this study. However, studies concerned with the most recent bugs would not be able to apply this method as Bugzilla has moved to enhanced identity management and does no longer provide the full email address for voters.

Characterizing Voters

A first dimension along which voters can be distinguished from non-voters, reported in Table 2, is with respect to both groups' status in the community.

Table 2 is a contingency table comparing community status and voting activity of participants in the bug resolution process for the intersection of 418 bugs with the following properties: they appear in the cvs; they have attracted votes; and they are associated with Firefox. As participants, we consider people who have either contributed at least one comment to at least one discussion thread or who have cast at least one vote for these bugs. Among the 418 bugs of interest, this definition yields a total of 2968 participants, 1681 of whom have cast a vote and 1755 of whom have written at least one message, which implies that 1213 participants have voted but never written a message. A first conclusion that can be drawn from these numbers, then, is that most voters do not engage in other activities. If we go one step further and check participation on a bug-by-bug basis, this finding becomes even more pronounced: typically, voters who are active in the bugs in the set tend to engage in this activity on bugs for which they did not vote.

In order to gauge the status of participants we rely on the CanConfirm privilege mentioned earlier. In particular, we check for each participant whether he or she has ever declared bugs contained in the set of 37408 bugs that appeared in the cvs logs. For those participants who did declare bugs we look at the initial status of those bugs. If all the bugs that a participant declared start with status new the participant is considered to belong to the core; if all the bugs start with status unconfirmed the participant belongs to the periphery; if some bugs start with unconfirmed and others with new the participant is considered to be a freshly joined or a freshly expelled member of core; finally if the participant has not declared any bug, he or she is classified as member of the outer-periphery, here denoted as "Other".

Given all this, the main conclusion from table 2 is that the people who cast a vote are mostly, yet not exclusively, outsiders. Interestingly, this finding also holds for the status of the people who voted for any one of the bugs that appeared in the cvs logs. Of the 11850 voters among these 3787 bugs 10269 have never declared a bug while only 283 participants have had all the bugs they declared accepted as new right-away. Furthermore, when we consider the top 1000 most active voters, 688 among them can still be classified as outsiders while only 36 belong to the core.

Figure 2 gives some indications about the voting activities of the people who have cast a vote for at least one of the 418 bugs in the latter sample. It shows the distribution of the number of bugs to which people have cast their vote as split according to projects and status. Actual outsiders, with status Other, tend to declare "pure" Firefox bugs while contributors with another status disperse their votes much more. q q q q q q q q Core B N O U q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q Firefox B N O U q q

MailNews.Core q q q SeaMonkey q q q Toolkit 10^0.0 q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q qq q q q q q q q q qq q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q qq q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q qq qq q q q qq q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q qq q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q qq qq q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q qq qq q qq q q q qqq q qq qq q q qq qqq q q q q q q q q qq q q q q q q qqq qq q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qqq q q q q q q q q q q q q q q q qq qq q q q q q q q q q q q q q q qq q q q q q qq q q q q qq q q q q qq q q q q q q q qq q q q q q qq qq q qqq q q q q q q q q q q qq q qq qq q q q qqq q q q q qq q q q q q q q qq qq q qq qqq q q q qq q q q q q q q q q q q q q q q q q q q q q qq q q q qq q q q q q qq q q q q q qq q q q q q qq q q qq q q qq q q qq q q q q q q q qq q q q qq qq q q q q q q q qq q q qq q q q q q q q q q q q q qq qq q q qq q q q q q q q q q q q qq q q q q q q Core Firefox MailNews Core SeaMonkey Toolkit other q q q q q q id total 0 1000 2000 3000 4000 0e+00 1e+05 2e+05 3e+05 4e+05 5e+05 qqq q q q q q qqq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q Fig. 3. Cumulative sum of bugs per project against bug-id; in the plot on the left specifically for Firefox (see text).

Figure 3 tries to shed some light on the timing of bug activity. Votes do not come with timestamps in the Bugzilla records, but we know that bug-ids are assigned sequentially. Figure 3 shows how many bugs had received votes before a given bug id against the sequence number that is used to identify them and this gives a rough indication about the distribution of voting over time. On the left is shown this distribution for bugs with votes and that appear in the cvs logs: typically, a steady proportion of bugs attract votes; not all projects are active at the same time; and some, for instance SeaMonkey, are gradually abandoned while others take off. The right graph focuses on bugs associated with the Firefox project more in particular. This graph includes the bugs that were voted on by the people who voted for the 418 Firefox cvs bugs that are represented in purple in the middle of the graph. The picture that appears is one of a very loyal electorate. Note that we are looking at all the votes that were cast by people who voted during the specific time window which is occupied by the 418 Firefox cvs bugs. Normally, one would expect a certain level of turnover among these people, implying that number of people who continue to vote would decrease over time. Nevertheless the ratio between increase in the number of bugs with votes and the increase in the total number of bugs looks more or less stable. So either people continue to vote, or abandonment of the project by some people is compensated by increased voting activity of the people who remain. In addition, the slope might also have been influenced by a change in the proportion of bug-ids that are attributed to the Firefox project.

Analyzing Bugs

Figure 4 shows the share of each project among the bugs in the cvs-set that have at attracted at least one vote. With 418 out of 3785 bugs Firefox is far from the most heavily represented project in this set. The most heavily represented project is "Core", which can be explained by the fact that "Core" concerns the foundation of code that is common to most Mozilla projects. The SeaMonkey project "is a community effort to develop the SeaMonkey all-inone internet application suite" (http://www.seamonkey-project.org/). In a sense, it pursues a strategy that Firefox explicitly chose not to follow and it is a little ironic that there are so many SeaMonkey bugs mentioned in commits related to Firefox code. This may be a reflection of the fact that these siblings have a lot of code in common. "MailNews Core" is harder to explain as this project is concerned with code for email clients, which Firefox, in contrast to SeaMonkey, choose not to include. "Toolkit", finally, includes cross-platform components such as "Gecko" the rendering engine for web-pages -which is of course important to Firefox in particular.

In order to compare the bugs that attract votes with those that don't, Table 3 gives the estimations of a generalized linear model, assuming a Poisson distribution for the variable totalVotes, which is a numeric variable whose value represents the total number of votes that a bug has attracted. The estimates are based on data from a subset of about ten thousand cases, bugs for which we don't have complete information, very old bugs with a low bug-number and other outliers having been removed. Please refer to [START_REF] Dalle | Channelling Firefox developers: Mom and dad aren't happy yet[END_REF] for a detailed description of these variables in so far as they are not explained below.

The number of votes is statistically correlated with NumAttention, which relates to the number of people who have put themselves on the CC-list associated with the bug so that they can follow the progress on the bug resolution, i.e. with the attention received by a bug.

More generaly, more votes tend to be associated with "problems" in solving a bug and notably to neglect: patches, which counts the number of different patches needed to solve a bug; duplicatesBeforeLastResolved, which indicates repeated declarations of the same bug; Ltpsassign, the log of the time need for the bug to be assigned to someone; numberOfTimesAssigned, the number of times a bug has been assigned; or else bugWasReopened, a self-explanatory dummy variable, are all variables of this kind. Conversely, high values for com com and com authrate, which are indicative for a high level of activity and a lot of commitment on a bug, are correlated with a lower number of votes: votes would be less needed when there is enough commitment on a given bug.

Interestingly then, several variables generally relevant for the patching and triage of bugs are not or only weakly significant here: numberOfEditsByBugReporter and numberOfEditsByLastAssignee, two variables that reflect the level of activity of the people who are most directly involved with the resolution of a bug; severity, which reflects the current community estimate of the severity of a bug; priority, the assessment by the community of the importance of a bug; and dependson, the number of other bugs which have been found to depend on a given bug.

Finally, and closer to our interest in this article, I/We, which represents the ratio between the number of times that the personal pronouns I and We appear in the bug thread, is highly significant: bugs patched in "I-mode" tend to recieve more votes, either because people vote for their own bugs or because bug patching in I-mode is associated with the involvement of peripheral members of the community. The significance of OC, CO, and esspecially of OO -dummy variables indicating that the bug reporter and the first "patcher" for that bug stem from periphery and core (in case of OC), core and periphery (CO), or both from the periphery (OO), respectively -tends to support the view that the involvement of the periphery in patching a bug would be statistically associated with more votes, even while controlling by attention, commitment, neglect, and various other problems affecting bug patching. In this last respect, Figure 5 is the result of an attempt to delve deeper into the relationship between patching and voting in the context of the relationship between periphery and core. Most of the patches are proposed by people from the core of the Firefox community. In many cases the first patch that is proposed is accepted as the solution for a bug. There are however a few cases in which multiple patches are proposed before a final patch is accepted as the solution for a bug. Figure 5 focuses on bugs whose first patch was proposed by a member of the periphery. We compute how many of these bugs do not receive any subsequent patches by members from the core, relative to bugs that have received zero votes, one to five votes, six-to-ten votes, and so further, respectively. What Figure 5 shows is that there is a clear increase in the level of participation of core members of the community when the number of votes increases. A possible interpretation of this could be that votes are used by the periphery to attract the attention of the core.

Conclusion

When Blake Ross and Dave Hyatt initiated Firefox, they established themselves as benevolent dictators fulfilling the volonté générale, to borrow from Rousseau, while emphatically reserving the right to ignore the volonté de tous. However, and contrary to acounts of voting in open source communities which tend to present it as a method to arrive at a fair representation of the will of the community, they allowed voting as as a channel through which voices from outside the community could be heard. Consequently, we found that most votes originate in the outer periphery. Bugs that attract most votes tend to be bugs that are relatively neglected or bugs where the periphery is heavily involved. Hence one can surmise that the votes were cast in order to attract the attention from the core. It would be interesting to see whether there are additional mechanisms apart from the votes that help the core to focus its attention.

Fig. 1 .

 1 Fig. 1. Sampling of bugs: 37408 appear in the code base (cvs); among them 3787 have attracted at least one vote (Votes ∩ cvs) and 418 among these are associated with the Firefox project (Firefox ∩ Votes ∩ cvs).

Fig. 2 .

 2 Fig. 2. Distribution of number of bug declared by status per project. B = both; N = new; O = other; U = unconfirmed.

Fig. 4 .

 4 Fig. 4. Pie chart showing the share of Mozilla projects among the bugs that received bugs in our sample.

Fig. 5 .

 5 Fig.5. Proportion of bugs that received patches from the periphery only among all bugs whose first patch was proposed by a member of the periphery (y-axis) against number of votes as average over a 5-vote range (i.e. 1 = 0 votes, 2 = 1 -5 votes, 3 = 6 -10 votes etc.) on the x-axis.

Table 2 .

 2 Number of voters by status for participants in the resolution of bugs which have received at least one vote, are mentioned in the cvs, and are associated with the Firefox project (n = 2968; χ 2 = 366, df = 3, p-value = 5.243e -79 ).

		Status
		Unconfirmed New Both Other Total
	Vote	184	25 64	1408 1681
	No Vote 286	139 182 680 1287

Table 3 .

 3 Generalized linear model with Poisson distribution for dependent variable totalVotes based on 10763 observations.

	Parameter	Est. Std.Er [Wald 95% ]	χ 2 Pr > χ 2
	Intercept	0.3231 0.1697 -0.0096 0.6558	3.62	0.057
	numberOfEditsByBugReporter 0.0061 0.0029 0.0005 0.0118	4.57 0.0326
	numberOfEditsByLastAssignee -0.0025 0.0014 -0.0052 0.0003	3.13 0.0771
	NoSgRestriction	0.5972 0.1046 0.3922 0.8022	32.6 <.0001
	numberOfTimesAssigned	0.1064 0.006 0.0946 0.1182 311.23 <.0001
	bugWasReopened	0.3264 0.0264 0.3781 0.2747 153.14 <.0001
	nauth	0.1799 0.021 0.1387 0.2212 73.19 <.0001
	patches	0.1217 0.0032 0.1154 0.1281 1410.15 <.0001
	attach patch	0.1065 0.0049 0.097 0.116 481.08 <.0001
	com com	-0.5699 0.0152 -0.5997 -0.54 1400.64 <.0001
	comauthrate	-0.2283 0.0154 -0.2584 -0.1981 220.65 <.0001
	severity	0.0341 0.0131 0.0085 0.0597	6.82	0.009
	priority	0.0053 0.0097 -0.0138 0.0244	0.3 0.5848
	priorityNotIncreased	-0.133 0.0698 -0.2698 0.0039	3.63 0.0568
	priorityNotDecreased	0.1907 0.0461 0.1005 0.281 17.15 <.0001
	severityNotIncreased	-0.321 0.0295 -0.3788 -0.2632 118.44 <.0001
	severityNotDecreased	-0.4144 0.0403 -0.4934 -0.3354 105.71 <.0001
	nfile	-0.0068 0.0009 -0.0086 -0.0051 58.35 <.0001
	dependson	0.0216 0.0075 0.007 0.0363	8.39 0.0038
	blocked	0.0561 0.0037 0.0489 0.0633 232.89 <.0001
	NumAttention	1.0415 0.0164 1.0093 1.0737 4018.84 <.0001
	version2 1.7	1.325 0.1105 1.1084 1.5416 143.73 <.0001
	version2 Trunk	-0.4801 0.0285 -0.536 -0.4242 283.24 <.0001
	Ltpsassign	0.0822 0.0053 0.0718 0.0926 239.27 <.0001
	DuplicatesBeforeLastResolved 0.1741 0.0044 0.1654 0.1828 1531.72 <.0001
	UX	0.3312 0.0454 0.2421 0.4202 53.12 <.0001
	I/we	0.0537 0.0014 0.0509 0.0565 1383.95 <.0001
	os3 NonWin	0.1279 0.0299 0.0693 0.1864 18.31 <.0001
	OC	0.1415 0.0278 0.0871 0.196 25.94 <.0001
	CO	0.424 0.0361 0.3533 0.4947 138.19 <.0001
	OO	0.8045 0.0366 0.7327 0.8763 482.33 <.0001
	Scale	1	0	1	1


G Zheng
email: gang.zheng@inria.fr

F J Bejarano
email: javbejarano@yahoo.com.mx

W Perruquetti
email: wilfrid.perruquetti@inria.fr

J.-P Richard

Unknown Input Observer for Linear Time-Delay Systems ⋆

Keywords: Delay systems, commensurate delays, observer, unknown inputs

This paper investigates an unknown input observer design for a large class of linear systems with unknown inputs and commensurate delays. A Luenberger-like observer is proposed by involving only the past and actual values of the system output. The required conditions for the proposed observer are considerably relaxed in the sense that they coincide with the necessary and sufficient conditions for the unknown input observer design of linear systems without delays.

Introduction

Time delay systems are widely used to model many applications, ranging from chemical and biological process to sampled data effects [START_REF] Richard | Time-delay systems:an overview of some recent advances and open problems[END_REF]. Many results have been published to treat this kind of systems for different aspects, such as stability [START_REF] Fridman | Introduction to Time-Delay Systems: Analysis and Control[END_REF], observability [START_REF] Zheng | On observation of time-delay systems with unknown inputs[END_REF] and identifiability [START_REF] Zheng | Identification of the delay parameter for nonlinear time-delay systems with unknown inputs[END_REF].

The unknown input observer design for linear systems without delays has already been solved in [START_REF] Bhattacharyya | Observer design for linear systems with unknown inputs[END_REF]; [START_REF] Darouach | Full-order observers for linear systems with unknown inputs[END_REF]; [START_REF] Yang | Observers for linear systems with unknown inputs[END_REF]; [START_REF] Hou | Design of observers for linear systems with unknown inputs[END_REF]; [START_REF] Kudva | Observers for linear systems with unknown inputs[END_REF]; [START_REF] Wang | Observing the states of systems with unmeasurable disturbances[END_REF]; [START_REF] Hostetter | Observing systems with unmeasurable inputs[END_REF]. This problem becomes more complicated when the studied system involves delays, which might appear in the state, in the input and in the output. For this issue, different techniques have been proposed in the literature, such as infinite dimensional approach [START_REF] Salamon | Observers and duality between observation and state feedback for time delay systems[END_REF], polynomial approach based on the ring theory [START_REF] Sename | Unknown input robust observer for time delay system[END_REF]; [START_REF] Emre | Regulation of split linear systems over rings: Coecient-assignment and observers[END_REF], Lyapunov function based on LMI [START_REF] Darouach | Linear functional observers for systems with delays in state variables[END_REF]; [START_REF] Seuret | A sliding mode observer for linear systems with unknown time varying delay[END_REF] and so on.

More precisely, [START_REF] Fattouh | An unknown input observer design for linear time-delay systems[END_REF] proposed an unknown input observer with dynamic gain for linear systems with commensurate delays in state, input and output variables, while the output was not affected by the unknown inputs. Inspired by the technique of output injection [START_REF] Krener | Ad f ,g ), (ad f ,g ) and locally (ad f ,g ) invariant and controllability distributions[END_REF], [START_REF] Hou | An observer design for linear timedelay systems[END_REF] solved this problem by transforming the studied system into a higher dimensional observer canonical form with delayed output injection. In [START_REF] Darouach | Linear functional observers for systems with delays in state variables[END_REF][START_REF] Darouach | Full order unknown inputs observers design for delay systems[END_REF], the unknown input observer was designed for the systems involving only one delay in the state, and no delay appears in the input and output. The other observers for some classes of time-delay systems can be found in [START_REF] Conte | Unknown input observers for linear delay systems: a geometric approach[END_REF]; [START_REF] Sename | New trends in design of observers for time-delay systems[END_REF]; [START_REF] Fu | Design of unknown input observer for linear time-delay systems[END_REF] and the references therein.

Most of the existing works on unknown input observer are focused on time-delay systems whose outputs are not affected by unknown inputs. However, this situation might exist in many practical applications since most of the sensors involve computation and communication, thus introduce output delays. This motivates the work of this paper. Compared to the existing results in the literature, this paper deals with the unknown input observer design problem for a more general sort of linear timedelay systems where the commensurate delays are involved in the state, in the input as well as in the output. Moreover, the studied linear time-delay system admits more than one delay. As far as we known, there exist some methods to eliminate (or reduce the degree of) the delay, such as [START_REF] Lee | Canonical forms for time delay system[END_REF], [START_REF] Germani | An asymptotic state observer for a class of nonlinear delay systems[END_REF] and [START_REF] Garate-Garcia | Equivalence of linear time-delay systems[END_REF]. It has been proven in [START_REF] Garate-Garcia | Equivalence of linear time-delay systems[END_REF] that the elimination or the reduction of delay degree via a bicausal transformation with the same dimension is possible if some conditions on A(δ ) and B(δ ) are satisfied. Since this paper investigates the most general linear system with commensurate delays on the state, the input and the output, to impose those kinds of conditions will definitely restrict the contribution of this paper. Moreover, even for the general single delay system with unknown input, the problem to design an observer is still unsolved, thus the contribution of this paper does not depend on the degree of time delay involved in A(δ ), B(δ ),C(δ ) and D(δ ).

This paper adopts the polynomial method based on ring theory since it enables us to reuse some useful techniques developed for systems without delays. The following notations will be used in this paper. R is the field of real numbers. The set of nonnegative integers is denoted by N 0 . I r means the r × r identity matrix. R [δ ] is the polynomial ring over the field R. R n [δ ] is the R [δ ]-module whose elements are the vectors of dimension n and whose entries are polynomials. By R q×s [δ ] we denote the set of matrices of dimension q × s, whose entries are in R

[δ ]. For a matrix M (δ ), rank R[δ ] M (δ ) means the rank of the matrix M (δ ) over R [δ ]. M(δ ) ∼ N(δ ) means the similarity between two polynomial matrices M(δ ) and N(δ ) over R[δ ],
i.e. there exist two unimodular 1 matrices U 1 (δ ) and

U 2 (δ ) over R[δ ] such that M(δ ) = U 1 (δ )N(δ )U 2 (δ ).

Problem statement

In this paper, we consider the following class of linear systems with commensurate delays:

       ẋ (t) = k a ∑ i=0 A i x (t -ih) + k b ∑ i=0 B i u (t -ih) y (t) = k c ∑ i=0 C i x (t -ih) + k e ∑ i=0 D i u (t -ih) (1)
where the state vector x (t) ∈ R n x , the system output vector

y (t) ∈ R p , the unknown input vector u (t) ∈ R m , the initial con- dition ϕ (t) is a piecewise continuous function ϕ (t) : [-kh, 0] → R n (k = max {k a , k b , k c , k d }); thereby x (t) = ϕ (t) on [-kh, 0]. A i , B i , C i
and D i are the matrices of appropriate dimension with entries in R.

In order to simplify the analysis, let us introduce the delay operator δ :

x (t) → x (t -h) with δ k x(t) = x(t -kh), k ∈ N 0 . Let R [δ ]
be the polynomial ring of δ over the field R, and it is obvious that R[δ ] is a commutative ring.

After having introduced the delay operator δ , system (1) may be then represented in the following compact form:

ẋ (t) = A (δ ) x (t) + B (δ ) u (t) y (t) = C (δ ) x (t) + D (δ ) u(t) (2)
where

A (δ ) ∈ R n x ×n x [δ ], B (δ ) ∈ R n x ×m [δ ], C (δ ) ∈ R p×n x [δ ],
and D (δ ) ∈ R p×m [δ ] are matrices over the polynomial ring

R [δ ], defined as A (δ ) := k a ∑ i=0 A i δ i , B (δ ) := k b ∑ i=0 B i δ i , C (δ ) := k c ∑ i=0 C i δ i , and D (δ ) := k d ∑ i=0 D i δ i .
Remark 1. For the system without delay, i.e. A(δ [START_REF] Hautus | Strong detectability and observers[END_REF] proposed the following unknown input Luenberger-like observer:

) = A, B(δ ) = B, C(δ ) = C and D(δ ) = D in (2),
ξ = Pξ + Qy x = ξ + Ky
and it has been proven as well the above Luenberger-like observer exists only if the following rank condition:

rank CB D D 0 = rank B D + rankD (3)
is satisfied.

1 refer to Definition 2 for the concept of unimodular matrix over R [δ ].

When considering the general linear system (2) with commensurate delays which can appear in the state, in the input and in the output, the problem to design a simple unknown input Luenberger-like observer is still open. The main idea of this paper is inspired by the method proposed in [START_REF] Hou | An observer design for linear timedelay systems[END_REF] where only linear time-delay systems without input were studied. More precisely, we firstly try to decompose system (2) into a simpler form provided that some conditions are satisfied, and then transform it into a higher dimensional observer normal form with output (and the derivative of the output) injection and its delay. Finally we can design an unknown input observer for the obtained observer normal form.

Notations and definitions

When designing an unknown input observer for time-delay systems, it is desired to use only the actual and the past information (not the future information) of the measurements to estimate the states because of the causality. Therefore, by noting x (t; ϕ, u) as the solution of (2) with the initial condition ϕ and the input u, we have the following observability definition stated in [START_REF] Bejarano | Observability of linear systems with commensurate delays and unknown inputs[END_REF].

Definition 1. System (1) (or system (2)) is said to be backward unknown input observable on [t 1 ,t 2 ] if for each τ ∈ [t 1 ,t 2 ] there exist t ′ 1 < t ′ 2 ≤ τ such that, for all input u and every initial con- dition ϕ, y (t; ϕ, u) = 0 for all t ∈ [t ′ 1 ,t ′ 2 ] implies x (τ; ϕ, u) = 0.
Concerning the above definition of backward unknown input observability, [START_REF] Bejarano | Observability of linear systems with commensurate delays and unknown inputs[END_REF] analyzed it by following the ideas of [START_REF] Silverman | Inversion of multivariable linear systems[END_REF] and [START_REF] Molinari | A strong controllability and observability in linear multivariable control[END_REF]. Define {∆ k (δ )} as the matrices generated by the following algorithm:

∆ 0 0, G 0 (δ ) C (δ ) , F 0 (δ ) D (δ ) S k (δ ) ∆ k (δ ) B (δ ) F k (δ ) , k ≥ 0 F k+1 (δ ) G k+1 (δ ) 0 ∆ k+1 (δ ) P k (δ ) ∆ k (δ ) B (δ ) ∆ k (δ ) A (δ ) F k (δ ) G k (δ )
(4) where P k (δ ) is a unimodular matrix over R [δ ] that transforms S k (δ ) into its Hermite form. Moreover define {M k (δ )} as follows:

M 0 (δ ) N 0 (δ ) ∆ 0 , N k+1 (δ ) N k (δ ) ∆ k+1 (δ ) , for k ≥ 0 M k+1 (δ ) 0 S N k+1 (δ ) 0 0 0 = Λ k+1 (δ ) N k+1 (δ ) Σ k+1 (δ ) (5)
where

S N k+1 (δ ) = diag{ψ k+1 1 (δ ) , • • • , ψ k+1 r k+1 (δ )} with Λ k+1 (δ ) and Σ k+1 (δ ) being unimodular matrices over R [δ ]
that transform N k+1 (δ ) into its Smith form, and ψ k+1 i (δ ) are called the invariant factors of N k+1 (δ ).

Since we are going to analyze system (2) which is described by the polynomial matrices over R[δ ], therefore let us give some useful definitions of unimodular and change of coordinates over R[δ ]. [START_REF] Hou | An observer design for linear timedelay systems[END_REF] For x(t) defined in (2),z(

Definition 2. A given polynomial matrix

A(δ ) ∈ R n×q [δ ] is said to be left (or right) unimodular over R[δ ] if there exists A -1 L (δ ) ∈ R q×n [δ ] with n ≥ q (or A -1 R (δ ) ∈ R q×n [δ ] with n ≤ q), such that A -1 L (δ )A(δ ) = I q (or A(δ )A -1 R (δ ) = I n ). A square matrix A(δ ) ∈ R n×n [δ ] is said to be unimodular over R[δ ] if A -1 L (δ ) = A -1 R (δ ). Definition 3.
t) = T (δ )x(t) with T (δ ) ∈ R n z ×n x [δ ] and n z ≥ n x is said to be a causal generalized change of coordinates over R[δ ] if rank R[δ ] T (δ ) = n x . Moreover, it is said to be a bicausal gen- eralized change of coordinates over R[δ ] if T (δ ) is left uni- modular over R[δ ].
When applying the algorithm ( 4)-(5) to system (2), it has been proven in [START_REF] Bejarano | Observability of linear systems with commensurate delays and unknown inputs[END_REF] that there always exists a least integer k * , which is independent of the choices of

{P k (δ ), Λ k (δ ), Σ k (δ )}, such that M k * +1 (δ ) = M k * (δ )
, based on which the following assumption will be made.

Assumption 1. For the quadruple (A(δ ), B(δ ),C(δ ), D(δ )) of system (2), there exists a least integer k * ∈ N 0 such that rank R[δ ] M k * (δ ) = n x , and M k * (δ ) is unimodular over R [δ ].
Then the following theorem was stated in [START_REF] Bejarano | Observability of linear systems with commensurate delays and unknown inputs[END_REF].

Theorem 1. If Assumption 1 is satisfied, then there exists a t 1 such that system (2) is backward unknown input observable on [t 1 ,t 2 ] for all t 2 > t 1 .
For simplicity, for any polynomial matrix D(δ

) ∈ R p×m [δ ] with rank R[δ ] D(δ ) = r D ≤ min{p, m}, let us denote Inv S [D(δ )] = {ψ i (δ )} 1≤i≤r D
as the set of its invariant factors of the Smith form defined in (5). Thereby, the following statement, adapted from the result on the left unimodular stated in [START_REF] Hou | An observer design for linear timedelay systems[END_REF], is obvious.

Lemma 1. A polynomial matrix D (δ ) ∈ R p×m [δ ] is left (or right) unimodular over R[δ ] if and only if rank R[δ ] D(δ ) = m ≤ p (or rank R[δ ] D(δ ) = p ≤ m ) and Inv S [D(δ )] ⊂ R. It is said to be unimodular over R[δ ] if and only if rank R[δ ] D(δ ) = p = m and Inv S [D(δ )] ⊂ R.

Main result

Before proposing an unknown input observer for the general system (2), we will firstly decompose system (2) into a simpler form under some additional conditions.

Preliminary result

In order to transform the general system (2) into a simpler form, let us make the following assumption.

Assumption 2. For the polynomial matrices B(δ ), C(δ ) and D(δ ) in system (2), it is assumed that

Inv S   C(δ )B(δ ) D(δ ) D(δ ) 0 B(δ ) 0   = Inv S C(δ )B(δ ) D(δ ) D(δ ) 0 (6)
Remark 2. When treating linear systems without delay, the conditions imposed in Assumption 1 is equivalent to:

rank sI -A -B C D = n + rank B D for all s ∈ C (7)
which is exactly the necessary and sufficient condition such that the system is strongly observable [START_REF] Trentelman | Control Theory for Linear Systems[END_REF].

The condition ( 6) imposed in Assumption 2 is equivalent to:

rank   CB D D 0 B 0   = rank CB D D 0 = rank B D + rankD
and it is exactly the necessary condition to ensure the existence of such a Luenberger-like observer (see Remark 1). As we are going to propose an unknown input observer for the general time-delay system (2) with the same structure, thus the condition ( 6) imposed in Assumption 2 is not restrictive.

Lemma 2. Suppose Assumption 2 is satisfied, then there exists a matrix W (δ ) ∈ R (n x +p)×2p [δ ] satisfying the following conditions:

1) W (δ ) C(δ )B(δ ) D(δ ) D(δ ) 0 = B(δ ) 0 D(δ ) 0 ; 2) for any matrix J(δ ) such that J(δ ) B(δ ) D(δ ) = 0, then J(δ )W (δ ) = 0.
Proof.

For simplicity, let us denote

C BD =   C(δ )B(δ ) D(δ ) D(δ ) 0 B(δ ) 0   and C D = C(δ )B(δ ) D(δ ) D(δ ) 0 .
It is easy to see that if Assumption 2 is satisfied, then we have

rank R[δ ] C(δ )B(δ ) D(δ ) D(δ ) 0 = rank R[δ ]   C(δ )B(δ ) D(δ ) D(δ ) 0 B(δ ) 0   = r
where r denotes the number of invariant factors. Moreover, this implies as well that there exist the unimodular matrices

P 1 (δ ), P 2 (δ ), Q 1 (δ ) and Q 2 (δ ) over R[δ ] such that P 1 (δ ) C(δ )B(δ ) D(δ ) D(δ ) 0 P 2 (δ ) = S C D 0 0 0 and Q 1 (δ )   C(δ )B(δ ) D(δ ) D(δ ) 0 B(δ ) 0   Q 2 (δ ) = S C BD 0 0 0 with S C BD = S C D = diag{ψ 1 , • • • , ψ r }. Then, we obtain   C(δ )B(δ ) D(δ ) D(δ ) 0 B(δ ) 0   ∼ P 1 (δ ) 0 0 I n x   C(δ )B(δ ) D(δ ) D(δ ) 0 B(δ ) 0   P 2 (δ ) ∼   P 1 (δ ) C(δ )B(δ ) D(δ ) D(δ ) 0 P 2 (δ ) B(δ ) 0 P 2 (δ )   since C(δ )B(δ ) D(δ ) D(δ ) 0 ∼ S C D 0 0 0 and   C(δ )B(δ ) D(δ ) D(δ ) 0 B(δ ) 0   ∼ S C BD 0 0 0 , there-
fore, B(δ ) 0 P 2 (δ ) should be spanned by

P 1 (δ ) C(δ )B(δ ) D(δ ) D(δ ) 0 P 2 (δ ) over R[δ ],
otherwise the condition ( 6) is violated. Thus, there exists

a matrix W (δ ) over R[δ ] such that B(δ ) 0 = W (δ )P 1 (δ ) C(δ )B(δ ) D(δ ) D(δ ) 0
, this implies as well that there exists a matrix

W (δ ) ∈ R (n x +p)×2p [δ ] such that W (δ ) C(δ )B(δ ) D(δ ) D(δ ) 0 = B(δ ) 0 D(δ ) 0 .
In order to prove the second condition of Lemma 2, let U(δ ) be a unimodular matrix over R[δ ] which transforms the following matrix into its Hermite form:

U(δ ) C(δ )B(δ ) D(δ ) D(δ ) 0 = V (δ ) 0 where V (δ ) is full row rank over R[δ ]. Since there exists a matrix W (δ ) ∈ R (n x +p)×2p [δ ] such that W (δ ) C(δ )B(δ ) D(δ ) D(δ ) 0 = B(δ ) 0 D(δ ) 0 , then we can find a matrix V (δ ) such that V (δ )V (δ ) = B(δ ) 0 D(δ ) 0 . Finally we can select W (δ ) = [ V (δ ), 0]U(δ ) with which we still have W (δ ) C(δ )B(δ ) D(δ ) D(δ ) 0 = B(δ ) 0 D(δ ) 0 .
Moreover, since V (δ ) is full row rank over R[δ ], then for any matrix J(δ ) such that J(δ ) B(δ ) D(δ ) = 0 we always have

J(δ ) V (δ ) = 0, which implies J(δ )W (δ ) = 0.

System decomposition

Suppose that W (δ ) ∈ R (n x +p)×2p [δ ] is a matrix over R[δ ] such that Lemma 2 is satisfied. Decompose W (δ ) = [W 1 (δ ),W 2 (δ )] with W 1 (δ ),W 2 (δ ) ∈ R (n x +p)×p [δ ], then we have W 1 (δ )D(δ ) = 0 since W (δ ) C(δ )B(δ ) D(δ ) D(δ ) 0 = B(δ ) 0 D(δ ) 0
. Thus, we obtain

W 1 (δ )y = W 1 (δ )C(δ )x
which yields the following equation

W 1 (δ ) ẏ = W 1 (δ )C(δ )A(δ )x + W 1 (δ )C(δ )B(δ )u Since W (δ ) C(δ )B(δ ) D(δ ) = B(δ ) D(δ )
, then we have

W 1 (δ ) ẏ + W 2 (δ )y = W (δ ) C(δ )A(δ ) C(δ ) x + W (δ ) C(δ )B(δ ) D(δ ) u = W (δ ) C(δ )A(δ ) C(δ ) x + B(δ ) D(δ ) u Decompose again the matrix W (δ ) as W (δ ) = K(δ ) Γ(δ ) = K 1 (δ ) K 2 (δ ) Γ 1 (δ ) Γ 2 (δ ) , where K i (δ ) ∈ R n x ×p [δ ] and Γ i (δ ) ∈ R p×p [δ ] for 1 ≤ i ≤ 2.
Thereby, we can substitute B(δ ) D(δ ) u into the original system (2) in order to replace the unknown input u. That is, if Assumption 2 is satisfied, then system (2) can be put into the following simpler form:

ẋ = Ā (δ ) x + K 1 (δ ) ẏ + K 2 (δ )y y = C(δ )x + Γ 1 (δ ) ẏ + Γ 2 (δ )y (8)
where

Ā (δ ) = A (δ ) -K (δ ) C (δ ) A (δ ) C (δ ) ∈ R n x ×n x [δ ] and C(δ ) = C (δ ) -Γ (δ ) C (δ ) A (δ ) C (δ ) ∈ R p×n x [δ ]. Suppose rank R[δ ] C(δ ) = r ≤ p, then there exists a unimodu- lar matrix Λ(δ ) over R[δ ] such that Λ(δ ) C(δ ) = C(δ ) 0 (9) with C(δ ) ∈ R r×n x [δ ] being full row rank over R[δ ]
. By noting ȳ = Λ(δ )y, finally system (8) can be written into the following decomposed form:

ẋ = Ā (δ ) x + K 1 (δ )Λ -1 (δ ) ẏ + K 2 (δ )Λ -1 (δ ) ȳ ȳ = C(δ ) 0 x + Γ1 (δ ) ẏ + Γ2 (δ ) ȳ ( 10
)
where

Γ1 (δ ) = Λ(δ )Γ 1 (δ )Λ -1 (δ ) ∈ R p×p [δ ] Γ2 (δ ) = Λ(δ )Γ 2 (δ )Λ -1 (δ ) ∈ R p×p [δ ] (11)

Observer normal form

This subsection is devoted to designing a Luenberger-Like observer for the deduced simple form (10). Before this, define the following polynomial matrix over R[δ ]:

Ōl (δ ) =      C(δ ) C(δ ) Ā(δ ) . . . C(δ ) Āl-1 (δ )      ∈ R rl×n x [δ ] (12)
where l ∈ N 0 , and let us recall a useful result stated in [START_REF] Hou | Design of observers for linear systems with unknown inputs[END_REF].

Theorem 2. [START_REF] Hou | Design of observers for linear systems with unknown inputs[END_REF] There exists a bicausal generalized change of coordinates z = T (δ )x which transforms the following system:

ẋ = Ā (δ ) x ȳ = C(δ )x ( 13
)
with rank R[δ ] C(δ ) = r into the following observer normal form:

ż = A 0 z + F(δ ) ȳ ȳ = C 0 z where F(δ ) = F T 1 (δ ), • • • , F T l * (δ ) T and A 0 =      0 I r • • • 0 0 0 . . . . . . 0 0 • • • I r 0 0 • • • 0      ∈ R rl * ×rl * C 0 = [I r , 0, • • • , 0] ∈ R r×rl * (14)
if and only if there exists a least integer l * ∈ N 0 such that Ōl * (δ ) defined in ( 12) is left unimodular over R [δ ].

Moreover, the bicausal generalized change of coordinates z 15) with F i (δ ) being determined through the following equations:

= T (δ )x with T (δ ) = col{T 1 (δ ), • • • , T l * (δ )} is defined as fol- lows: T 1 (δ ) = C(δ ) T i+1 (δ ) = T i (δ ) Ā(δ ) -F i (δ ) C(δ ), for 1 ≤ i ≤ l * -1 (
[F l * (δ ), • • • , F 1 (δ )] = C(δ ) Āl * (δ ) Ōl * (δ ) -1 L (16)
Remark 3. Theorem 2 deduces a very simple observer normal form with constant matrices A 0 and C 0 plus a linear output delayed term F(δ ) ȳ for a special form of system (10), which implies in fact that in the original system (2) the matrices B(δ ) = D(δ ) = 0, i.e. system (10) has no inputs. Theorem 2 can be also applied to design a Luenberger-like observer for system (2) with known input, however it cannot treat directly system (2) with unknown input, since the observability in this case depends as well on the matrices B(δ ) and D(δ ).

It has been stated in Theorem 1 that system (2) is backward unknown input observable if Assumption 1 is satisfied. In the following it will be shown that Assumptions 1 and 2 imply that the observability matrix defined in ( 12) is left unimodular. For this, we need the following result.

Lemma 3. If Assumption 1 is satisfied for the quadruple (A(δ ), B(δ ),C(δ ), D(δ )) in system (2), then there exists a least integer l * ∈ N 0 such that

O l * (δ ) =      C(δ ) C(δ )A(δ ) . . . C(δ )A l * -1 (δ )      ∈ R pl * ×n x [δ ] (17) is left unimodular over R [δ ].

Proof.

If Assumption 1 is satisfied for the quadruple (A(δ ), B(δ ),C(δ ), D(δ )) of system (2), then by applying the algorithm defined in (4)-(5) to system (2), we can find an integer k

* ∈ N 0 such that rank R[δ ] M k * (δ ) = n, and M k * (δ ) is unimodular over R [δ ].
Now, consider the first iteration of the algorithm, we have

P 0 (δ ) ∆ 0 (δ )B(δ ) ∆ 0 (δ )A(δ ) D(δ ) C(δ ) = F 1 (δ ) G 1 (δ ) 0 ∆ 1 (δ )
with ∆ 0 (δ ) = 0. Thus, there exist two matrices S 1 (δ ) and

R 1 (δ ) over R [δ ] such that ∆ 1 (δ ) = S 1 (δ )C(δ ) and G 1 (δ ) = R 1 (δ )C(δ ).
In the second iteration, we obtain

P 1 (δ ) ∆ 1 (δ )B(δ ) ∆ 1 (δ )A(δ ) F 1 (δ ) G 1 (δ ) = P 1 (δ ) S 1 (δ )C(δ )B(δ ) S 1 (δ )C(δ )A(δ ) F 1 (δ ) R 1 (δ )C(δ ) = F 2 (δ ) G 2 (δ ) 0 ∆ 2 (δ )
from which we can see that there exist the matrices S 2 (δ )

and

R 2 (δ ) over R [δ ] such that ∆ 2 (δ ) = S 2 (δ ) C(δ ) C(δ )A(δ )
and

G 2 (δ ) = R 2 (δ ) C(δ ) C(δ )A(δ )
. The next iteration yields

P 2 (δ ) ∆ 2 (δ )B(δ ) ∆ 2 (δ )A(δ ) F 2 (δ ) G 2 (δ ) = F 3 (δ ) G 3 (δ ) 0 ∆ 3 (δ ) with ∆ 3 (δ ) = S 3 (δ )   C(δ ) C(δ )A(δ ) C(δ )A 2 (δ )   and G 3 (δ ) = R 3 (δ )   C(δ ) C(δ )A(δ ) C(δ )A 2 (δ )   , for some matrices S 3 (δ ) and R 3 (δ ) over R [δ ].
Thus, by induction we can see that in the k-th iteration there

exists the matrix S k (δ ) such that ∆ k (δ ) =S k (δ )    C(δ ) . . . C(δ )A k (δ )   
with k ∈ N 0 . Hence, the matrix N l (δ ) defined in (5) can be expressed as N l (δ ) = S(δ )O l (δ ) where S(δ ) depends on S i (δ ) and O l (δ ) is defined in (17). Therefore, if Assumption 1 is satisfied for system (2), i.e. there exists a least integer l * ∈ N 0 such that rankM l * (δ ) = n and M l * (δ ) is unimodular over R [δ ], where the unimodular matrix

M l * (δ ) over R [δ ] is the corresponding Smith form of N l * (δ ), then N l * (δ ) is left unimodular over R[δ ]. Thus, N l * (δ ) admits a left inverse matrix [N l * (δ )] -1 L such that I n x = [N l * (δ )] -1 L N l * (δ ) = [N l * (δ )] -1 L S(δ )O l * (δ ) which implies [N l * (δ )] -1 L S(δ ) is a left inverse of O l * (δ ). Therefore O l * (δ ) is left unimodular over R [δ ].
Based on Lemma 3, we have the following result for the deduced system (8).

Lemma 4. If Assumption 1 is satisfied for the quadruple (A(δ ), B(δ ),C(δ ), D(δ )) defined in (2), then for the deduced system (8) there exists a least integer l * ∈ N 0 such that

Õl * (δ ) =      C(δ ) C(δ ) Ā(δ ) . . . C(δ ) Āl * -1 (δ )      ∈ R pl * ×n x [δ ] (18) is left unimodular over R [δ ].
Proof.

According to Lemma 3, we need only to prove that, if Assumption 1 is satisfied for the quadruple (A(δ ), B(δ ),C(δ ), D(δ )), then this assumption is also satisfied for the quadruple Ā(δ ), B(δ ), C(δ ), D(δ ) , which implies that Õl * (δ ) is left unimodular over R [δ ].

For this, by keeping the same matrix P 0 (δ ) as in the proof of Lemma 3 for the quadruple (A(δ ), B(δ ),C(δ ), D(δ )), we obtain:

P 0 (δ ) ∆ 0 (δ )B(δ ) ∆ 0 (δ ) Ā(δ ) D(δ ) C(δ ) = P 0 (δ ) ∆ 0 (δ )B(δ ) ∆ 0 (δ )A(δ ) D(δ ) C(δ ) -P 0 (δ )     0 ∆ 0 (δ )K(δ ) C(δ )A(δ ) C(δ ) 0 Γ(δ ) C(δ )A(δ ) C(δ )     =   S 1 (δ )D(δ ) G 1 (δ ) -S 1 (δ )Γ(δ ) C(δ )A(δ ) C(δ ) 0 ∆ 1 (δ )   for some matrix S 1 (δ ) over R[δ ].
In the last equality we use the fact that, by the result in Lemma 2, any annihi-

lator of B(δ ) D(δ ) is also an annihilator of W (δ ) = K(δ ) Γ(δ ) . Hence ∆ 1 (δ ) for Ā(δ ), B(δ ), C(δ ), D(δ ) is the same as for (A(δ ), B(δ ),C(δ ), D(δ )).
For the second step of the same algorithm, we obtain

P 1 (δ )   ∆ 1 (δ )B(δ ) ∆ 1 (δ ) Ā(δ ) S 1 (δ )D(δ ) G 1 (δ ) -S 1 (δ )Γ(δ ) C(δ )A(δ ) C(δ )   = P 1 (δ ) ∆ 1 (δ )B(δ ) ∆ 1 (δ )A(δ ) S 1 (δ )D(δ ) G 1 (δ ) -P 1 (δ )     0 ∆ 1 (δ )K(δ ) C(δ )A(δ ) C(δ ) 0 S 1 (δ )Γ(δ ) C(δ )A(δ ) C(δ )     =   S 2 (δ ) B(δ ) D(δ ) G 2 (δ ) -S 2 (δ ) K(δ ) Γ(δ ) C(δ )A(δ ) C(δ ) 0 ∆ 2 (δ )   .
Thus, by induction, it is easy to see that the matrix N k (δ ) for the quadruple Ā(δ ), B(δ ), C(δ ), D(δ ) is the same as the matrix N k (δ ) calculated for (A(δ ), B(δ ),C(δ ), D(δ )). Therefore, according to Lemma 3, there exists a least integer l * ∈ N 0 such that Ōl * (δ ) defined in ( 12) is left unimodular over R [δ ].

Lemma 5. If there exists a least integer l * ∈ N 0 such that Õl * (δ ) defined in ( 18) is left unimodular over R [δ ], then Ōl * (δ ) defined in ( 12) is left unimodular over R [δ ].

Proof.

Since there exists a unimodular matrix Λ(δ Theorem 3. If Assumption 1 and Assumption 2 are both satisfied for system (2), then for the deduced system ( 10) there exists a least integer l * ∈ N 0 such that Ōl * (δ ) defined in ( 12) is left unimodular over R [δ ].

) over R[δ ] such that Λ(δ ) C(δ ) = C(δ ) 0 , then we can define the unimodular matrix Λ d (δ ) = diag {Λ(δ ), • • • , Λ(δ )} ∈ R pl * ×pl * [δ ],
Proof. If Assumption 2 is satisfied for system (2), then it can be transformed into system (10). Thus, the proof can be easily achieved by combing the results stated in Lemma 3, Lemma 4 and Lemma 5.

After having proved the left unimodularity of Ōl * (δ ) defined in (12) over R [δ ], the following corollary is obvious due to Theorem 2.

Corollary 1. If Assumption 1 and Assumption 2 are both satisfied for system (2), then there exists a bicausal generalized change of coordinates z = T (δ )x defined in ( 15) such that system ( 10) can be transformed into the following observer normal form:

   ż = A 0 z + [F(δ ), 0] ȳ + K1 (δ ) ẏ + K2 (δ ) ȳ ȳ = C 0 0 z + Γ1 (δ ) ẏ + Γ2 (δ ) ȳ ( 19
)
where Γ1 (δ ), Γ2 (δ ), A 0 , C 0 and F(δ ) are defined in ( 11), ( 14) and ( 16) respectively, with

K1 (δ ) = T (δ )K 1 (δ )Λ -1 (δ ) ∈ R n z ×p [δ ] K2 (δ ) = T (δ )K 2 (δ )Λ -1 (δ ) ∈ R n z ×p [δ ] (20)
where n z = rl * .

Proof. The proof of this corollary just needs to apply the results stated in Theorem 2 and Theorem 3.

Unknown input observer design

For the obtained observer normal form (19), we are ready to present our main result.

Theorem 4. If Assumption 1 and Assumption 2 are both satisfied for system (2), then the following dynamics:

   ξ = L 0 ξ + J(δ )Λ(δ )y ẑ = ξ + H(δ )Λ(δ )y x = T -1 L (δ )ẑ (21)
with T -1 L (δ ) being defined in (15), and

L 0 = A 0 -G 0 C 0 H(δ ) = K1 (δ ) -[G 0 , 0] Γ1 (δ ) J(δ ) = [F(δ ), 0] + K2 (δ ) + L 0 H(δ ) -[G 0 , 0] Γ2 (δ ) + [G 0 , 0] (22)
where G 0 is a constant matrix which makes (A 0 -G 0 C 0 ) Hurwitz, is an exponential unknown input observer for system (2).

Proof. As we have proved that, if Assumption 1 and Assumption 2 are both satisfied for system (2), then it can be transformed into the observer normal form (19). Denote e z = zẑ, e x = xx and note Ḡ0 = [G 0 , 0], F(δ ) = [F(δ ), 0], since ȳ = Λ(δ )y, then we have

ėz = A 0 z -L 0 ẑ + [ F(δ ) + K2 (δ ) + L 0 H(δ ) -J(δ )] ȳ + [ K1 (δ ) -H(δ )] ẏ
Since the pair (A 0 ,C 0 ) is observable, then there exists a constant matrix G 0 such that (A 0 -G 0 C 0 ) is Hurwitz. With the chosen matrix G 0 , we can determine the matrices L 0 , H(δ ) and J(δ ) defined in ( 22), with which the above equation becomes:

ėz = A 0 z -L 0 ẑ + Ḡ0 Γ2 (δ ) -Ḡ0 ȳ + Ḡ0 Γ1 (δ ) ẏ = [A 0 -G 0 C 0 ] e z Since x = T -1 L (δ )z, then e x = x -x = T -1 L (δ )e z is governed by: ėx = T -1 L (δ ) (A 0 -G 0 C 0 ) T (δ )e x Due to the fact that (A 0 -G 0 C 0 ) is a constant Hurwitz matrix, so T -1 L (δ ) (A 0 -G 0 C 0 ) T (δ )
is Hurwtiz as well. Consequently, we proved that system ( 21) is an exponential unknown input observer of system (2).

Remark 4. When treating linear systems without delay, Assumption 1 and Assumption 2 are necessary and sufficient for the existence of a Luenberger-like observer. In this sense, when studying linear systems with delay, the conditions required by Assumption 1 and Assumption 2 are not restrictive to guarantee the existence of a Luenberger-like observer.

Remark 5. The proposed method is based on the output injection (delayed) technique. It can be seen that the observation error dynamics ėz = [A 0 -G 0 C 0 ]e z is independent of the delay, which implies that this method can be applied to any commensurate and constant delay.

For the given quadruple (A(δ ), B(δ ),C(δ ), D(δ )), if Theorem 4 is valid, the following summarizes the procedure to design the proposed unknown input observer for system (2):

Step 1: Compute the unimodular matrix U(δ ) over R[δ ] which transforms the following matrix into its Hermite form:

U(δ ) C(δ )B(δ ) D(δ ) D(δ ) 0 = V (δ ) 0
with V (δ ) being full row rank over R[δ ], and calculate

V (δ ) such that V (δ )V (δ ) = B(δ ) 0 D(δ ) 0 .
Then we obtain the gain matrix W (δ ) = [ V (δ ), 0]U(δ );

Step 2: With the obtained matrix W (δ ), decompose it as

W (δ ) = K(δ ) Γ(δ ) = K 1 (δ ) K 2 (δ ) Γ 1 (δ ) Γ 2 (δ )
, then transform system (2) into (10) with Ā (δ ) = A(δ ) -

K(δ ) C(δ )A(δ ) C(δ ) , C(δ ) = C(δ ) -Γ C(δ )A(δ ) C(δ )
, and find the unimodular matrix Λ(δ

) over R[δ ] such that Λ(δ ) C(δ ) = C(δ ) 0 ;
Step 3: After having obtained Ā(δ ) and C(δ ), deduce T (δ ) defined in (15) and F(δ ) defined in (16); Step 4: Deduce A 0 and C 0 defined in ( 14), Γ1 (δ ) and Γ2 (δ ) defined in (11), K1 (δ ) and K2 (δ ) defined in (20); Step 5: Design the observer of the form (21) by choosing the matrices L 0 , H(δ ) and J(δ ) defined in ( 22).

Remark 6. The above procedure involves the computations over polynomial matrices. There exist lots of packages already implemented in Matlab and Maple which enable us to easily realize those calculations by computer.

Illustrative example

Consider the following example:

A(δ ) =     0 -1 1 0 -1 δ 0 0 1 0 1 0 δ 1 1 -1     , B(δ ) =     0 0 0 0 1 1 0 δ     C(δ ) =   δ 0 0 0 0 1 0 0 0 0 1 1   , D(δ ) =   1 δ 0 0 1 δ  
For the given quadruple (A(δ ), B(δ ),C(δ ), D(δ )), by applying the algorithm ( 4)-( 5), we find that there exist k * = 3 such that M k * = M k * +1 = I 4 , thus Assumption 1 is satisfied. Moreover, by calculating the invariant factors we have

Inv S   C(δ )B(δ ) D(δ ) D(δ ) 0 B(δ ) 0   = Inv S C(δ )B(δ ) D(δ ) D(δ ) 0 = {1, 1, 1}
therefore Assumption 2 is satisfied as well. According to Theorem 4, there exists a Luenberger-like observer to exponentially estimate the state of the studied system.

Step 1:

In order to transform the matrix

C(δ )B(δ ) D(δ ) D(δ ) 0 into
its Hermite form, we can find

U(δ ) =         δ 0 -δ 1 0 δ -1 0 1 0 0 -1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 -1 0 1 0 0 0 0 1 0         and V (δ ) =   1 0 0 0 0 1 0 0 0 0 1 δ   , then we can find V (δ ) =   0 0 1 0 1 0 1 0 0 1 δ δ 0 δ 0 0 0 0 0 0 0   T such that V (δ )V (δ ) = B(δ ) 0 D(δ ) 0 , which gives us W (δ ) = K 1 (δ ) K 2 (δ ) Γ 1 (δ ) Γ 2 (δ ) =           0 0 0 0 0 0 0 0 0 0 0 0 δ -1 0 1 -δ 1 0 δ -1 -δ 0 δ 0 0 -δ 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0          
Step 2: With the above deduced W (δ ), we obtain:

Ā (δ ) =     0 -1 1 0 -1 δ 0 0 δ 2 -δ δ 2 -1 -δ 2 + 2δ -2δ + 2 -δ 2 1 -δ -δ 2 1 -δ + δ 2 2δ -1     and C(δ ) =   0 0 0 0 0 1 0 0 -δ 0 1 1   , thus we can choose the uni- modular matrix over R[δ ] as Λ(δ ) =   0 1 0 0 0 1 1 0 0   , which gives C(δ ) = 0 1 0 0 -δ 0 1 1 .
Step 3: With the deduced Ā(δ ) and C(δ ), we can check that there

exists l * = 3 such that Ō3 (δ ) =         0 1 0 0 -δ 0 1 1 -1 δ 0 0 -δ 0 1 1 -δ 1 + δ 2 -1 0 -δ 0 1 1         is left unimodular over R[δ ], with Ō3 (δ ) -1 L =     δ 0 -1 0 0 0 1 0 0 0 0 0 1 0 δ 0 -1 0 δ 2 -1 1 -2δ 0 1 0     , which gives [F 3 (δ ), F 2 (δ ), F 1 (δ )] = C(δ ) Ā3 (δ ) Ō3 (δ ) -1 L with F(δ ) =   F 1 (δ ) F 2 (δ ) F 3 (δ )   =         -2 -δ 2 + 5δ 0 0 0 1 + 3δ -5δ 2 + δ 3 0 0 0 3 -4δ -δ 2 + δ 3 2δ -2 0 1         (23)
Then we obtain the bicausal generalized change of coordinates z = T (δ )x where

T (δ ) =         0 1 0 0 -δ 0 1 1 -1 2 -4δ + δ 2 0 0 -δ 0 1 1 -2 + 4δ -δ 2 -δ + δ 2 -1 0 -δ 0 1 1         with [T (δ )] -1 L =     2 -4δ + δ 2 0 -1 0 0 0 1 0 0 0 0 0 -19δ 2 + 15δ + 8δ 3 -4 -δ 4 0 -4δ + 2 + δ 2 0 -1 0 15δ 2 -13δ -7δ 3 + 4 + δ 4 0 3δ -2 -δ 2 1 1 0    
Step 4: With the deduced change of coordinates, the studied system can be transformed into the simple observer form (19) with F(δ ) given in ( 23) and -10, -10, -25, -25, -50, -50).

A 0 =         0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0         ,C 0 = 1 0 0 0 0 0 0 1 0 0 0 0 K1 (δ ) K2 (δ ) =         0 0 0 0 0 0 0 1 -1 0 -1 1 0 0 0 0 0 0 0 1 -1 0 -1 1 0 δ -1 1 -δ 0 1 -δ -1 0 1 -1 0 -1 1         Γ1 (δ ) Γ2 (δ ) =   0
And finally we obtain the following gain matrices:

L 0 =         -85 0 1 0 0 0 0 -85 0 1 0 0 -2000 0 0 0 1 0 0 -2000 0 0 0 1 -12500 0 0 0 0 0 0 -12500 0 0 0 0         H(δ ) =         0 0 0 0 1 -1 0 0 0 0 1 -1 0 δ -1 1 -δ 0 1 -1         J(δ ) =         83 + 5δ -δ 2 0 0 0 0 0 2001 -5δ 2 + 3δ + δ 3 δ -1 1 -δ 0 0 0 12503 -4δ -δ 2 + δ 3 δ -1 -1 0 0 1        
Step 5: With the deduced L 0 , H(δ ) and J(δ ), one can easily design the unknown input observer described in (21). In the simulation of the studied system, we set the unknown input as u 1 = -10 sin 100t and u 2 = 20 sin 20t (see Fig. 1). The simulation step is 0.001s, and the basic delay h = 0.01s. By choosing the calculated gain matrices L 0 , H(δ ) and J(δ ), the observation errors (in log scale) are given in Fig. 2, from which we can notice not only the convergence of the proposed observer, but also the delay effect in the observer which is equal to 0.04s and it is due to the term δ 4 in [T (δ )] -1 L . The singularity in the figure is due to the fact that the observation error passes zero and changes the sign. In order to show that the proposed method is independent of the time-delay involved in the studied system, another simulation was made with the same gains and a bigger delay h = 0.1s, whose results (again in log scale) were depicted in Fig. 3. Compared Fig. 2 with Fig. 3, we can conclude that, with two distinct delays, the resulting estimation errors converge to 0 with the same speed, depending on the eigenvalues of T -1 L (δ ) (A 0 -G 0 C 0 ) T (δ ). Moreover, with a bigger delay, the estimations will have a bigger delay as well (in Fig. 3 the delay effect in the observer equals to 0.4s, corresponding to the term δ 4 in [T (δ )] -1 L ). In order to show the robustness of the proposed observer, the third simulation (the same gains with h = 0.01s) was made by adding a mean-zero random disturbance in the output belonging to [-2, 2]. The estimation errors are depicted in Fig. 4 and it can be noticed that the estimation error is always bounded.

Conclusion

The class of linear time-delay systems investigated in this paper is quite larger than that those in the literature since we consider unknown inputs in both the state equation and in the system output. Moreover, commensurate delays are allowed to appear in the state, input, and in the output also. We have matched the backward unknown input observability condition recently obtained in [START_REF] Bejarano | Observability of linear systems with commensurate delays and unknown inputs[END_REF], with the observability condition required in [START_REF] Hou | An observer design for linear timedelay systems[END_REF] for the observer design of linear time-delay systems without inputs. The required conditions for the observer design are considerably relaxed in the sense that they coincide with the necessary and sufficient conditions for the unknown input observer design of linear systems without delays.

  and there exists an elementary matrix E ∈ R pl * ×pl * such that EΛ d (δ ) Õl * (δ ) = Ōl * (δ ) 0 which shows that the left unimodularity of Õl * (δ ) over R [δ ] defined in (18) implies the left unimodularity of Ōl * (δ ) defined in (12) over R [δ ].

T

  such that (A 0 -G 0 C 0 ) has negative eigenvalues (

Figure 1 :

 1 Figure 1: Unknown input u of the studied system.

Figure 2 :Figure 3 :

 23 Figure 2: The observation error (in log scale) for h = 0.01s.

Figure 4 :

 4 Figure 4: The observation error for h = 0.01s with noisy measurement.

Preprint submitted to ElsevierJuly 10, 2015

⋆ This paper was supported by Ministry of Higher Education and Research, Nord-Pas de Calais Regional Council and FEDER through the Contrat de Projets Etat Region (CPER) CIA 2007-2013, and also supported by ARCIR Project ESTIREZ, Nord-Pas de Calais Regional Council. F.J. Bejarnano acknowledges as well the support of Proyecto SIP 20151040, Mexico.