Nancy Ide

Laurent Romary

TOWARDS INTERNATIONAL STANDARDS FOR LANGUAGE RESOURCES

Keywords: language resources, standards, corpora, linguistic annotation, ISO, American National Corpus 1

come   L'archive ouverte pluridisciplinaire

INTRODUCTION

As noted in Cole, et al., 1997, years of research and development in computational linguistics and language engineering have yielded many stable results, which have in turn been integrated into language processing applications and industrial software. Especially over the past fifteen years, researchers and developers have increasingly understood the need to define common practices and formats for linguistic resources, which serve HLT development as the primary source for statistical language modeling. To answer this need, numerous projects have been launched to lay the basis for standardization of resource representation and annotation--e.g., the Text encoding Initiative (TEI) 1 , the Corpus Encoding Standard (CES and XCES) 2 , the Expert Advisory Group on Language Engineering Standards (EAGLES) and the International Standard for Language Engineering (ISLE) 3 -as well as software platforms for resource creation, annotation, and use--MULTEXT 4 , LT XML 5 , GATE6 , NITE7 , ATLAS8 ). However, although in practice consensus has begun to emerge, definitive standards have not yet been put in place. In large part this is as it should be: advances in technology together with the emergence of a solid body of web-based standards have dramatically impacted and re-defined many of our ideas about the ways in which resources will be stored and accessed over the past several years. Perhaps more importantly, the ways in which language data-together with "communicative" data of any kind, including gesture, facial expression, speech characteristics-are processed and analyzed will certainly continue to change, as more and more emphasis is put on immediate processing of (often multi-modal) streamed data. Whatever the scenario, though, if we intend to make HLT work in the larger arena of universal availability and accessibility, data, its annotations, and processing results will have to be represented in some way that allows exploitation by the full array of language processing technologies.

It has been argued that attempting standardization for language resources and surrounding information is premature, and the evolving nature of the domain and technology certainly speaks to that claim. But the growth of the web and the explosion in the number of electronic documents to be handled and maintained within the industrial sector has created an immediate and urgent need for generic language processing components for document indexing and classifying, information extraction, summarization, topic detection, etc., in both mono-and multi-lingual environments, together with robust machine translation and facilities for man-machine multimodal communication. While progress will continue, the field has nonetheless reached a point where we can see clear to a reasonable representation and processing model that should fulfill the needs of HLT for at least the foreseeable future. Indeed, commonality that can enable flexible use and reuse of communicative data is essential for the next generation of language processing applications, if we are to build a global information environment. It is therefore critical at this time to move toward standardization, and in particular, to do this in an internationally accepted framework.

It is in this context that a committee of the International Standards Organization (ISO), TC 37/SC 4, has been established to develop standards for language resource management, with the aim of building on existing 3 http://www.ilc.cnr.it/EAGLES96/home.html 4 http://www.lpl.univ-aix.fr/projects/multext 5 http://www.ltg.ed.ac.uk/software/xml technologies and schemes to codify best practices as a set of standards for representing and processing language-related information, as a means to leverage the growth of language engineering. Fully aware that its activities will be necessarily on-going and evolving, the committee has set out the following general goals: -to provide means to use and reuse linguistic data across applications, at all levels of linguistic description from surface mark-up of primary sources to multi-layered processing results; -to facilitate maintenance of a coherent document life cycle through various processing stages, so as to enable enrichment of existing data with new information and the incremental construction of processing systems;

BACKGROUND

Before initiating any standardizing activity, it is necessary to identify its scope and relation to past and/or on-going activities. As a starting point, Figure 1 describes the general "ecology" of language resources and the interdependencies required for their management. Primary resources may be texts, spoken data, multi-modal data (e.g., hand motion, eye gaze, perceptual settings, etc.). Linguistic information consists of annotations (ranging from phonetic and morpho-syntactic annotation to discourse level annotations such as reference chains, dialogue structure, etc.) associated with a segment or segments of a primary resource

Access protocols

Meta-data

Linguistic information

Primary resources

Lexical structures

Knowledge structures

LINKS

or other descriptive layer. 9 Lexical and knowledge structures may be linked to primary resources and annotations, or created from primary resources; they are most often used to support linguistic analysis, including annotation. As such, they often are the source of information that is used for linguistic annotation. Meta-data can be regarded as another type of annotation associated with a document containing primary or annotation data, which identifies and describes the resource. Finally, links and access protocols provide the mechanisms for representing and accessing language resources.

Over the past 20 years, numerous projects and initiatives have worked toward the development of standards for one or more of the components pictured above, as well as for a general architecture that would enable efficient representation of the resources themselves together with the "links" establishing the inter-dependencies among them. Among the most notable are the TEI, CES and XCES, and MATE/NITE for the representation of primary data and annotations; EAGLES/ISLE for annotation content; OLIF 10 , SALT 11 , and ISLE for various kinds of lexical/terminological data; RDF/OWL and Topic Maps for knowledge structures; Dublin Core and the Open Archives Initiative (OAI) 12 for general metadata; MPEG7, IMDI, and OLAC for domain-specific metadata; Corba 13 and the W3C's SOAP 14 and web services work for access protocols; and MULTEXT, Edinburgh's LT framework, TIPSTER 15 , GATE, and ATLAS for general architecture. Most of these projects actually address several of what we can regard as the multiple "dimensions" of language resource representation, including (at least) the following:

Rendering formats and mechanisms, such as SGML, XML, Lisp-like structures, annotation graphs, or a particular database format.

Annotation content, including categories of annotation information for linguistic phenomena (e.g., modality, aspect, etc.) and the values that can be associated with each category.

General architectural principles for language resources, such as the now widely-accepted notions of pipeline architecture and stand-off annotation. 9

In fact, the term "primary resource" is somewhat misleading, since each transcription or annotation level can be regarded as a primary resource for another level. This notion of multiple information layers is the underlying principle for stand-off markup. 10 http://www.olif.net/ 11 http://www.loria.fr/projets/SALT/ 12 http://www.openarchives.org/ 13 http://www.corba.org/ 14 http://www.w3.org/TR/soap/ 15 http://www.fas.org/irp/program/process/tipster.htm Even here, there are inter-dependencies: for example, the choice of a representation format will have repercussions for content, first of all because relations among pieces of information may be expressed implicitly through the structures provided by the format, the most common of which is a hierarchical structure for grouping and/or defining part/whole relations. Some formats impose other constraints-for example, Lisp-like formats provide a hierarchical structure but do not readily accommodate labeling the structures to distinguish their function (e.g., grouping, listing alternatives, etc.), as one might do in XML by simply giving a tag a meaningful name. Similarly, implementing stand-off annotation with XML dictates use of XML paths, pointers, and links. As a result, format and content have in past projects often been treated as a whole, rather than addressing them separately.

Despite the numerous projects and initiatives that have sought to establish standards for various aspects of linguistic annotation, there remains no universally accepted set of practices and categories, and there continues to be considerable re-invention of the wheel within the international community. This begs the question: why should the ISO effort succeed where others have failed? There are several answers to this question, the most notable of which is the evolution of technology, both in terms of the availability of accepted frameworks that operate within the web context, including primarily World Wide Web Consortium (W3C) standards such as XML and RDF/OWL, together with cross-platform/web-adaptable software development tools such as Java. However, the technological advances resulting from development of the web has done more than provide us with widely accepted standards for language data representation. The shift from stand-alone applications to an environment where both data and software is distributed over the web has dramatically impacted the ways in which we create and represent language resources and their annotations, as well as the kinds of information we want to represent. The enhanced potential to exploit the web to share, merge, and compare language data has itself encouraged widespread adoption of W3C representation standards, and indeed, the web itself has come to be regarded as a virtually infinite "corpus" of multilingual and multi-modal data. In addition, in the context of the web certain language processing applications-e.g., information retrieval and extraction, summarization, etc., together with applications that handle multi-modal data-have taken the foreground, and the kinds of information that we are most interested in identifying and processing has evolved in tandem. The web has also spawned heightened interest in what we can regard as "on the fly" annotation and analysis for streamed data, and more generally, a need to support incremental annotation at various linguistic levels.

Attempts to standardize linguistic content categories and their values have always been plagued by the thorny problem of varying linguistic theories and application needs: some de facto standards, such as WordNet for semantic annotation, have emerged, but there is relatively little commonality in this area beyond these few exceptions despite massive efforts such as the EAGLES/ISLE project. The forces driving new interest in harmonization of annotation content are similar to those driving standardization for data representation: the existence of the web and the promise of a "semantic web" demand common terminology for every level of description, as the recent efforts to develop standard meta-data categories and ontologies demonstrate. The ontology efforts also show how difficult content standardization is to achieve. So, while we have increased motivation to develop linguistic content categories, and possibly a better base than at any time in the past from which to proceed, this aspect of language resource standardization can only be approached cautiously and, likely, far more slowly than resource representation.

With a sounder technological base and a clearer idea of where we need to go, yet another standardization effort seems to be in order. It is important to note, however, that the ISO effort builds to the extent possible on previous efforts, adopting the parts it can and extending or modifying them as seems necessary, and taking advantage of the incremental convergence of opinion on various aspects of the process that has directly resulted from attempts at standardization and/or commonality in the past. To this end, the ISO group has established collaborations with major standardizing groups, including most of the prior initiatives enumerated above as well as others involved in standardization activities, in order to ensure that the development of ISO standards for language resource management both incorporates and reflects existing practice and informs on-going work within these other groups. In addition, the on-going work within the ISO committee is continually presented at major conferences and workshops so that the community is aware of our work and can comment and contribute to the effort.

The "incremental view" of standardization, wherein standards are developed over a series of iterations that potentially span decades, informs both the work within ISO/TC 37/SC 4 and the place of its work in the overall scheme. The standards developed by this ISO sub-committee may not be the final word on language resource representation and management, but they will, we hope, take a necessary step toward that goal. Our work, like the creation of the web-based infrastructure being developed by W3C and others, is best seen as part of a development process that can be compared to building a brick wall: we add brick by brick, layer by layer, and occasionally develop some infrastructural component that adds a significant piece to the overall construction. We are not sure when or where this process will end, but each effort is required for eventual completion.

THE LINGUISTIC ANNOTATION FRAMEWORK

The Linguistic Annotation Framework (LAF) is intended to provide a standard infrastructure for representing language resources and their annotations that can serve as a basis for harmonizing existing resources as well as developing new ones.

Annotation of linguistic data may involve multiple annotation steps, for example, morpho-syntactic tagging, syntactic analysis, entity and event recognition, semantic annotation, co-reference resolution, discourse structure analysis, etc. Annotation at lower linguistic levels typically serves as input to the higher-level annotation process in an incremental process. Depending on the application intended to use the annotations, lower-level annotations may or may not be preserved in a persistent format. For example, information extraction software often annotates linguistic features required to generate the final annotation, without preserving the intermediate information. In other situations, the annotation process may not be strictly incremental. For example, when handling streamed data (text, video, and audio, a stream of sensor readings, satellite images, etc.) the processor analyzes language data in a linear, time-bound sequence, and therefore annotations may be temporarily partial during processing if long-distance dependencies between seen and unseen segments of the data exist.

At present, most annotated resources are static entities used primarily for training annotation software, as well as corpus linguistics and lexicography. However, in the context of the Semantic Web, annotations for a variety of higher-level linguistic and communicative features will increasingly be preserved in web-accessible form and used by software agents and other analytic software for inferencing and retrieval. This dictates that the LAF not only relies on web technologies (e.g., RDF, OWL) for representing annotations, but also that "layers' of annotations for the full range of annotation types (including named entities, time, space, and event annotation, annotation for gesture, facial expression, etc.) are at the same time separable (so that agents and other analytic software can access only those annotation types that are required for the purpose, and mergeable (so that two or more annotation types can be combined where necessary). They may also need to be dynamic, in the sense that new and/or modified information can be added as necessary.

The LAF consists of two major components:

1. an abstract data model and a concrete representation format isomorphic to the model;

a mechanism for defining and using linguistic categories and values

Each of these components is covered in the following sections.

Architecture and abstract model

In order to ensure that the LAF architecture reflects state-of-the-art methods drawn from consensus of the research community, a group of experts [START_REF] Romary | Keith Suderman (Vassar College)[END_REF] was convened in November, 2002, to lay out its overall structure. The group, which included researchers with extensive experience in the development of annotation schemes at a variety of linguistic levels together with developers of major resource-handling software (GATE, ATLAS, Edinburgh LT tools), defined the general architecture pictured in Figure 2.

The fundamental principle underlying the LAF architecture is that the user controls the representation format for linguistic resources and annotations, using any desired scheme (XML, LISP structures, or any other format). The only restriction applied to the user format is that it must be mappable to an abstract data model. This mapping is accomplished via a rigid "dump" format, isomorphic to the data model and intended primarily for machine rather than human use.

To guide the LAF development, the following general principles were outlined by the group of experts:

• The data model and document form are distinct but mappable to one another

• The data model is parsimonious, general, and formally precise.

• The document form is largely under user control.

• The mapping between the flexible document form and data model is via a rigid dump-format. The responsibility of converting to the dump format is on the producer of the resource.

• Mapping is operationalized via either a schema-based data-binding process or schema-derived stylesheet mapping between the user document and the dump format instantiation. The mapping from document form to the dump format is documented in an XML Schema (or the functional equivalent thereof) associated with the dump format instantiation.

• It must be possible to isolate specific layers of annotation from other annotation layers or the primary (base) data; i.e., it must be possible to create a dump format instantiation using stand-off annotation

• The dump format supports stream marshalling and unmarshalling The dump format is isomorphic to the underlying abstract data model, which is built upon a clear separation of the structure of linguistic information (including annotations and knowledge structures) and content, that is, the linguistic information itself. A document and its annotations form a directed graph capable of referencing n-dimensional regions of primary data as well as other annotations. In the primary data, the nodes of the graph are virtual, located between each "character" in the primary data, where a character is defined to be a contiguous byte sequence of a specified length. 18 When an annotation references another annotation document rather than primary data, the nodes are the edges within that document that have been defined over the primary data or other annotation documents. That is, given a graph, G, over primary data, we create an edge graph G' whose nodes can themselves be annotated, thereby allowing for edges between the edges of the original graph G. Edges are labeled with feature structures containing the annotation content relevant to the data identified by the edge. The choice of this model is indicated by its almost universal use in defining generalpurpose annotation formats, including the Generic Modeling Tool (GMT) (Ide and Romary, 2001, 2002; Ide, et al., 2003) and Annotation Graphs (Bird and Liberman, 2001). All annotations are stand-off--i.e., represented in documents separate from the primary data and other annotations-in order to support incremental annotation and separability of different annotation levels.

The graph of feature structures contains elementary structural nodes to which one or more feature structures are attached, providing the semantics ("content") of the annotation. A small inventory of logical operations (e.g. disjunction, sets) over the feature structures is specified, which define the model's abstract semantics. These operations provide the same expressive power as those defined for general-purpose, typed feature structures. Semantic coherence is provided by a registry of features maintained RDF/OWL format, as described below in section 3.2. Users may define their own data categories or establish variants of categories in the registry. In the latter case, the newly defined data categories are formalized using the same format as definitions available in the registry. A schema providing the mapping of categories used in the document to categories in the registry and the formal specification of newly-defined categories is associated with the dump format instantiation.

In the LAF scenario, the dump format is invisible to users; users work only with their own formats, and transduce to and from the dump format only for processing and exchange. Thus, each site need only define a mapping between an in-house format and the dump format in order to use resources produced by any other site.

Data Category Registry

It is important to note that in principle, the dump format places no restrictions on annotation content (i.e., the categories and values in an annotation); annotation content is effectively user-defined, taken directly from the user's original annotation. However, it is obvious that harmonization of content categories is a critical next step toward standardizing annotations. LAF is addressing this far more controversial and problematic issue separately. Two major activities within SC4 are aimed at harmonization of annotation content: (1) definition of user annotation formats for different annotation levels 19 , and (2) creation of a Data Category Registry (DCR) containing pre-defined data elements and schemas that can be used directly in annotations (Ide and Romary, 2004).

Differences in approach to language resources and among individual system objectives inevitably lead to variations in data category definitions and data category names. The use of uniform data category names and definitions within the same resource domain (e.g., among terminological, lexicographical, text corpus, etc. resources), at least at the interchange level, contributes to system coherence and enhances the re-usability of data. Procedures for defining data categories in a given resource domain should also be uniform in order to ensure interoperability.

We define a data category as an elementary descriptor used in a linguistic annotation scheme. In feature structure terminology, data categories include both attributes (hereafter called type descriptors) such as SYNTACTIC CATEGORY and GRAMMATICAL GENDER, as well as a set of associated atomic values taken by such attributes, such as NOUN and FEMININE. In both cases we distinguish between the abstraction (concept) behind an attribute or value, and its realization as some string of characters or other object. Figure 3 provides an overview of these relationships. Whereas there is only one concept for a given attribute or value, there may be multiple instantiations. The DCR under development within ISO/TC 37/SC 4 is built around this fundamental concept/instance distinction. In principle, the DCR provides a set of reference concepts, while the annotator provides a Data Category Specification (DCS) that comprises a mapping between his or her schemespecific instantiations and the concepts in the DCR. As such, the DCS provides documentation for the linguistic annotation scheme in question. The DCS for a given annotation document/s is included or referenced in any data exchange to provide the receiver with the information required to interpret the annotation content or to map it to another instantiation. Semantic integrity is guaranteed by mutual reference to DCR concepts.

To serve the needs of the widest possible user community, the DCR must be developed with an eye toward multi-lingualism. The Data Category Registry will support multiple languages by providing the following:

• reference definitions for data categories in various languages;

• data element names for the data categories in various languages;

• description of usage in language-specific contexts, including definitions, usage notes, examples, and/or lists of values (e.g., GENDER takes the values masculine, feminine in French; masculine, feminine, neuter in German)

In addition, to both accommodate archival data and ensure semantic integrity, a mapping of data categories instantiated in the DCR to categories and values in well-known projects and initiatives will be provided.

The creation of a single global data category registry for all types of language resources treated within TC 37 provides a unified view over the various applications of the resource. However, for the purposes of both category creation and DCR access, the DCR will be organized according to thematic views, i.e. domains of activity, which include specialized subsets of the information in the registry. Given the on-going activities within TC 37, we can envisage definable subsets of the DCR for at least the following: terminological data collection, various types of linguistic annotation (morpho-syntactic, syntactic, discourse level, etc.), lexical representation for both NLP-oriented and traditional lexicography, language resource metadata, and language codes. Figure 4 illustrates the relationship between data category specifications and the DCR. The patterned cells correspond to individual DCS's. Some data categories are relevant to a single domain, while others are common to multiple domains: for example, sense number is probably specific to lexicographical resources, but linguistic categories such as part of speech, grammatical gender, grammatical number, etc. have wider application. Each thematic domain contributes all its data categories the global DCR, while at the same time identifying those data categories that it with other domains. The oval shapes in the Venn diagram represent DCS subsets. A smaller subset can be selected from the domain DCS for use in a given application, as represented by the octagon in Figure 4. Note that while some of the data categories contained in this subset are common to several different domains, this application is wholly contained within the DCS for terminological entries, so we can conclude that it is designed for use with a terminological application.

We intend to proceed cautiously, implementing categories that are widely used and relatively low-level, to ensure acceptance by the community. By Chapter # building up slowly, the DCR should eventually contain a wide range of data categories, with their complete history, data category description, and attendant metadata. It would then be possible to specify a DCS (see previous section) for different thematic domains and an ontology of relations among them. In the short term, it is likely unreasonable to define such an ontology until there is greater awareness and consensus at the international level. No choice should be made in the definition of the DCR that would hamper further work in this direction.

So far, we have defined a preliminary template for data category definitions to be used as an underlying model for the DCR (ISO DIS 12620 under ISO committee TC 37/SC 3), which can also serve as a model for manipulation and transmission of proprietary data categories within the language engineering community. The heart of a data category description is the Conceptual Entry section, which we define to include the following fields:

ENTRY IDENTIFIER used for interchange of data category DEFINITION reference definition for the category, language and theory neutral to the extent possible.

EXPLANATION additional information about the data category not relevant in a definition (e.g. more precise linguistic background for the use of the data category); EXAMPLE illustration of use of the category, excluding language specific usages (documented elsewhere) SOURCE may refine definition, explanation, or example to indicate the source from which the corresponding text has been borrowed or adapted. STATUS may refine definition to indicate approval, acceptability, or applicability in a given context PROFILE relates the current data category to one or several views (e.g. Morpho-syntax, Syntax, Metadata, Language description, etc.) CONCEPTUAL RANGE relates the category to the set of possible values (expressed as a list of data categories). A datatype may be provided instead of a list of values NOTE additional information excluding technical information that would normally be described within explanation BROADER CONCEPT generic pointer to a more general data category (e.g., from Common noun to Noun).

Using the DCR

The purpose of the DCR is to promote greater usability and reusability of annotated language resources and increased semantic integrity for information in annotation documents by providing a set of formally-defined reference categories. "Formal definition" in this context includes natural language definitions for each category accompanied by specification of the possible values each category may take. At present, we envision instantiation of the DCR as a simple database in which each entry is either a type descriptor or value. Data categories will be referenced either by the DCR entry identifier, or, since the DCR will be publicly available on-line, via a URI.

Note that this simple instantiation of the DCR makes no distinction in terms of representation between type descriptors and values; each is considered as a data category and provided with an entry identifier for reference. Only minimal constraints on their use in an annotation are specified--i.e., constraints on descriptor/value combinations given in the descriptor entry. The broader structural integrity of an annotation is provided by placing constraints on nodes in the annotation graph (as defined in the LAF architecture) with which a given category can be associated. For example, the structural graph for a syntactic constituency analysis would consist of a hierarchy of typed nodes corresponding to the non-terminals in the grammar, with constraints on their embedding, and with which only appropriate descriptor/value pairs may be associated. Node types (e.g., NP, VP) as well as associated grammatical information (e.g., tense, number) may all be specified with data categories drawn from the DCR.

A more formal specification of data categories can be provided using mechanisms such as RDF Schema (RDFS) and the Ontology Web Language (OWL) to formalize the properties and relations associated with data categories. For example, consider the following RDF Schema fragment: <rdfs:Class rdf:about="#Noun"> <rdfs:label>Noun</rdfs:label> <rdfs:comment>Class for nouns</rdfs:comment> </rdfs:Class> <rdfs:Property rdf:about="#number"> <rdfs:domain rdfs:resource="Noun"/> <rdfs:range rdf:resource="rdfs:#Literal"/> </rdfs:Property> This fragment defines a class of objects called " "Noun" that have the property "number". Note that the schema defines the classes but does not instantiate objects belonging to the class; instantiation may be accomplished directly in the annotation file, as follows (for brevity, the following examples assume appropriate namespace declarations specifying the URIs of schema and instance declarations)

Chapter # <Noun rdf:about="Mydoc#W1"> <number rdf:value="Plural"/> </Noun> where "Mydoc#W1" is the URI of the word being annotated as a noun. Alternatively, the DCR could contain instantiations of basic data elements, specifying values for properties, which can be referenced directly in the annotation. For example, the DCR could include the following instantiation: <Noun rdf:ID="NMP"> <number rdf:value="plural"/> </Noun> An annotation document could then reference the pre-defined instance as follows:

<rdf:Description rdf:about="myDoc#W1"> <POS rdf:resource="categories#NMS"/> </rdf:Description>20 An RDFS/OWL specification of data categories would enable greater control over descriptor/value use and also allow for the possibility of inferencing over annotations. RDFS/OWL descriptions function much like class definitions in an object-oriented programming language: they provide, in effect, templates that describe the properties of an object, specify constraints on which objects can provide the value for a given property, and specify super-and sub-class relations among objects. For example, a general dependent relation may be defined for a verb object, which must have one of the possible values argument or modifier; argument can in turn have the possible values subject, object, or complement, etc. 21 In a document containing a syntactic annotation, several objects with the type argument may be instantiated, each with a different value. Based on the RDFS/OWL definition, each instantiation of argument is recognized as a sub-class of dependent and inherits the appropriate properties.

Definition of a precise hierarchy of linguistic categories and properties is a massive undertaking, and it is far from obvious that such a hierarchy could be agreed upon within the community. Therefore, we are proceeding cautiously to define hierarchical relations among categories, and leaving the bulk of this activity to users of the DCR. We will provide a library of RDF/OWL specifications describing hierarchical relations together with value constraints, inter-dependencies, etc., than can be used as desired by annotators. We expect that the library will be built up gradually from our initial descriptions and the contributions of users.

It cannot be overemphasized that the goal of the DCR is not to impose a specific set of categories, but rather to ensure that the semantics of data categories included in annotations are well-defined, either by referring to categories that are formally described in the DCR or by formal definition of new or variant categories. The DCR, at least at the outset, can only help us to move toward commonality in annotation content, which is becoming more and more essential as annotated language data is increasingly distributed over multiple sites and accessible via the web.

In the end, the DCR will come into widespread use only if it is easy for annotators to use and provides useful categories for various kinds of resource annotation. Ease of use can be assured by providing ready-to-use templates for reference to the DCR from within annotation documents, enabling immediate web access to definitions in a clear and concise format, and, perhaps above all, ensuring that at least a few highly visible projects use DCR references. The initial inclusion of categories that are for the most part relatively atomic and universally accepted is a move toward ensuring their usefulness for linguistic annotation, but, if the DCR is to be truly successful, it will also be necessary to include and demonstrate the use of categories that have become, for better or worse, de facto standards defined by widely used resources. The obvious example is WordNet: whatever its shortcomings for NLP, Wordnet is the most universally used resource in the field, and there are now over thirty wordnets in different languages built around the same categories and concepts. One way to bring the DCR into general use is to implement a "DCR-aware" version of WordNet that specifies a mapping of Wordnet categories to the DCR, and, on the other hand, ensure that WordNet-specific categories (e.g., synset) and all categories used in Wordnet (e.g., meronym, hypernym, etc.) are in fact included in the DCR. Similarly, a mapping of categories in FrameNet, which is now also being replicated for other languages, and other existing of developing "standards" such as the EAGLES morpho-syntactic categories, TIME-ML22 , etc., can be made available via the DCR website. In this way, annotators will become aware of DCR categories and have real examples demonstrating DCR use.

PUTTING IT ALL TOGETHER

To illustrate how the LAF principles are applied in practice, consider an interchange scenario between two users ("A" and "B"), each having his/her own annotation scheme for a given annotation layer, and a third user ("C")

Chapter # who wants to use both A's and B's annotations. Such a scenario is in fact typical within evaluation campaigns such as PARSEVAL.

A and B apply LAF by mapping the descriptors used in their respective annotation schemes to categories in the DCR. The mapping is specified using an RDF/OWL schema, for which a template or automatic generation tool is available on the DCR website. If categories used in the user-specific annotation scheme are not included in the DCR, or if a DCR definition for a given category requires modification or extension, the new or variant categories are fully defined in the schema (again using a template or tool available on the DCR website).

Next, the user format is transduced to a LAF representation. The transduction may reveal that some of the annotation information in the user's scheme is implied by its structure; for example, in the Penn Treebank (PTB) syntactic annotation, the "subject" relation between a noun phrase and a verb phrase is implied by their relative positions in the parse tree represented by the LISP format, while the "object" relation is given explicitly (via an NP-Obj label) because the position of an NP in the tree is less definitively indicative of its semantic role. Similarly, embedded "S-units" in the PTB imply what is often called an "xcomp" relation, which in turn (implicitly, in the PTB) inherits its subject from the S-unit within which it is nested. In order to use such implicit information, the software must be aware that, for instance, the first NP within an S is to be considered the subject. However, it should not be expected that user C's software is designed to make this inference, and therefore LAF compliance requires that such information be made explicit by the creator of the original scheme when transducing to LAF format. 23 The transduction process demands familiarity with the LAF XML format and moderate computational expertise to create a transduction script. LAFcompliaint annotations are represented in a generic XML format for specifying edges (using a <struct> element, historically so-named to stand for "structural node") and the associated feature structures; as such, the XML elements provide the structure of the annotation but do not include any information concerning annotation content. The actual content of the annotation is provided in the attribute/value pairs within the feature structure. 24 The transduction process therefore involves user-specific structures (e.g., nested parentheses in the PTB LISP example) to XML 23 It is of course possible to generate a LAF representation without making implicit information explicit, thus placing the burden of extracting the information on the user of the LAF instantiation. LAF guidelines can "require" explicitness in principle, but they cannot ensure that it is enforced. 24 A full description of the XML feature structure representation can be found in ISO standard 24610-1. See also the TEI guidelines, chapter 16 (http://www.tei-c.org/release/doc/tei-p5doc/html/FS.html).. <struct> elements, and filling attribute value slots in the feature structure encoding with the appropriate labels. Because all LAF annotation documents are stand-off, it also may involve disentangling data and annotations, and providing XPointer links from edges (<struct> elements) in the annotation document to the primary data. An example of a PTB transduction to LAF format is given in Figures 5a and5b. Each <struct> element corresponds to an edge in the graph, traversing the indicated span in the primary data. <feat> elements provide the feature/value pairs associated with the immediate parent node. 25 Note that in this example, XML embedding of <struct> elements reflects the constituency relations among the edges, reflecting the LISP tree-structure. We take advantage of the fact that XML processors will reconstruct the implied tree structure from the embedding, while at the same time we providing sufficient information to reconstruct it automatically from the values given in the TARGET attributes if XML processing is unavailable or inapplicable.

When user C obtains the LAF version of A's and B's annotations, the only processing requirement is that his tool understand the dump format to extract the annotation information in each one, either in order to use them directly in an application or transduce them to an in-house format of his own. Because both user A and user B have provided a mapping of their respective categories in the RDF/OWL schema that accompanies the LAFcompliant annotation documents, user C can readily translate schemespecific categories such as "NP" to his own category designation, if they differ. So, for example, if user A uses "NP" for noun phrases, and user B uses "Nominal", then if both A's and B's RDF/OWL schemas map these two desgnations to a common DCR category, user C knows that the two notations represent the same concept. User C, in turn, can map A's and B's notations to his own notation for that concept, if desired.

((S (NP-SBJ-1 Paul) (VP intends) (S (NP-SBJ *-1) (VP to (VP leave (NP IBM)))) .))

Figure 5.a. PTB annotation of "Paul intends to leave IBM". 25 The use of <feat> elements in this example show the use of a simplified XML format for feature structures that is sufficient for many types of annotation information. In cases where the full power of FS representation is required, the TEI/ISO standard XML representation for feature structures can be used.

A Case Study: The ANC

The American National Corpus (ANC) project 26 , which is creating a 100 million word corpus of American English comparable to the British National Corpus, is representing its data and annotations in accordance with the LAF specifications. The ANC is being heavily annotated for a variety of linguistic information, including morpho-syntax, syntax, named entities, semantics (WordNet sense tags and FrameNet frames), etc., and the project is providing multiple alternative annotations at each level produced by different automatic annotation tools. In order to accommodate the layering of several different POS taggings, noun and verb chunks, dependency and constituency parse annotation schemes, and named entity annotations, and in particular to enable merging annotations when desired, it is necessary to use a common representation that can accommodate many different kinds of annotation. Therefore, the ANC has chosen to represent all annotations in the LAF dump format. The annotation set for each ANC document includes the header for that document and the primary data with no internal markup, together with all applicable annotation documents. The header points to the primary data as well as each annotation document; annotation documents are linked to the primary data.

The ANC's choice to use the LAF representation makes the data extremely flexible: the primary text can be used with no markup or annotations if desired (which is commonly the case for concordance generation, etc.), or the user can choose to deal with a particular annotation set independent of the text (e.g to generate statistics for POS taggers or parsers). Furthermore, annotations of many different types, or several versions of a single annotation type (e.g., multiple part of speech taggings), can be provided without encountering the problems of incompatibility (in particular, the famous "overlapping hierarchy" problem that arises when different systems assign different boundaries to words or other elements in data). Most importantly, users acquire all annotations in a common format; if users were to generate annotations for the ANC data on their own, each annotation-including annotations of the same type-would be in a different format and require special processing. By rendering all annotations in LAF format, comparison and merging of annotations becomes a far simpler task.

At present, few software systems handle stand-off annotation, and those that do often demand computational expertise beyond what many ANC users--who include linguists, teachers of English as a second language, etc.-have access to. Therefore, the ANC project has developed an easy-to-use tool and user interface27 (Suderman and Ide, 2006) to merge the stand-off annotations of the user's choice with the primary data and produce the merged document in any of several formats, including, at present, a wellformed XML document in XCES format (suitable for use with various search and access interfaces such as the BNC's XAIRA28 ), WordSmith/MonoConc Pro format, and text with part of speech tags appended to each word and separated by an underscore. The ANC merging tool implements the org.xml.sax.XMLReader, and therefore it is relatively trivial for users to provide their own interface in order to produce output in any format, or to perform other operations on the data (e.g. frequency counts, bigram generation, etc.). By using this tool, the ANC user need never deal directly with or see the underlying representation of the corpus and its stand-off annotations, but gains all the advantages that representation offers.

Because the DCR is still in its development phase, ANC annotation documents do not currently provide RDF/OWL schema mappings to DCR categories. Furthermore, because many ANC annotations are generated automatically using a wide range of freely available or contributed software, determining the mapping for each annotation document may be unfeasible. The ANC will, however, provide the DCR mapping for categories used to annotate its 10 million word "gold standard" sub-corpus, which includes hand-validated annotations for morpho-syntax, syntax, named entities, WordNet senses, and FrameNet frames. As such, the ANC should provide a proof of concept for the LAF architecture, and serve as a usage example upon which others can build.

CONCLUSION

The framework presented here for linguistic annotation is intended to allow for variation in annotation schemes while at the same time enabling comparison and evaluation, merging of different annotations, and development of common tools for creating and using annotated data. We have developed an abstract model for annotations that is capable of representing the necessary information while providing a common encoding format that tools can be adapted to manipulate and access as well as a means to combine and compare annotations. The details presented here provide a look "under the hood" in order to show the flexibility and representational power of the abstract scheme; however, the intention is that annotators and users of syntactic annotation schemes can continue to use their own or other formats with which they are comfortable, and translation into and out of the abstract format will be automatic.

Our framework for linguistic annotation is built around some relatively straightforward ideas: separation of information conveyed by means of structure and information conveyed directly by specification of content categories; development of an abstract format that puts a layer of abstraction between site-specific annotation schemes and standard specifications; and creation of a Data Category Registry to provide a reference set of annotation categories. The emergence of XML and related standards, together with RDF/OWL, provides the enabling technology. We are, therefore, at a point where the creation and use of annotated data and concerns about the way it is represented can be treated separately-that is, researchers can focus on the question of what to represent, independent of the question of how to represent it. The end result should be greater coherence, consistency, and ease of use and access for linguistically annotated data.

The abstract model that captures the fundamental properties of an annotation scheme provides a conceptual tool for assessing the coherence and consistency of existing schemes and those being developed. The model enforces clear distinctions between implicit and explicit information (e.g., functional relations implied by structural relations in constituent syntactic analyses) and phrasal and functional relations. It is alarmingly common for annotation schemes to represent these different kinds of information in the same way, rendering their distinction computationally intractable (even if they are perfectly understandable by the informed human reader). Handdeveloped annotation schemes used in treebanks are often described informally in guidebooks for annotators, leaving considerable room for variation; for example, Charniak (1996) notes that the PTB implicitly contains more than 10,000 context-free rules, most of which are used only once. Comparison and transduction of schemes becomes virtually impossible under such circumstances. While requiring that annotators make relations explicit and consider the mapping to the abstract format increases overhead, we feel that the exercise will help avoid such problems, and can only lead to greater coherence, consistency, and inter-operability among annotation schemes.

Figure 1 .

 1 Figure 1. Ecology of language resources

  Figure 2. LAF Architecture

  Figure 3. Data category overview

Figure 4 .

 4 Figure 4. Relation of Data Category Selections to the DCR

Figure 5

 5 Figure 5.b. Dump format instantiation of "Paul intends to leave IBM".

http://www.tei-c.org

http://www.xml-ces.org

http://gate.ac.uk/

http://www.dfki.de/nite/main.html

http://www.nist.gov/speech/atlas/

Draft documents and working papers for the various areas, including morpho-syntactic annotation (ISO/TC 37/SC 4 document N225), syntactic annotation (ISO/TC 37/SC 4 document N244), word segmentation (ISO/TC 37/SC 4 document N233), etc. are available at http://www.tc37sc4.org/.

In these examples, NUMBER is given literal values. However, with OWL it is possible to restrict the range of possible values by enumeration.

Cf. the hierarchy in Figure1.1, Caroll, Minnen, and Briscoe (2004).

http://www.timeml.org

http://AmericanNationalCorpus.org

http://americannationalcorpus.org/tools/index.html#xces-parser

http://sourceforge.net/projects/xaira


Keywords: telomere length, epidemiology, prospective study

Spurious association between telomere length reduction over time and baseline telomere length

Ehrlenbach and co-workers found a linear relationship between baseline relative telomere length (RTL) and the decrease of RTL over 10 years (r=0.674; P<0.001). [START_REF] Ehrlenbach | Influences on the reduction of relative telomere length over 10 years in the population-based Bruneck Study: introduction of a well-controlled highthroughput assay[END_REF] Similarly, others have reported on this relationship between the telomere attrition rate and the baseline telomere length and found largely similar associations. [START_REF] Nordfjäll | The individual blood cell telomere attrition rate is telomere length dependent[END_REF][START_REF] Aviv | Leukocyte telomere DYNAMICS: longitudinal findings in young adults of the Bogalusa Heart Study[END_REF] Likewise, when we correlated the RTL and delta RTL during 7 years of follow-up in 75 men from the Zutphen Elderly Study [START_REF] Giltay | Cardiovascular risk profile and subsequent disability and mental well-being: the Zutphen Elderly Study[END_REF] with an age range of 70 to 91 years we found a largely identical association (r=0.733; P<0.001; unpublished data).

We question whether this association is trivial. We used a random number generator to produce 510 baseline RTL values, similar to the number of pairs in the study of Ehrlenbach et al. [START_REF] Ehrlenbach | Influences on the reduction of relative telomere length over 10 years in the population-based Bruneck Study: introduction of a well-controlled highthroughput assay[END_REF] A mean of 1.49 was aimed at for baseline values and 1.05 at 10-years follow-up, with distributions comparable to those presented in Table 1. [START_REF] Ehrlenbach | Influences on the reduction of relative telomere length over 10 years in the population-based Bruneck Study: introduction of a well-controlled highthroughput assay[END_REF] Using these random numbers, we found a beta coefficient that was nearly similar to the beta coefficient that was presented in Table 2 (0.557 as compared to 0.589, respectively). Because baseline RTL (X) was used to calculate the RTL shortening rate (X-Y), the 'dependent' and 'independent' variables were functionally related. [START_REF] Senn | Importance of trends in the interpretation of an overall odds ratio in the metaanalysis of clinical trials[END_REF] Pearson's correlation coefficients using randomly generated factors can be estimated to be around 1/√2, if baseline and outcome have equal variances. [START_REF] Senn | Importance of trends in the interpretation of an overall odds ratio in the metaanalysis of clinical trials[END_REF] Therefore, it was to be expected that a linear regression model would best fit the data (as X was regressed on X-Y) and that an exceptional P-value of 2.3x10 -90 was found (Table 2). [START_REF] Ehrlenbach | Influences on the reduction of relative telomere length over 10 years in the population-based Bruneck Study: introduction of a well-controlled highthroughput assay[END_REF] We think that the slope of the regression line should have been tested against the slope of a no-effect line, instead of zero (i.e., a horizontal line).

We therefore think that the reported association is not explained by older cells having lower division rates nor by telomerase that acts preferentially on short telomeres as a special protection mechanism, as was suggested as potential explanations, 1,2 but is merely a

of

consequence of mathematical coupling. It seems more likely that the attrition rate of RTL is biologically independent of baseline RTL.

Conflict of interest: None declared.


T Boukhobza
email: taha.boukhobza@cran.uhp-nancy.fr

F Hamelin

G Kabadi

S Aberkane

Discrete mode Observability of switching linear systems with unknown inputs. A graph-theoretic approach

Keywords: Switching linear systems, mode observability, sensor location, graph theory

This paper deals with the observability of the discrete mode of switching structured linear systems with unknown inputs. The proposed method, based on a graph-theoretic approach, assumes only the knowledge of the system's structure. We express, in graphical terms sufficient conditions for the generic observability of the discrete mode. If these conditions are not satisfied, we also propose a sensor placement procedure which allows to recover the mode observability. More precisely, we provide an exhaustive location set for additional sensors to recover the given sufficient mode observability condition. Our approach uses algorithms which have polynomial complexity orders and assumes only the knowledge of the system's structure. It can be implemented by classical graph-theory algorithms.

INTRODUCTION

Hybrid systems, combining event-driven and time-driven dynamics, have received growing attention in the control community as they can be used to describe a wide range of physical and engineering systems [START_REF] Johansson | Hybrid systems in automotive control[END_REF][START_REF] Antsaklis | Hybrid systems: Theory and applications[END_REF][START_REF] Van Der Schaft | An introduction to hybrid dynamical systems[END_REF]. For such systems, the general problem of estimating the mode, the internal state and the unknown input is of great interest in many control areas. In the context of switching continuous time linear systems, studies presented in [START_REF] Babaali | Observability of switched linear systems in continuous time[END_REF][START_REF] Santis | Observability of internal variables in interconnected switching systems[END_REF][START_REF] Santis | Observability and detectability of linear switching systems: A structural approach[END_REF][START_REF] Vidal | Observability of linear hybrid systems[END_REF] are among the most significant works which deal with observability. They characterize completely the observability of the continuous internal state and/or the discrete mode variable, which is assumed to be unknown and arbitrary. Other definitions of observability for other kinds of hybrid systems are also provided in the literature. For instance, [START_REF] Bemporad | Observability and controllability of piecewise affine and hybrid systems[END_REF][START_REF] Collins | Observability of piecewise-affine hybrid systems[END_REF][START_REF] Chaib | Observability of the discrete state for dynamical piecewise hybrid systems[END_REF] study the observability of hybrid linear systems, where the discrete mode depends on the state trajectory or is associated to discrete outputs. Deterministic discrete-time switching linear systems were considered in [START_REF] Vidal | Observability and identifiability of jump linear systems[END_REF][START_REF] Babaali | On the observability of piecewise linear systems[END_REF][START_REF] Bemporad | Observability and controllability of piecewise affine and hybrid systems[END_REF], knowing that, contrary to classical linear systems, important differences exist between the discrete and continuous time cases for switching linear systems (SLS) [START_REF] Babaali | Observability of switched linear systems in continuous time[END_REF]. Even if our study is only concerned by mode observability, From the point of view of the class of systems under study and observability definitions used here, our paper is close to [START_REF] Babaali | Observability of switched linear systems in continuous time[END_REF][START_REF] Santis | Observability of internal variables in interconnected switching systems[END_REF][START_REF] Vidal | Observability of linear hybrid systems[END_REF][START_REF] Santis | Observability and detectability of linear switching systems: A structural approach[END_REF]. But, our proposed method and the obtained results present two main originalities. On the one hand, few works deal with the observability of hybrid systems with unknown inputs, which model disturbances or faults for example. In fact, there exist some works ( [START_REF] Pina | Simultaneous state and input estimation of hybrid systems with unknown inputs[END_REF] and the references therein), which aim at designing unknown input observers for SLS, but they do not study state and input observability. [START_REF] Vu | On invertibility of switched linear systems[END_REF] addresses the problem of recovering the discrete mode variable and the input given an output and an initial state but not simultaneous state and input observability. On the other hand, in most cases, observability analysis for SLS deals with algebraic and geometric tools and so requires the exact knowledge of the state space matrices characterizing the systems' model. In many modeling problems or during conception stage, these matrices have a number of fixed zero entries determined by the physical laws while the remaining entries are not precisely known. In these cases, to study the structural properties, like observability, the idea is that we only keep the zero/non-zero entries in the state space matrices. Thus, we consider models where the fixed zeros are conserved while the non-zero entries are replaced by free parameters. Many interesting works on these models, called structured models, are related to the graph-theoretic approach and aim to analyse properties such as controllability, observability . . . [START_REF] Dion | Generic properties and control of linear structured systems: a survey[END_REF]. It results from these works that the graphtheoretic approach provides quite simple and elegant analysis tool. In this context, the first part of the paper is proposed a graphbased approach to provide sufficient conditions which ensure the discrete mode observability for switching structured linear systems (SSLS). In a second part, and using a graph-theoretic approach, we address the problem of sensor placement in order to recover discrete mode observability property. More precisely, we answer to the following question: when the discrete mode of a SLS is not generically observable, where can we place efficiently additional sensors to recover this property ? All the proposed results are based on classical combinatorial algorithms with polynomial order complexity. This may be an important criterion when we deal with large scale systems. Moreover, since we consider structured systems, our approach can be used during a conception stage. The paper is organised as follows: after Section 2, which is devoted to the problem formulation, some definitions related to the graph-theoretic approach are given in Section 3. The main results are enounced in Section 4 before a brief conclusion.

PROBLEM STATEMENT

Consider the following SLS

Σ : ẋ(t) = A(r t )x(t) + B(r t )u(t) y(t) = C(r t )x(t) + D(r t )u(t) (1)
where x ∈ R n , u ∈ R m and y ∈ R p are respectively the state vector, the unknown input vector and the output (measurement) vector and where A(•), B(•), C(•) and D(•) are real matrices of compatible dimensions. The exogenous and unobserved discrete mode variable (or switching signal) r : [0, ∞) → Q def = {1, . . . , N }, is assumed, as in [START_REF] Babaali | Observability of switched linear systems in continuous time[END_REF], to be right-continuous and only a finite number of jumps can occur in any finite interval of [0, ∞). It results that all the system trajectories are well defined and infinitely right-differentiable over [0, ∞). Zeno behaviors can thus not occur, even though no minimum dwell time is imposed. Note that, contrary to non-hybrid linear systems, when we study observability, we cannot remove the known inputs from the model, as discrete mode observability depends also on input-output links [START_REF] Santis | Observability and detectability of linear switching systems: A structural approach[END_REF]. Nevertheless, without loss of generality and for the sake of homogeneity, all the inputs are assumed to be unknown. In fact, the control input signals, whose values are known, are considered to be measured i.e. we associate a virtual output equation of the form y k ′ = u k to these inputs. Moreover, our aim is to address, in the same framework autonomous SLS and SLS with known or unknown inputs. It results that, the discrete mode observability as it is defined in [START_REF] Santis | Observability of internal variables in interconnected switching systems[END_REF], cannot be used since it is dependent on input vector and so cannot be satisfied for autonomous SLS. We choose here to release this constraint on discrete mode observability to have a more general framework by imposing mode distinguishability not for all but for generic initial conditions x 0 and unknown inputs u: Definition 1. (Mode distinguishability) Two modes q ∈ Q and q ′ ∈ Q with (q = q ′ ) are distinguishable if at least one of the two following conditions holds: -there exist an integer s ≥ 0 and an expression Ψ q (y, ẏ, . . . , y (s) ) = 0 which is satisfied for mode q but is not satisfied for mode q ′ for almost all initial conditions x 0 and inputs u.

-there exist an integer s ′ ≥ 0 and an expression Ψ q ′ (y, ẏ, . . . , y (s ′ ) ) = 0 which is satisfied for mode q ′ but is not satisfied for mode q for almost all initial conditions x 0 and inputs u.

Here, " for almost all initial conditions x 0 and inputs u(t) " is to be understood as " for all (x T 0 , u T ) T ∈ R n+m except for the zero set of some polynomials with real coefficients in the n+m initial state and input components. These polynomials can be written down explicitly, i.e. we can precisely describe when the mode distinguishability fails to be true. Obviously u(t) ≡ 0 and x 0 = 0 are two of these polynomials. The zero set of some polynomial forms a proper algebraic variety of R n+m which has Lebesgue measure zero. So, by the expression " for almost all initial conditions x 0 and input functions u " we mean for all initial conditions and inputs except the ones belonging to a proper algebraic variety in the state and input space. The interpretation of Definition 1 is that q is distinguishable from q ′ if, for generic initial states x 0 and unknown input u, we can rule out q or q ′ when observing the output over [0, T ]. Relatively to the definitions of [START_REF] Babaali | Observability of switched linear systems in continuous time[END_REF], our notion of distinguishability of q and q ′ is equivalent to the fact that q is discernible from q ′ or vice-versa. The mutual mode discernibility, which is a dissymmetric property in [START_REF] Babaali | Observability of switched linear systems in continuous time[END_REF], is equivalent to have both conditions of Definition 1 satisfied. Definition 2. (Location observability) SLS (Σ) is location observable if its modes are all distinguishable two-by-two i.e. ∀q ∈ Q, ∀q ′ ∈ Q, with q = q ′ , q and q ′ are distinguishable.

Comparatively with the notion of location observability defined in [START_REF] Santis | Observability and detectability of linear switching systems: A structural approach[END_REF][START_REF] Santis | Observability of internal variables in interconnected switching systems[END_REF], our definition concerns as well as autonomous and non-autonomous systems. In [START_REF] Santis | Observability and detectability of linear switching systems: A structural approach[END_REF][START_REF] Santis | Observability of internal variables in interconnected switching systems[END_REF], location observability is defined as the ability to reconstruct the mode starting from the knowledge of the input and the output, for any nonzero input value and for all initial conditions. Since we deal with unknown input systems, this definition is not applicable and it cannot be achieved for autonomous systems. In our definition, we relax this by accepting that the reconstruction of the mode may be possible not for all but for almost all inputs and initial condition values. Location observability analysis can be reduced to the study of the distinguishability of each pair of modes. Thus, for the sake of simplicity, there is no loss of generality in considering in the first part of the paper, that we have only two modes. At the end of Section 4, we extend the obtained results to the multiple modes case. Since we study structural properties, it is pertinent to deal with structured systems, for which we assume that only the sparsity pattern of matrices A(q), B(q), C(q) and D(q) is known for q ∈ {1, 2}. So, to each entry of these matrices, we only know whether its value is fixed to zero, or that it has an unknown real value represented by a real parameter λ i . The vector of these parameters is Λ = (λ 1 , λ 2 , . . . , λ h )

T and it is assumed that Λ can take any value in R h or equivalently that parameters λ i are free. We denote by A λ (q), B λ (q), C λ (q) and D λ (q) respectively the matrices obtained by replacing the nonzeros in A(q), B(q), C(q) and D(q), for q ∈ {1, 2} by the corresponding parameters λ i and we denote

Σ Λ : ẋ(t) = A λ (r t )x(t) + B λ (r t )u(t) y(t) = C λ (r t )x(t) + D λ (r t )u(t) (2)
If all parameters λ i are numerically fixed, we obtain a so-called admissible realization of SSLS (Σ Λ ). We say that a property is true generically for SSLS (Σ Λ ) if it is true for almost its realizations or equivalently for almost all parameters λ i . Location observability analysis is based on the distinguishability of the structured models associated to the two discrete modes. So, it is pertinent and necessary to highlight the similarities and the differences between the models associated to these modes. Thus, we decompose each structured matrix into two parts: the first one is common to the two modes and the second one is specific to each mode i.e. for q ∈ {1, 2},

A λ (q) = A λ 0 + A λ q , B λ (q) = B λ 0 +B λ q , C λ (q) = C λ 0 +C λ q and D λ (q) = D λ 0 + D λ q .
When we write the matrices under this form, we assume that the entries of all these matrices are free. These notations are generalized to the multi-mode case in subsection 4.5. To summarize, our first aim is to provide sufficient conditions to check if a SSLS is generically location observable i.e. is location observable for almost all its realizations or equivalently for almost all parameters λ i . Next, when these conditions are not satisfied, we provide additional sensors' locations which allow to recover the location observability property.

GRAPHICAL REPRESENTATION OF STRUCTURED SWITCHING LINEAR SYSTEMS

The digraph associated to

(Σ Λ ) is noted G(Σ Λ ).
It is constituted by a vertex set V and an edge set E i.e. G(Σ Λ ) = (V, E). The vertices are associated to the continuous state, the input and the output components of (Σ Λ ) and the directed edges represent links between these variables. More precisely, V = X ∪ U ∪ Y, where X = {x 1 , . . . , x n }, U = {u 1 , . . . , u m } and Y = {y 1 , . . . , y p } are respectively the set of state, input and output vertices. For q ∈ {0, 1, 2}, we define

E q = A q -edges ∪ B q -edges ∪ C q -edges ∪ D q -edges, where, for q ∈ {0, 1, 2}, A q -edges = {(x j , x i ) | A q (i, j) = 0}, B q -edges = {(u j , x i ) | B q (i, j) = 0}, C q -edges = {(x j , y i ) | C q (i, j) = 0} and D q -edges = {(u j , y i ) | D q (i, j) = 0}. Finally the edge set is E = 2 q=0 E q .
Here, M (i, j) is the (i, j)th element of matrix M and

(v 1 , v 2 ) denotes a directed edge from vertex v 1 ∈ V to vertex v 2 ∈ V.
The edges included in E 0 represent the common part of the two modes' models, while E q , for q ∈ {1, 2} is related to the specific part of each mode's model. For the sake of clarity, the vertices are written in bold fonts to differentiate them from the corresponding variables. Each edge is associated to a free non-zero parameter of the system's model called the weight of the edge. Note that number q is written under each E q -edge and represents its index. Example 1. To the system defined by the following matrices, we associate the digraph in Figure 1.

A λ 0 =      
0 0 0 0 0 0 0 0 0 0 λ1 0 0 0 0 0 0 λ2 0 0 0 0 0 0 0 0 0 0 λ3 0 0 λ4 0 λ5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 λ6 λ7 0 0 0 0 0 0 0 0 λ8 0

      , B λ 0 =       0 0 0 0 0 λ12 0 0       , C λ 0 =
λ13 0 0 0 0 0 0 0 0 0 0 0 λ14 0 0 0 0 0 0 λ15 0 0 0 0 0 0 0 0 0 0 0 λ16 , all the entries of A λ 1 are zero The digraph representing the SSLS is built from the superposition of the digraphs related to each mode. In order to study the properties of the system associated to a specific mode q, we have to restrict the edge set to E 0 ∪ E q . In this context, many of the functions and specific vertex subsets, defined below, present an index q related to the considered mode.

except A λ 1 (1, 2) = λ 9 , all the entries of A λ 2 are zero ex- cept A λ 2 (5, 2) = λ 10 and A λ 2 (7, 6) = λ 11 , the elements of matricesB λ 1 , B λ 2 , C λ 1 , C λ 2 , D λ 0 , D λ 1 and D λ 2 are equal to zero.
Let us now give some useful definitions and notations.

•

A path P is denoted P = v s0 → v s1 → . . . → v s i , where (v s j , v s j+1 ) ∈ E for j = 0, 1, . . . , i -1.
We say in this case that P covers v s0 , v s1 , . . . , v s i .

• The weight of P is the product of the weights of all its edges.

• A path is simple when every vertex occurs only once in this path.

• A cycle is a path of the form v s0 → v s1 → . . . → v s i → v s0
, where v s0 , v s1 , . . . , v s i are distinct.

• For q ∈ {1, 2}, we say that path P is included in E 0 ∪ E q if all its edges are included in E 0 ∪ E q .

• Some paths (resp. cycles) are disjoint if they have no common vertex.

• P is a Y-topped path if its end vertex belongs to Y. A Ytopped path family consists of disjoint simple Y-topped paths.

In the sequel, V 1 and V 2 represent two subsets of V. We denote by card(•) the cardinality function and

V 1 \ V 2 is the set of elements in V 1 which are not in V 2 . • A path P = v s0 → v s1 → . . . → v s i is said a V 1 -V 2 path if v s0 ∈ V 1 and v s i ∈ V 2 .
Moreover, if the only vertex of P which belongs to V 1 is v s0 and the only vertex of P which belongs to

V 2 is v s i , P is called a direct V 1 -V 2 path. • For q = {1, 2}, ρ q V 1 , V 2 is the maximal number of disjoint V 1 -V 2 paths included in E 0 ∪ E q . Moreover, a set of ρ q V 1 , V 2 disjoint V 1 -V 2 paths included in E 0 ∪ E q is a maximum V 1 -V 2 linking in E 0 ∪ E q . • For q ∈ {1, 2}, V ess,q V 1 , V 2 is the vertex subset includ- ing the vertices present in all the maximum V 1 -V 2 linkings included in E 0 ∪ E q .
• For q ∈ {1, 2}, there exists a unique vertex subset noted S o q V 1 , V 2 and called minimum output separator which is the set of begin vertices of all direct

V ess,q V 1 , V 2 -V 2 paths in- cluded in E 0 ∪ E q . In Example 1, ρ 1 U, Y = ρ 2 U, Y = 1 and ρ 1 {x 1 , x 2 , x 3 }, Y = ρ 2 {x 1 , x 2 , x 3 }, Y = 2. More- over, V ess,2 {x 3 }, Y = {x 3 , x 2 , x 5 } but V ess,1 {x 3 }, Y = {x 3 , x 2 } because there exists in E 0 ∪ E 1 a path which from x 3 to Y which does not cover x 5 : x 3 → x 2 → x 1 → y 1 . Finally, S o 1 U, Y = {x 8 }, S o 2 {x 3 }, Y = {x 5 } and S o 1 {x 3 }, Y = {x 2 }.
Function ρ q and the two vertex subsets V ess,q and S o q constitute the classical graphic-notions used in most of the results related to the structural analysis using a graph-theoretic approach. Indeed, ρ q is associated to the generic rank of transfer matrices and pencil matrices for example and is useful in the analysis of many problems as disturbance-rejection, input-output decoupling, fault detection and isolation [START_REF] Dion | Generic properties and control of linear structured systems: a survey[END_REF]. Subsets V ess,q and S o q are often used, as we will see later, in the system's decomposition [START_REF] Van Der Woude | The generic number of invariant zeros of a structured linear system[END_REF] or in the graph simplification because for some properties, analysing all the graph is not always necessary.

• In G(Σ Λ ), for each mode q, two vertices v i and v j are said to be strongly connected in mode q, if it exists a path included in E 0 ∪ E q from v i to v j and a path included in E 0 ∪ E q from v j to v i . In each mode, the relation "is strongly connected to" is an equivalence relation and we can define its equivalence classes. We call each equivalent class related in mode q by a q-strongly connected component (q-scc). These q-scc are well known in the graph theory [START_REF] Murota | System Analysis by Graphs and Matroids[END_REF]. They can be ordered using a partial order relation " " defined between two q-scc V i and V j as V i V j if there exists a path, included in E 0 ∪ E q , from an element of V j to an element of V i .

• For each mode q, a q-scc V i is maximal if there is no distinct q-scc V j such that V i V j .

• We define, for each mode q, the union of all maximal q-scc:

V or,q = {v ∈ V i , where V i is a maximal q-scc} = V i is a maximal q-scc V i . In
= {u 1 , x 2 , x 3 }. Furthermore, S o 1 V or,1 , Y = {x 2 , x 8 }.
In mode 2, the strongly connected components are the same. However, since there is no edge between x 2 and x 1 , the latter is also a maximal 2-scc. Therefore, V or,2 = {u 1 , x 1 , x 2 , x 3 }. Furthermore, S o 2 V or,2 , Y = {y 1 , x 5 , x 8 }.

MAIN RESULTS

Preliminaries

In a first stage, hereafter we recall some existing results useful to establish our observability conditions. These results are mainly issued from [START_REF] Murota | System Analysis by Graphs and Matroids[END_REF][START_REF] Reinschke | Multivariable Control. A Graph Theoretic Approach[END_REF][START_REF] Van Der Woude | The generic number of invariant zeros of a structured linear system[END_REF][START_REF] Van Der Woude | Zero orders and dimensions of some invariant subspaces in linear structured systems[END_REF][START_REF] Dion | Generic properties and control of linear structured systems: a survey[END_REF]. Consider subset W q = S o q V or,q , Y . We have, according to Menger's Theorem, that card(W q ) = ρ q V or,q , Y . Furthermore, let us denote by Xq all the state vertices belonging to direct W q -Y paths and which are not in W q . The dynamics of the state components associated to Xq is then on the form : Σq : ẋq = Āλ q xq + Bλ q w q y = Cλ q xq + Dλ q w q (3)

where w q , xq are the input and state components associated respectively to vertices of Wq and Xq . Furthermore, since W q = S o q V or,q , Y , an important remark can be done now and is summarized in the following lemma: Lemma 1. Considering subsystem ( Σq ) constituted by input w q , state xq and output y. For each Y u = {y i1 , y i2 , . . . , y i k } ⊂ Y such that ρ q W q , Y u = card(W q ), there exist, generically, a matrix G, a function ϕ and an integer ν ≤ n q def = card(X q ) such that w q = ϕ(Y u , Ẏu , . . . , Y

(ν) u ) + Gx q , where Y u (ν) = (y (ν) i1 , y (ν) i2 , . . . , y (ν)
i k ) T

Proof: According to [START_REF] Dion | Generic properties and control of linear structured systems: a survey[END_REF] (Theorem 4), for subsystem ( Σq ), the existence of Y u = {y i1 , y i2 , . . . , y i k } ⊂ Y such that ρ q W q , Y u = card(W q ), implies the invertibility of ( Σq ) using only Y u . Thus, using the inversion algorithm of [START_REF] Silverman | Inversion of multivariable linear systems[END_REF], we can express the input of a such system i.e. w q in function of its state xq and its output components Y u and their derivatives. Thus, we have that there exist, generically, a matrix G, a function ϕ and an integer ν ≤ n q such that w q = ϕ(Y u , Ẏu , . . . , Y

u )+Gx q , where Y u (ν) = (y

(ν) i1 , y (ν) i2 , . . . , y (ν)
i k ) T . △ Substituting this in Equations (3) for mode q, we have:

         ẋq = ( Āλ q + Bλ q G)x q + Bλ q ϕ(Y u , Ẏu , . . . , Y (ν) u ) def = Ãx q + ϕ x (Y u , Ẏu , . . . , Y (ν) u ) y = Cλ q xq + Dλ q G)x q + Dλ q ϕ(Y u , Ẏu , . . . , Y (ν) u ) def = C xq + ϕ y (Y u , Ẏu , . . . , Y (ν) u ) (4
) Remark: To avoid heavy notations, even if function ϕ and matrices G, Ã and C depend on parameters λ i and on mode q, we omit to write superscript λ and subscript q on each of them.

Location observability analysis

Using the previous settings and definitions, we enounce the first result of the paper. It characterizes a sufficient condition for the existence of an algebraic equation depending on a specific mode to ensure mode distinguishability. Proposition 1. SSLS (Σ Λ ), with two possible modes q ∈ {1, 2}, associated to digraph G(Σ Λ ) is generically location observable if for some q ∈ {1, 2}, there exists a direct S o q V or,q , Y -Y path included in E 0 ∪ E q and containing at least one edge of E q .

Proof: Consider that this condition is satisfied and let denote by v i the vertex of S o q V or,q , Y from which there is a direct S o q V or,q , Y -Y path P included in E 0 ∪ E q and containing at least an edge e κ of E q . Let us denote by λ κ the non-zero parameter (or weight) associated to e κ . Let y j be the end of P and ℓ its length. Since v i belongs to S o q V or,q , Y , it exists a subset Y or = {y i1 , y i2 , . . . , y i k } ⊂ Y \ {y j } such that ρ q S o V or,q , Y], Y or = card(S o q V or,q , Y ) without using edges and vertices of P . Thus, as it is shown in Lemma 1, there exist a matrix G, a function ϕ and an integer ν ≤ n q such that the dynamics equation of subsystem ( Σq ) is in the form (4). Since the elements of G are represented by edges belonging to the Y or -topped paths, they are independent from the elements of Ã. From the characteristic equation of matrix Ã, we can write an equation as

C j Ãn1 + . . . + a k Cj Ãk + . . . + a 0 Cj à X = 0 (5)
where also Cj is the line of matrix C related to output y j in mode q in (4) i.e. y j = Cj X + ϕ y,j (Y or , Ẏor , . . . , Y

or ) and so, Cj Ãk

1,1 X = y (k) j -Cj ϕ (k-1) x (Y or , Ẏor , . . . , Y or (ν) ) + Ã1,1 ϕ (k-2) x (Y or , Ẏor , . . . , Y or (ν) ) + . . . + Ãk-2 1,1 φx (Y or , Ẏor , . . . , Y or (ν) ) -ϕ (k) y,j (Y or , Ẏor , . . . , Y (ν)
or ). Since there exists a path of length ℓ from v i to y j containing an edge e κ , term

C j Ãℓ-1 1,1 ϕ (k-ℓ) x (Y or , Ẏor , . . . , Y or (ν)
), for all k ≥ ℓ, is not zero and depends on the element of A q denoted previously λ κ which is specific to location q. In particular, first term Cj Ãn1 , which is present in relation ( 5) is not zero and depends on λ κ . Thus, equation ( 5) leads to an algebraic equation Ψ q (Y, Ẏ , . . . , Y (s) ) = 0 parameterized by at least an element of A q and so satisfied only when mode q occurs. So, the system is location observable. △

Comments and interpretation: To establish location observability, we must first search in the graph the edges, called specific edges, which are specific to one mode. Next, we interest to the position of these edges w.r.t. the output vertices in order to analyse if it is possible to obtain an algebraic equation specific to a mode. If a specific edge belongs to any S o q V or,q , Y -Y path then the mode distinguishability is possible. Note that the condition of Proposition 1 generalizes the condition [START_REF] Santis | Observability of internal variables in interconnected switching systems[END_REF][START_REF] Santis | Observability and detectability of linear switching systems: A structural approach[END_REF] of location observability for non autonomous systems, where the inputs are measured (∃i ≥ 0 such that

C λ (1)(A λ ) i (1)B λ (1) = C λ (2)(A λ ) i (2)B λ (2)
). Note that if there exists an equation characterising mode q, then the one characterizing mode q ′ = q cannot be satisfied by mode q. So, both the conditions of Definition 1 are satisfied and we can rule out mode q ′ when observing output related to mode q and also mode q when observing output related to mode q ′ . Using definition of [START_REF] Babaali | Observability of switched linear systems in continuous time[END_REF], this means, that the two modes q and q ′ are mutually discernible. Exemple 1 Let us see if it is possible to find a specific equation characterizing mode 1. Recall that S o 1 V or,1 , Y = {x 2 , x 8 }. Furthermore, there is one edge (x 2 , x 1 ) which is specific to mode 1 and which belongs to a S o 1 V or,1 , Y -Y path. So, condition of Proposition 1 is satisfied and the system is generically location observable. Indeed, this graphic condition characterizes algebraic relation ẏ1 λ9λ13 -ẏ2 λ5λ14 = 0 depending on λ 9 which is specific to mode 1 only. This relation is not satisfied for mode 2 because, in this case ẏ1 is identically zero. Thus, relation ẏ1 = 0 is specific to mode 2 even if there is no specific coefficient to mode 2 which appears.

Additional sensor location to recover the mode distinguishability

The aim of this part of the paper is to study additional sensor placement when the condition of Proposition 1 is not satisfied.

In the sequel, we define a new output vector Υ representing the additional sensors which collect the new measurements Υ(t) = H λ x x(t) + H λ u u(t) independently from the mode, for practical consistency. Hence, we denote the completed system by Σ c Λ :

Σ c Λ :    ẋ(t) = A λ (r t )x(t) + B λ (r t )u(t) y(t) = C λ (r t )x(t) + D λ (r t )u(t) Υ(t) = H λ x x(t) + H λ u u(t)
The additional sensor components can be represented by vertex set Υ and edge subsets H x -edges and H u -edges from respectively X to Υ and U to Υ. Proposition 1. Consider SSLS (Σ Λ ), with two possible modes q ∈ {1, 2}, associated to digraph G(Σ Λ ). Let denote by V s (q) = {v ∈ V, v is the begin vertex of an edge belonging to E q }. To recover the sufficient condition of Proposition q∈{1, 2}

V ess,q V or,q , Y ∩ {v i such that ∃ a simple v i -Y path covering an element of V s (q)} Proof: Assume that we place an additional sensor on a vertex which is included in q∈{1, 2}

V ess,q V or,q , Y ∩{v i such that ∃ a simple v i -Y path covering an element of V s (q)} .

Since this vertex denoted v i belongs to V ess,q V or,q , Y and since it will exist a new path from it to an output vertex (the additional sensor) then v i will be included in the output separator set of the extended system i.e. v i ∈ S o q V or,q , Y ∪ Υ . Moreover, the fact that there exists a simple v i -Y path covering an element of V s (q) means that there exists a direct S o q V or,q , Y ∪ Υ -Y ∪ Υ path included in E 0 ∪ E q and containing at least one edge of E q . Therefore, completed system (Σ c Λ ) satisfies condition of Proposition 1 and the Proposition 1 follows. △ , Y -Y paths have a zero length and so condition of Proposition 1 is not satisfied. For mode 1, only x 4 is a vertex which begins specific edge and so V s (1) = {x 1 }. For mode 2, V s (1) = {x 2 }. Therefore, an additional sensor in Υ = {x 4 , x 2 , x 3 } allows to ensure the location observability property.

Computational issues

The conditions of Proposition 1 need few information about the system. Moreover, it is quite easy to check it by means of wellknown combinatorial techniques. Indeed, from a computational point of view, the first step of our procedure requires the calculation of the strongly connected components which can be done using an algorithm which complexity order equals O(N log(N )) = O(nlog(n)) [START_REF] Fleischer | On Identifying Strongly Connected Components in Parallel[END_REF], where N = n + m + p the number of vertices of our graphs. Note that, without loss of generality, M = O(n 2 ). After finding the strongly components, we must order these components simply by comparison to find the minimal elements with a O(n 2 ) complexity order algorithm. The third step is the computation of the output separator between the maximal strongly connected components and the output sets. It is based on the Ford-Fulkerson algorithm which must be executed n+p times and so the complexity order for this step is n × O(n 3 ) = O(n 4 ). To check the location observability condition or to compute the possible additional sensors' locations, we must find all the vertices belonging to direct S o q V or,q , Y -Y paths and extract those which are the begin vertices of specific edges. This is done by successor and predecessor computation algorithms, which have O(n 2 ) complexity order. Therefore, without any simplification, the complexity order of algorithms using this method is, in the worst case, O(n 4 ). The fact that the overall complexity order is not exponential makes the proposed method suited to deal with large scale systems. Obviously, some researches can be done in order to lower the overall order complexity by reducing the graph for example or subdividing it, but it is not the aim of the paper.

Generalization to multi-mode case

Since state and input observability of each mode has to be studied separately, the main difficulty is to generalize location observability criterion and more precisely the matrix decomposition related to each mode into two parts: a common one and a specific one.

Consider SSLS (Σ Λ ) defined in Equation [START_REF] Babaali | On the observability of piecewise linear systems[END_REF], where Q def = {1, 2, . . . , N }. We take the following notations: for q ∈ {1, 2, . . . , N }, q ′ ∈ {1, 2, . . . , N } with q = q ′ , A λ (q) = A λ q,q ′ + A λ q,q ′ , where A λ q,q ′ = A λ q ′ ,q denotes the common part between A λ (q) and A λ (q ′ ) and A λ q,q ′ represent the specific part of A λ (q) relatively to A λ (q ′ ). Similarly, B λ (q) = B λ q,q ′ +B λ q,q ′ , C λ (q) = C λ q,q ′ + C λ q,q ′ and D λ (q) = D λ q,q ′ + D λ q,q ′ . We have multiple decompositions for matrices A λ (q), B λ (q), C λ (q) and D λ (q) useful only in location observability study. To each of these matrices, we associate, as in Section 3, an edge subset. Thus, we state: Proposition 2. SSLS (Σ Λ ) with N modes associated to digraph G(Σ Λ ) is generically location observable if for each pair q ∈ {1, 2, . . . , N }, q ′ ∈ {1, 2, . . . , N } with q = q ′ , Proposition 1 is satisfied by substituting edge subsets E 0 by A q,q ′ -edges ∪ B q,q ′ -edges ∪ C q,q ′ -edges ∪ D q,q ′ -edges, E 1 by E q,q ′ = A q,q ′ -edges∪B q,q ′ -edges∪C q,q ′ -edges∪D q,q ′ -edges and E 2 by E q ′ ,q = A q ′ ,q -edges ∪ B q ′ ,q -edges ∪ C q ′ ,q -edges ∪ D q ′ ,q -edges.

Proof: The proof is quite immediate starting from Proposition 1 and considering that the location observability in multimode case is equivalent to the distinguishability of each pair of modes. △

In the multi-mode case, concerning the additional sensors placement, we generalize the results of Proposition 1: Proposition 3. Consider a multi-mode SSLS (Σ Λ ) with N modes associated to digraph G(Σ Λ ). For each, q ∈ {1, 2, . . . , N }, q ′ ∈ {1, 2, . . . , N } with q = q ′ , let denote by V s (q, q ′ ) = v ∈ V, v is the begin vertex of an edge belonging to E q,q ′ and V s (q ′ , q) = {v ∈ V, v is the begin vertex of an edge belonging to E q ′ ,q }. To recover the sufficient condition of Proposition 2, the additional sensors Υ must measure at least one component in each subset Sens q,q ′ , q ∈ {1, 2, . . . , N }, q ′ ∈ {1, 2, . . . , N } with q = q ′ defined by: Sens q,q ′ = V ess,q V or,q , Y ∩ {v i s.t. ∃ a simple v i -Ypath, covering an element of V s (q, q ′ ) ∪

V ess,q ′ V or,q ′ , Y ∩ {v i s.t. ∃ a simple v i -Y path covering an element of V s (q ′ , q)} Proof: From Proposition 1, taking a measure on each set Sens q,q ′ guarantees the distinguishability of modes q and q ′ . Thus, the location observability, which is equivalent to the distinguishability of all the pairs q ∈ {1, 2, . . . , N }, q ′ ∈ {1, 2, . . . , N } with q = q ′ is ensured by measuring one component in each subset Sens q,q ′ , q ∈ {1, 2, . . . , N }, q ′ ∈ {1, 2, . . . , N } with q = q ′ .

CONCLUSION

In this paper, we propose a graph-theoretic tool to analyze generic mode location observability for switching structured linear systems with unknown inputs. At first, we provide a simple but not trivial sufficient condition to ensure the generic location observability of switching structured linear systems. Next, when this observability condition is not satisfied, we study the location of additional sensors in order to recover the generic location observability. This problem has not been solved previously in the literature. It is shown also that our approach uses classical programming techniques and is free from numerical difficulties since it uses well-known combinatorial techniques. Indeed, all the algorithms used in the paper have polynomial complexity orders. This makes our proposed method well-suited to large scale systems.

In future works, we will interest to complete this study by providing quite simple necessary and sufficient location observability conditions and also a more complete procedure recovering this property when it is not achieved. We will interest also in coupling the presented approach based on a structural criterion (here the location observability) with reliability indicators and economic cost functions to propose a global strategy to design large scale systems.

Figure 1 .

 1 Figure 1. Digraph associated to system of Example 1

Example 2 .Figure 2 . 2 {u 1 , x 3 , x 4 }

 222134 Figure 2. Digraph associated to system of Example 2{u 1 , x 3 , x 4 } and so S o 1 V or,1 , Y = S o 2 V or,1 , Y = {y 1 , y 2 , y 3 }. Thus, all the direct S o 1 V or,1, Y -Y paths have a zero length and so condition of Proposition 1 is not satisfied. For mode 1, only x 4 is a vertex which begins specific edge and so V s (1) = {x 1 }. For mode 2, V s (1) = {x 2 }. Therefore, an additional sensor in Υ = {x 4 , x 2 , x 3 } allows to ensure the location observability property.

  Example 1, the 1-scc are: {u 1 }, {x 1 }, {x 2 , x 3 }, {x 4 }, {x 5 }, {x 6 }, {x 7 }, {x 8 }, {y 1 }, {y 2 }, {y 3 }, {y 4 }. The maximal ones are {u 1 } and {x 2 , x 3 } and so V or,1