Renzo Stanley
email: rstanley@inf.utfsm.cl

Hernán Astudillo

Víctor Codocedo
email: victor.codocedo@loria.fr

Amedeo Napoli
email: amedeo.napoli@loria.fr

A Conceptual-KDD approach and its application to cultural heritage

Keywords: Formal concept analysis, Knowledge discovery in databases, Conceptual knowledge discovery, Intangible Cultural Heritage, Documentation

Several governmental and non-governmental organizations (NGOs), motivated by the UNESCO have undertaken the task of documenting the intangible cultural heritage of their communities. However, this has proven to be a difficult task. In this work we present a conceptual knowledge discovery in databases (CKDD) approach to aid a particular organization in this task (which has already started). Because of the dynamism of the cultural heritage domain, the design of the database used to store the documentation data has become obsolete. We propose to redesign the database (actually, its schema) to unveil independent modules of information collaboratively created by different domain experts. Finally, we present a straightforward method to convert the redesigned data schema into an ontological model which can be used for integration and publication purposes.

Introduction

The Chilean National Council of Culture and Arts1 (CNCA) has undergone the mission of documenting the intangible cultural heritage (ICH) of different small zones of the country in the context of a world-wide UNESCO2 crusade to incentivize governments and NGOs to properly maintain our cultural knowledge. The ICH, as drafted in the Convention for the Safeguarding of the Intangible Cultural Heritage3 refers to "traditions or living expressions inherited from our ancestors and passed on to our descendants, such as oral traditions, performing arts, social practices, rituals, festive events, knowledge and practices concerning nature and the universe or the knowledge and skills to produce traditional crafts".

To survey the ICH, the CNCA maintains several "documenters" who meet artists, artisans and other actors of the folkloric stage. Each documenter fills a "file" containing several semi-structured and text-free fields which are later registered in a relational database (DB). This database is later consulted by curators (usually domain experts) who fix problems in data definitions or storage. The CNCA has requested help in two specific aspects. Given the difficulty of documenting very different domains in ICH, the design of a data schema to support its documentation is a hard task which leads to inconsistencies in its model. Currently, the data schema used by the CNCA was designed by a computer engineer with some knowledge on the domain. However, as the ICH documentation process expanded to other cultural domains ("music", "folk festivals", "crafts", etc.) the data schema became too general and some modifications were requested to enable a higher level of details. The CNCA requested to analyse the data schema in order to find "modular" partitions on the model corresponding to different domains in ICH. Thus, each module can be maintained by a related domain-expert avoiding the risk of information conflict.

The second request derives from the fact that, since the ICH documentation is a multi-organizational endeavour motivated by UNESCO, it is expected that data collected by CNCA will be integrated with other databases later on. Because of this, CNCA has asked aid to obtain an ontological schema from its current data schema which can be used for linked data publication.

In this work we propose a novel knowledge discovery in databases process guided by formal concept analysis (also, referred to as conceptual knowledge discovery in databases CKDD [START_REF] Hereth Correia | Conceptual knowledge discovery-a human-centered approach[END_REF]) approach to deal with both requirements. We analyse the current data schema definition to construct a concept lattice through FCA in which we apply different techniques to find the modules representing ICH domains. The contributions of this work are firstly, to present a real-world experience using FCA and concept lattices to achieve a task as important as heritage documentation and secondly, the description of a process to elicit an ontological schema from a relational DB schema which can be of benefit in different applications.

The remainder of this article is organised as follows: Section 2 presents the CKDD process while Sections 3, 4 and 5 detail each of its steps. Section 6 describes the case study of applying the CKDD process over the CNCA database for ICH documentation. Finally, Section 7 presents a discussion on related work and concludes the paper.

2 Formal concept analysis and knowledge discovery in databases.

We propose an iterative and human-centred approach to overcome both requirements of the CNCA based on Conceptual Knowledge Discovery in Databases (CKDD) [START_REF] Hereth Correia | Conceptual knowledge discovery-a human-centered approach[END_REF]. CKDD is a tool to support humans in the discovery and extraction of knowledge from large collections of data where the conceptual representation of knowledge is a key aspect [START_REF] Wille | Why can concept lattices support knowledge discovery in databases[END_REF]. Fig. 1: FCA-based KDD process for CNCA Figure 1 presents a 3-step CKDD process designed to take a database schema and convert it into a knowledge base. The process contains a loop between the interpretation and the FCA step in which domain expert knowledge is included. Notice that to avoid conflicts with the CNCA data, we only extract information from the database and never modify it. In the following sections we provide a detailed description of each step and sub-tasks developed.

First Step of the CKKD process: Data preprocessing

The first step starts by extracting the database schema and ends when it is converted to a formal context. Currently, most of the relational database management systems are based on the relational model constituted by tables and their relations (there are actually more elements in a relational model which are not of first interest here). We provide an adapted definition of the relational schema model as described in [START_REF] Ramez | Fundamentals of Database Systems[END_REF].

Relational data schema model

A relational schema S = {R 1 , R 2 , ..., R |S| } is defined as a set of tables or "relation schemas" R i (A 1 , A 2 , ..., A ni ) consisting of a table name R i and a list of n i fields A j which define value assignments of the domain dom(A j ) to an entry in the table. The notation R i .A j stands for the field A j in table R i . An entry in a table is defined as an ordered n-tuple of values denoted by t[R i ] =< v 1 , v 2 , ..., v ni > where each value is denoted as t[A j ] = v j ∈ dom(A j ) ∪ {N U LL}. N U LL indicates that the value is unknown for the field in the entry. The relation state r(R i ) = {t 1 , t 2 , ..., t ri } of table R i denotes its total set of entries. In a table R i , the set of fields SK ⊂ R i denotes a superkey which identifies a tuple as unique. A primary key P K is defined as a superkey where |SK| = 1 and |.| denotes set cardinality, i.e. P K is a single field and we say that R i .P K is the primary key of table R i the value of which unequivocally identifies an entry in table

R i . Finally, a field R 1 .F K is called a foreign key iff R 1 .F K = R 2 .P K which indicates a re- lation between R 1 and R 2 .
In the particular case of the CNCA database for ICH documentation, a notion of inheritance of tables is supported. We define this as

!"#$%& !"#$%&'(& )*(#'*+,&)& ,$-.%)/*'"& 01/'&& '$+&& $"")&22& &+$!3& '())#*+,#&!"#$%& &2($,3!21+&'(& %&'"&)#-/+0/2!4/'& -$./,/.01)&!"#$%& ,!)(1"$5& %&'"&)& 2#3+,#64,#$%& !"#7&2(& '$+&& "&2-)!04/'& ,$-.%)/*'"& 8!&92& "*)$4/'& !"#$%&'(& 5/%01)& !"#)!(*$3& '$+&& "&2-)!04/'& 8!&92& 03$-&& !"#$%&'(&
: table R 1 inherits from table R 2 iff R 2 ⊂ R 1 and R 1 .P K = R 2 .P K, i.e.

Formal context definition

Considering data schema S = {R 1 , R 2 , ..., R |S| } and the tables of the form R i (A 1 , A 2 , ..., A ni ) composed by the fields A j , we define the formal context K = (S, A, I) where

A = Ri∈S R i .A j I = {(R i , A j ) / ∀R i ∈ S, ∀A j ∈ R i }
Formal context K is composed by tables in the set S (all the tables or a sub-set of them), the set of fields A (composed by the set of all fields from all tables considered in S) and the relation set I (the relations between tables in S and their fields in A). Notice that we define a formal context by making the correspondences object-table and attribute-field. To avoid confusions, in this work we differentiate between these correspondences by using different font faces for objects or attributes and for tables or fields. Along with the formal context, we also define the following rules of attribute integration based on the characteristics of the fields:

-The special attribute id represents all primary keys: id ∈ A , (R i , id) ∈ I ∀R i ∈ S. -Fields with the same name are integrated into a single attribute (e.g. attribute name represents Agent.name and Ritual .name)

Relational attribute scaling

In the context of FCA, foreign keys correspond to relational attributes. For example, in Figure 2 we do not say "table Ritual contains a foreign key" (as in the case of Ritual contains a primary key), but rather "Ritual is related to Agent by a foreign key". Such kind of attributes cannot be included in a binary formal context. To deal with relational attributes, we scale them and treat them as normal attributes in the lines of [START_REF] Rouane-Hacene | A proposal for combining Formal Concept Analysis and description Logics for mining relational data[END_REF]. We do so by prepending the prefix related to: to the name of the table where the foreign key directs to (e.g. in the formal context in Table 1, we say that the object Ritual contains the attribute related to:Agent). This is formalized as This step receives a formal context and ends when a concept lattice is constructed. Figure 3(a) shows the concept lattice calculated for the formal context in Table 1. Along with the concept lattice, the original formal context is sent to step 3 to allow modifications in it for further iterations of the process. We develop two tasks related to the identification of elements which would help in the redesign of the data schema.

R j .F K = R i .P K; R i , R j ∈ S ⇒ related to:R i ∈ A ∧ (R j ,
× × × × × × × IndividualAgent × × × × × × × × × CollectiveAgent × × × × × × × × × FestiveEvent × × × × × × × Ritual × × × × × ×

Attribute concept identification

The attribute concept of attribute A j is defined by µA j = (A ′ j , A ′′ j ), where () ′ is the derivation operator in FCA [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF]. The identification of attribute concepts is rather simple and we do it by navigating from the top to the bottom of the lattice. Attribute concepts are the most general concepts in the lattice containing a given attribute. In our case, the attribute concept of a given field contains the largest set of tables related to it. This is important since, as we will describe in the next step of interpretation, we process each field separately in order to create the ontological schema. Attribute concepts make this simpler as for each field we only need one concept and not the whole lattice.

Extensional stability calculation:

Since we are looking to enhance the design of a data schema in the database, within the lattice we would like to have only those concepts which group together in their extents tables of the same domain. This would allow us to address the modularization of information per domain issue which is one of the request of the CNCA, assuming that tables in the same domain are likely to share similar fields. In order to do so, we use the notion of extensional stability as firstly described in [START_REF] Kuznetsov | On stability of a formal concept[END_REF] and later in [START_REF] Roth | Towards concise representation for taxonomies of epistemic communities[END_REF] as a way to measure "the probability of a concept to preserve its extent after leaving out an arbitrary number of attributes".

Third Step of the CKDD process: Interpretation

The final step receives a formal context and its associated concept lattice where each attribute concept is identified and each formal concept contains an extensional stability value. Since CKDD is an iterative process, this step has two possible outputs. If the expert decides to make another iteration, the process goes back to step 2 sending a modified version of the formal context received including feedback of the expert. If the expert decides to end the process, this will create an "ontological schema" which will be stored in a knowledge base and the process ends. For the iteration, there are two tasks to perform: Question creation/answering and Modularization. The task which transforms the concept lattice into an ontological schema ends the process. A further step of annotation which converts the entries in tables into linked data using the ontological schema can be considered, but for the sake of space we have left it out of this paper.

Question creation and answering

We use extensional stability as an indicator of how related are tables within a given concept extent. A lower stability indicates that those tables are grouped more as an accident (for example, because of the misuse of a single (or several) field name(s)) rather than because they belong to the same domain. We look for unstable attribute concepts because they are the most general concepts containing a given attribute, so they are those that relate more tables together. Moreover, we can create questions for the expert to answer in the hope they provide information to "break" the attribute concept and separate domains.

Consider the example in Figure 3(a) in which two domains are illustrated. The first relates events while the second relates people and communities. The most unstable attribute concepts (extensional stability of 0.5) correspond to those labelled with the attributes background and place. In the case of place, it only contains one table meaning that "breaking" this concept does not help in separating domains 4 . The attribute concept of background contains four objects, namely FestiveEvent, Agent, IndividualAgent and CollectiveAgent for which FestiveEvent belongs to a different domain than the others.

Regarding the questions posed to the expert, we have:

1. Would you like to assign attribute to all the objects? 2. Would you like to eliminate the attribute from a single/a set of objects/s? 3. Would you like to split attribute into different attributes for different objects?

If the expert selects option 1, the attribute will be shared by every object and hence, it will be placed as part of the intent of the top of the lattice (like id and name in Figure 3(a)). In the case of option 2, the attribute is erased from the formal context and hence, its attribute concept is removed. With option 3, we can recommend the partition of the attribute by looking at the sub-concepts of the attribute concept. Then, a new attribute is created for each partition made while the original attribute disappears. Consider A i to be the attribute for which the expert has to answer a question. For each option we can define a new formal context as follows:

1. Option 1: K A = (S, A, I ∪ {(R, A i ); ∀R ∈ S}) 2. Option 2: K A = (S, A\{A i }, I\{(R, A i ; )∀R ∈ S}) 3. Option 3: Let A j be the splits of attribute A i assigned to objects R j , then

K A = (S, (A\{A i }) ∪ A j , I\{(R, A i ); ∀R ∈ S} ∪ {(R j , A j )})
In the example, the expert selected option 3 splitting background into an attribute for FestiveEvent (practice background) and another for the Agents (records). This example is actually an extract of a real case study where the expert realized that the term "background" was used with multiple meanings and that it should be separated into an attribute registering the history of past events and another for the official records of people. Figure 3(b) presents the concept lattice created from the formal context yielded by this decision.

Modularization

The expert may choose to perform this task disregarding answering questions. We start from the already processed concept lattice L and find its sublattices such as L i ∩ L j = {⊤, ⊥} where L i , L j are sublattices of L and ⊤, ⊥ represent the top and the bottom of L respectively. We achieve this by obtaining the connected graphs from the lattice once ⊤ and ⊥ are removed. Each sublattice is a candidate to represent a domain which must be labelled by the expert. The label is included into the formal context as a special attribute of the form domain:Label with relations to all the objects in the sublattice. The concept lattice is later recalculated. Figure 3(b) depicts the final form of the lattice for the running example. Finally, the expert may also be interested in merging more than one sublattice into a single domain. In that case, the special attribute is added to all objects in the set of sublattices selected by the expert.

Ontological schema creation

The final task of the process derives an ontological model from the concept lattice that can be used for data integration and linked data publication. This is done Table 2: Formal concept translation into RDF triples. Triples in the third column are created for the elements described in the second column within the formal concepts in the first column by creating a set of RDF triples5 for given elements in the formal concepts of the lattice. Table 2 shows this conversion where for example, in the first row it is shown that for the top concept, all the tables in its extent are modelled as RDFS classes6 [START_REF] Mcbride | The resource description framework (rdf) and its vocabulary description language rdfs[END_REF]. For simplicity purposes, Table 2 only presents a part of the total set of triples created considering the top ⊤, the bottom ⊥ and attribute µA j concepts.

Case study: CNCA Intangible Cultural Heritage Database

The database schema of the CNCA for ICH documentation consists of nearly 300 tables, however only 27 tables were selected by the experts on the basis of their representative and multi-disciplinary knowledge. Selected tables consider descriptions of agents, collective agents, festive events, culinary manifestations, geolocations and more. The formal context derived from the database contains 27 objects, 56 attributes, and 25 relational attributes. Figure 4 depicts the concept lattice built from this formal context. Table 3: Iterations made for the case study Table 3 shows the actions taken by the domain expert during 9 iterations of the CKDD process. We distinguished between facts, questions and actions. Facts represent database assertions which are displayed for helping the expert in decision taking. For example, in iteration 1 the expert is presented with the facts: "71% of the objects contain the attribute name" and "The attribute name has a value in 100% of the entries in the objects where it appears". The first fact helps the expert to understand that name is actually very common among the objects and can easily be extended to the whole object set. The second fact combines information from the DB and the concept lattice to tell the expert that in all the entries t which contain the field name (represented by the attribute name), the value t[name] is different than N U LL. This indicates him that the attribute should not be removed from any object. Questions and actions were already detailed in Section 5.1.

In iterations 3 and 4 the expert split the attribute background ("antecedentes" in Spanish). This attribute appears in several objects (46% of object set) through all the domains, however with different semantics. Finally, the expert created the attributes historical background, records, practice background and culinary background. In iteration 5 and 6, the expert decided to eliminate some attributes from the object set. For example, the relation related to:Commune which represented a foreign key in the database, was not being used in 3 tables from which it was removed. Finally, in iterations 7, 8 and 9 the expert labelled the modules as subdomains of ICH FestiveFeatures, Geo and AgentFeatures. Modelling semantic relations in DBs is proposed in [START_REF] Priss | Efficient implementation of semantic relations in lexical databases[END_REF] where the author presents a framework to formalize semantics in a lexical database. A lexical database maintains information about concepts and their semantic position w.r.t. each other (hypernymy or meronymy). In general, relational DBs do not share the same characteristics nor structure as lexical databases, allowing to store more heterogeneous data. In [START_REF] Priss | Establishing connections between formal concept analysis and relational databases[END_REF] the same author proposes an algebra for relational DBs which can be interpreted also in terms of a formal context in FCA. A similar idea was proposed by [START_REF] Hereth | Relational scaling and databases[END_REF] where the author uses the algebra to translate a relational database into a family of formal contexts to benefit from both, the simplicity of the relational model description and the power of FCA in analysis. By contrast, our approach is more straightforward since we are not interested in data operations using the concept lattice, but rather in a direct translation of the data schema. Thus, we do not work with the entries in the tables of the database. In our approach we use the concept lattice as a support for guiding the redesign process in which a domain expert is the main provider of knowledge.

To conclude, in this article we have presented an application of a conceptual knowledge discovery in databases process designed to redesign and convert a database schema into an ontological model. The process is heavily human centred as it considers a domain expert as the main source of knowledge to guide the process. To support him, we use formal concept analysis with a formal context created from the set of tables and fields extracted from the database schema. The concept lattice calculated from this formal context is used to analyse the schema and create questions which the user should answer. Each question has an associated set of actions aimed at redesigning the database schema model.

The application is implemented over an excerpt of the Chilean National Council of Culture and Arts (CNCA) database for intangible cultural heritage documentation. Currently, we are implementing the process in full scale including more domain experts. Future work include the annotation process of data using the ontological schema created which has already been considered, however not described in this article. As pointed out by one of the reviewers of this work, the approach presented in this article may also be applied in the context of software engineering, specifically in code re-factoring and object-model re-engineering [START_REF] Godin | Formal concept analysis-based class hierarchy design in object-oriented software development[END_REF].

Fig. 2 :

 2 Fig. 2: Data schema example from the ICH domain

  (a) Concept lattice created from the data schema example (b) Concept lattice after the expert's decision (attribute background split into practice background and records) including domain labels

Fig. 3 :

 3 Fig. 3: Concept lattices for CNCA (before and after the expert's decision)

Fig. 4 :

 4 Fig. 4: Concept lattice from the ICH database schemaIteration Attribute Action 1 name Assign to all tables 2 description Assign to all tables 3 background Split the attribute 4 background Split the attribute 5 related to:Commune Eliminate from some tables 6 related to:Localization Eliminate from some tables 7 -Domain labelling 8 -Domain labelling 9 -Domain labelling

Figure 5

 5 illustrates the final concept lattice presenting the different subdomains identified from left to right, namely; Agent descriptors subdomain, Festive Event descriptors subdomain, Culinary descriptors subdomain, Geographical subdomain, Content creators subdomain, Photo subdomain, ICH subdomain. The last subdomain includes all the manifestations about ICH in this database schema.

Fig. 5 :

 5 Fig. 5: Concept lattice after 9 iterations

table R 1

 R contains all the fields in table R 2 and they share the same primary key. Figure2illustrates a data schema example S = {Festive Event, Ritual , Agent, Individual Agent, Collective Agent} where arrows represent relation between two tables and a line with a rhombus at the end represents inheritance. Table Ritual can be represented as Ritual(id ritual, name, description, views, place, id agent) where dom(name) = string, Ritual.id ritual is the primary key of table Ritual and Ritual.id agent is a foreign key relating Ritual with Agent. The example also shows that Individual Agent and Collective Agent inherit from table Agent, meaning that all the attributes from table Agent are also present in tables Individual Agent and Collective Agent.

  In the case the table R i pointed to by a foreign key do not exist in S, then we simply do not take into consideration that table nor we create the scaled relation related to:R i .

	id	rut number	email	phone	name	address	background	description	views	place	related to:Agent	birthday	gender	establishment	gender composition	duration
	Agent

related to:R i ) ∈ I

Table 1 :

 1 Formal context created from the data schema example 4 Second Step of the CKDD process: Formal Concept Analysis

http://www.consejodelacultura.cl

United nations educational, scientific and cultural organization.

http://en.wikipedia.org/wiki/Convention_for_the_Safeguarding_of_ Intangible_Cultural_Heritage

A low stability in a singled-object attribute concept may indicate that the table should be split in two or more different tables. We do not address this issue in this work

Resource Description Framework (RDF) is a standard specification for semantic web and linked data based on triples http://www.w3.org/RDF/.

Resource Description Framework Schema (RDFS) is an extension of RDF which supports classes, properties and more complex definitions.


Víctor Codocedo
email: victor.codocedo@loria.fr

Ioanna Lykourentzou
email: ioanna.lykourentzou@tudor.lu

Hernán Astudillo

Amedeo Napoli
email: amedeo.napoli@loria.fr

Using pattern structures to support information retrieval with Formal Concept Analysis

Keywords: Formal Concept Analysis, Interval Pattern Mining, Information Retrieval

In this paper we introduce a novel approach to information retrieval (IR) based on Formal Concept Analysis (FCA). The use of concept lattices to support the task of document retrieval in IR has proven effective since they allow querying in the space of terms modelled by concept intents and navigation in the space of documents modelled by concept extents. However, current approaches use binary representations to illustrate the relations between documents and terms ("document D contains term T") and disregard useful information present in document corpora ("document D contains X references to term T"). We propose using pattern structures, an extension of FCA on multi-valued and numerical data, to address the above. Given a set of weighted document-term relations, a concept lattice based on pattern structures is built and explored to find documents satisfying a given user query. We present the meaning and capabilities of this approach, as well as results of its application over a classic IR document corpus.

Introduction

Information retrieval (IR), is a problem of lasting interest for the research community. Among the tasks comprising the IR domain, document retrieval (i.e. the search and ranking of documents that are relevant to an original user query from a given document corpus) is one of the most popular in the field given its importance in everyday routines. In the wide spectrum of techniques applied to support document retrieval, formal concept analysis (FCA) has gained interest in the last years [START_REF] Carpineto | Exploiting the potential of concept lattices for information retrieval with CREDO[END_REF][START_REF] Carpineto | Using Concept Lattices for Text Retrieval and Mining[END_REF][START_REF] Codocedo | Semantic querying of data guided by Formal Concept Analysis[END_REF][START_REF] Ferré | Camelis: a logical information system to organise and browse a collection of documents[END_REF][START_REF] Priss | Lattice-based Information Retrieval[END_REF] because of its robust framework and the qualities of a concept lattice.

Formal concept analysis (FCA) is a mathematical formalism used for data analysis and classification, which relies on the dualistic understanding of concepts as consisting of an extent (the objects that belong to the concept) and an intent (the attributes that those objects share) organized in a lattice structure called a concept lattice [START_REF] Ganter | Pattern Structures and their projections[END_REF]. We refer to FCA-based information retrieval as CL4IR which stands for"concept lattices for information retrieval".

In a typical CL4IR approach, a binary table of documents and terms is created and then, using FCA algorithms, the respective concept lattice is created. This lattice contains several formal concepts, each defined by a set of documents (extent) and the set of terms that they share (intent). Thus, the lattice provides a multiple hierarchical classification of documents and terms which can be navigated and searched as an index, to retrieve concepts that are "close" or "similar" to the original query concept. In this way a CL4IR system exploits the connections of concepts within the lattice to find relevant documents for a given query and takes advantage of the lattice structure to enrich the answer in different ways: by navigating the lattice to look for approximate answers through generalizations and specifications of the original query concept's intent [START_REF] Carpineto | Order theoretical ranking[END_REF][START_REF] Messai | Querying a bioinformatic data sources registry with concept lattices[END_REF], by enriching the term vocabulary with a thesaurus [START_REF] Codocedo | Semantic querying of data guided by Formal Concept Analysis[END_REF] or by directly integrating external knowledge sources [START_REF] Priss | Lattice-based Information Retrieval[END_REF]. Nevertheless, current CL4IR systems are restricted by the binary nature of their data (a document can either contain a given term or not). Consequently, they can work only with Boolean-like queries, which is an important limitation w.r.t. other IR approaches such as vector-space ranking methods [START_REF] Manning | Introduction to Information Retrieval[END_REF] that allow partial-matching documents to be considered as possible answers.

In this article we present a novel CL4IR approach, which deals with numerical datasets, i.e. document-term relations, where a document is annotated by a term with a certain weight. This approach provides CL4IR systems with an extended query space, on which vector-space ranking methods can be adapted and applied. In parallel, this approach retains the main advantage of using lattices as the document search index, which is the provision and exploration potential of the complete query space. Our approach is based on the pattern structures framework, an extension of FCA to deal with complex data [START_REF] Ganter | Pattern Structures and their projections[END_REF]. Given a numerical table representing weighted associations between documents and terms, we apply pattern structures to build the extended query space, while we also introduce steps for reducing and simplifying the document search within the constructed query space. We illustrate our approach through running example on a classical IR dataset and by comparing our results, in terms of precision and recall, to those reported in the literature. Furthermore we provide a discussion on the meaning and capabilities of the proposed approach. The remainder of the paper is organized as follows. Section 2 provides an introduction to the use of formal concept analysis for document retrieval. Section 3 describes the pattern structure framework and details the proposed CL4IR approach which can be applied on numerical datasets. Section 4 presents the experiments. Finally, Section 5 concludes the paper.

Concept Lattices for Information Retrieval

The setting of a typical concept lattice for information retrieval (CL4IR) application is given by a formal context K = (D, T, I) made of a set of documents D, set of terms T and an incidence relation

I = {(d i , t j )} indicating that document d i contains term t j .
d1 x x x d2 x x x x x x d3 x x x x d4 x x x d5 x x x d6 x d7 x x d8 x x x d9 x x x q *
x x * Grey row represents the query.

Table 1: A term-document formal context including the query q.

Given a user query q = {t 1 , t 2 ...t |q| } , the document retrieval task consists in returning a set of documents ordered by "relevance" w.r.t. the query q. In CL4IR systems a query can be represented as a virtual document containing the set of terms {t 1 , t 2 ...t |q| }. Then, the query is inserted in the formal context as another object and the incidence relation set I is updated to include the relations of the virtual query-document and its terms. The formal context becomes K q = (D + {q}, T, I + {(q, t i ) i..|q| }).

The standard procedure to find "relevant" documents within the concept lattice consists in identifying the query concept (which is defined as the object concept of the virtual object q and denoted by γ(q) = ((q ′ ) ′ , q ′ )) and concepts related to the query concept (for example, its superconcepts) which can provide further results. We refer to the later concepts as "answer concepts". For the formal context in Table 1, consider the query q with terms "graph" and "tree" (grey row). Figure 1 shows the concept lattice derived from this formal context (including the query). The query concept corresponds to concept 17 and contains in its extent documents d 7 and d 8 which satisfy the query and can be retrieved to the user. The superconcepts of the query concept (concepts 7 and 8) contain documents d 6 and d 9 which can also be retrieved. Different relevance measures can be used to rank the retrieved documents. For example, the topological distance within the lattice between the query concept and the "answer concepts" (i.e. concepts partially satisfying the query) can be calculated and in this case documents d7 and d8 are at distance 0 (more relevant), while d 6 and d 9 are at distance 1 (less relevant). Other such measures include semantic distance, extent intersection, and Jaccard similarity [START_REF] Carpineto | Order theoretical ranking[END_REF][START_REF] Messai | Using Domain Knowledge to Guide Lattice-based Complex Data Exploration[END_REF][START_REF] Codocedo | Semantic querying of data guided by Formal Concept Analysis[END_REF].

More generally, the concept lattice defines a query space where each formal concept C can be considered as a conjunctive Boolean query (i.e. a query where the constraint is given by the conjunction of the attributes in the intent of C) and a combination of formal concepts provides disjunction and negation (e.g. The union of concepts 7 and 8 in Figure 1 satisfies the disjunctive query "graph" or "tree"). Unfortunately, the binary case is the "ideal world". In most real-world datasets the relation between a document and a term is built w.r.t. a measure such as frequency, distance or weight involving a range of numerical values [START_REF] Manning | Introduction to Information Retrieval[END_REF].

A document corpus can be defined as a term-document matrix A = [a ij ], where terms t i ∈ T are in rows, documents d j ∈ D in columns and each cell a ij of the matrix represents the "value" of the term t i in the document d j , given by a function val(d j , t i ) (weight, frequency, etc.). In order to work with this kind of datasets, a CL4IR system can resort to interordinal scaling [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF] by simply assigning an incidence relation when a term in a document has a value within a given range, i.e. I = {(d, t)|val(d, t) > 0}). However, interordinal scaling could greatly increase the complexity for IR tasks [START_REF] Kuznetsov | Pattern Structures for Analyzing Complex Data[END_REF] as it induces redundancy as shown in [START_REF] Kaytoue | Revisiting numerical pattern mining with formal concept analysis[END_REF]. To the best of the authors' knowledge, a CL4IR system directly dealing with a weighted term-document dataset is not yet reported in the FCA nor in IR literature. In the following, we present a method and an implementation of a CL4IR approach dealing with numerical datasets.

CL4IR with many-valued datasets 3.1 Pattern structure framework

Here, we introduce the pattern structure framework firstly described in [START_REF] Ganter | Pattern Structures and their projections[END_REF].

A pattern structure K = (G, (P, ⊓), δ) is a generalization of a formal context. In K, G is a set of objects, (P, ⊓) is a semi-lattice of object descriptions and δ : G → P is a mapping associating a description to an object. The description of an object g ∈ G is a vector of intervals v = [l i , r i ] i∈{1..|M |} , where v ∈ P , l i , r i ∈ R and l i ≤ r i .

In (P, ⊓) the similarity operator ⊓ applied to

v a = [l 1 i , r 1 i ] and v b = [l 2 i , r 2 i ] yields the convex hull v a ⊓ v b = [min(l 1 i , l 2 i ), max(r 1 i , r 2 i )] where i ∈ {1..|M |}. The associated subsumption relation is defined as v a ⊓ v b = v a ⇐⇒ v a ⊑ v b .
A Galois connection between ℘(G) (powerset of G) and (P, ⊓) is defined as follows:

X = g∈X δ(g) ; v = {g ∈ G|v ⊑ δ(g)}
where X represents the common description to all objects in X while v represents the set of objects respecting the description v. A pair (X, v) such as X = v and v = X is called a interval pattern concept (ip-concept) with extent X and pattern intent v. Ip-concepts can be ordered in an interval pattern concept lattice (ip-concept lattice). Algorithms for computing ip-concepts from an interval pattern structure are proposed in [START_REF] Kaytoue | Revisiting numerical pattern mining with formal concept analysis[END_REF][START_REF] Ganter | Pattern Structures and their projections[END_REF].

CL4IR based on pattern structures

A document corpus or a term-document matrix, as described at the end of Section 2, can naturally be represented as a many-valued context [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF] 2 shows an example containing 9 documents (white rows) and 12 terms. The value in a cell represents the "relative frequency" of a term in a document, i.e. the ratio between the amount of times a term appears in a document and the total amount of terms occurrences in the document. Like in the binary case, a query q = {t 1 , t 2 , ..t |q| } is considered as a virtual document and included in the many-valued context which becomes K q = (D + {q}, T, W, I + {val(q, t i )} ∀ti∈q ). The cells of the query contain also a "relative frequency" value. The query q = {"graph", "tree"} is illustrated in the grey row in Table 2 (e.g. val(q, graph) = 1/2 = 0.5).

K = (D, T, W, I), where W = {val(d j , t i )} ∀dj ∈D,ti∈T and I = (d j , t i , w k ); f (d j , t i ) = w k , w k ∈ W . Table
To deal with K q , we define the pattern structure as (D + {q}, (P, ⊓), δ) where interval patterns in P contain the interval-vector representation of documents in |T | dimensions (one for each term). The mapping δ(d) = [val(d, t i ), val(d, t i )] i∈[1..|T |] assigns an interval pattern representation to a document (or the virtual query-document) consisting of a zero-length interval for each term existing in T at the value of the term in the document (e.g. in Table 2, δ(d 1 ) = [0.33, 0.33][0.33, 0.33][0.33, 0.33][0, 0] . . . [0, 0] , where [0, 0] is represented by [-]). The similarity operator ⊓ applied to two interval patterns returns the convex hull between their document representations. From the pattern structure we construct the ip-concept lattice representing the query space which will be used to retrieve documents in a similar way as binary approaches.

The query concept is still considered as the object concept of q. However the semantic of the query space changes. While in the binary case the query space represents a pool of Boolean query possibilities, here the query space can be considered as a vector space where the query is grouped with documents having similar representations. For example, consider the first three columns in Table 3 where each row represents an ip-concept. Concept 1 is the query concept which in its extent includes documents d 7 and its interval pattern (intent) only includes zero-length intervals in all 12 dimensions, making the description of the query identical to the description of d 7 . Concept 2 is a superconcept of 1, whose extent contains d 7 and d 8 . This time, there are only 9 zerolength intervals in all 12 dimensions. Concept 2 is less similar to the query than concept 1 w.r.t 3 dimensions. Following with concept 3, we can see that the later is less similar to the query than concept 1 w.r.t. 4 dimensions. We get in this way a "natural" ranking of the concepts.

In order to rank ip-concepts we rely on the notion of maximal distance within an interval pattern. For illustrating this notion, we will use the geometrical interpretation of patterns already introduced in [START_REF] Kaytoue | Revisiting numerical pattern mining with formal concept analysis[END_REF]. Let us consider the 2-dimensional case with two ip-concepts in Figure 2 For ranking an ip-concept Z i w.r.t. the query, we will consider the "maximal distance" possible between any two objects in the extent of Z i , which in the case of Z 1 is between objects q and C and for Z 2 is between q and D. Thus, this distance is actually the Euclidean distance between the edges of the interval vector. Table 3 presents the retrieved ip-concepts for the query in Table 2 ranked by maximal distance in column 4. Table 3: Extents and Intents of concepts in Figure 2 presenting the cosine similarity between its edges ([-] represents the zero-length interval [0, 0]).

Id Extent Pattern intent max dist 1 q, d7 * [-][-][-][-][-][-][-][-][-][0.5, 0.5][0.5, 0.5][-] 0 2 q, d7, d8 [-][-][-][-][-][-][-][-][-][0.33, 0.5][0.33, 0.5][0, 0.33] 0.408 3 q, d7, d8, d9 [-][-][-][-][-][-][-][-][0, 0.33][0, 0.5][0.33, 0.5][0, 0.33] 0.704 4 q, d6, d7 [-][-][-][-][-][-][-][-][-][0.5, 1][0, 0.5][-] 0.707 5 q, d2, d7 [

Dealing with real-world datasets

Calculating a concept lattice is an expensive task which can yield a large amount of concepts making it prohibitive for large document corpora. The scenario is worst for pattern structures since for every concept the size of the intent is set to the whole set of attributes adding even more complexity. Calculating the whole query space of a termdocument matrix is not advisable, since for a given query only a small part of the whole space is required. In order to avoid a sizeable query space in each step of the retrieval process, progressive actions to filter data are performed. In the following, we describe the retrieval process and each action.

1. Constructing the pattern structure: The process starts with the input of a query q = {t 1 , t 2 , ..., t |q| } and ends after the pattern structure containing the virtual querydocument is created. We include in the set of documents only those which contain at least a given number of the terms provided in the query, which can be performed at a negligible cost by firstly storing documents and terms in a relational database. The set of terms only include those provided in the query. The minimum number of terms for a document is left as a parameter of the process.

2. Constructing the ip-concept lattice: This step receives the pattern structure in order to create an ip-concept lattice. A standard FCA algorithm, namely Ganter's algorithm [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF] is used for this purpose. However the algorithm has been adapted for the present task.

Many ip-concepts found in the interval pattern lattice are not useful for document retrieval purposes. For example, the framework creates ip-concepts with documents which do not share terms (e.g. consider the interval [0, 1][0, 1][0, 1] created from the documents sharing no terms with orthogonal representations

v 1 = [0, 0][1, 1][1, 1] and v 2 = [1, 1][0, 0][0, 0]
). We denominate these concepts non-informational.

In order to reduce the amount of non-informational concepts, we modified the ⊓ operator in the set of ordered patterns (P, ⊓) such as [l, r] ⊓ [0, 0] = [ * ] and [l, r] ⊓ [ * ] = [ * ]; ∀l, r ∈ R. The interval [ * ] has been used before to indicate absence of similarity [START_REF] Kaytoue | Embedding tolerance relations in formal concept analysis[END_REF]. Let Z i = (X i , v i ) be an ip-concept, then ρ(Z i ) represents the number of intervals different from [ * ] in v i . We call ρ(Z i ) the dimensionality of Z i . For a second ip-concept

Z j = (X j , v j ) is easy to show that (Z i ≤ Z j ⇐⇒ v j ⊑ v i ) =⇒ ρ(Z i ) ≤ ρ(Z j ).
We use a threshold of minimal dimensionality (min dim) to reduce the amount of ipconcepts calculated. Consider this analogous to the use of a minimal support in the construction of an iceberg lattice [START_REF] Stumme | Conceptual clustering with iceberg concept lattices[END_REF].

Experiments and Discussion

To test the validity of the proposed approach, we applied it on a popular IR dataset which is openly available. We refer to this implementation as "ip-CL4IR". The CISI dataset 4 consists of 1460 documents and 35 queries, each one containing a set of valid answers. Documents contain text in natural language and queries are given as a set of terms connected by Boolean operators. In our experiments, we converted documents to collections of weighted terms and stored them in a relational database. The weighting measure used was term frequency-inverse document frequency (tf.idf ) [START_REF] Manning | Introduction to Information Retrieval[END_REF]. Boolean operators in the query were ignored since they do not provide meaning in the vectorspace model (except in the extended Boolean model case [START_REF] Salton | Extended Boolean information retrieval[END_REF] not considered in this work). The virtual query-document was constructed using the inverse document frequencies calculated from the dataset for each of its terms.

After receiving a query, ip-CL4IR consults the database and extracts all documents that contain at least 2 terms of the query (as described in Section 3.3, this value is a parameter of ip-CL4IR). The ip-concept lattice is computed using a minimal dimensionality of min dim = 2, to keep consistency w.r.t. the restriction given for the creation of the pattern structure. The query concept is searched in the lattice and its superconcepts are retrieved and ranked using the Euclidean distance between the boundaries of their interval patterns. Cosine distance (instead of Euclidean distance) was also calculated showing better results. Table 4 shows the results for 11-point precision of fixed recall and 6 measures of precision for the top 5,10 and 20 ranked documents retrieved. Results on an implementation based on concept lattice-based ranking (CLR) [START_REF] Carpineto | Order theoretical ranking[END_REF] using the same dataset and a simple binnarization of the relation document-term is reported along with our results for comparison purposes. 4 reports the results in 8 measures for ip-CL4IR, a reported CL4IR system called concept lattice-based ranking (CLR) [START_REF] Carpineto | Order theoretical ranking[END_REF] and a naive approach called exact matching (EM) where documents are ranked according to how many terms have in common w.r.t. the query. The second row contains the values of the interpolated average precision (IAP) over 11-points of recall illustrated on Figure 3. Interpolated precision in a given recall point r i in Figure 3 indicates the best precision value in the interval [r i , r i+1 [. From Figure 3, the interpolated precision in the recall point 0 for ip-CL4IR is the best precision obtained in the recall interval [0, 1[ equal to 0.51. The third row contains the values of the mean average precision (MAP) calculated over the precision values for each valid document found in the ranked documents retrieved by a system for each query. For example, given query if the first valid document is found in the third position of the ranking it has a precision value of 0.3. If the second is found in the fifth position its precision is 0.2 and the MAP is 0.25. IAP and MAP are standard information retrieval measures [START_REF] Manning | Introduction to Information Retrieval[END_REF] to evaluate ranked results from a retrieval system. The remaining rows present values of precision and recall in the first 5 (@5), 10 (@10) and 20 (@20) ranked documents from each system. Boldface entries indicate the best values for the three systems.

Values in Table 4 show a better performance of ip-CL4IR on 4 of the 8 measures while EM is better in the remaining 4, namely precision and recall in the first 5 and 10 ranked documents. This indicates that EM is actually better to recognize documents very close to the query, but for documents with less elements in common with the query, EM is not very precise. This can be better appreciated in Figure 3 where the interpolated precision values of ip-CL4IR quickly overcome those of EM which is only better in 1 of the 11 recall points. This fact is also supported by the significant difference in the values of IAP and MAP between ip-CL4IR and EM. For the 35 queries in the dataset, our approach took 42.23 seconds (1.2 seconds per query) to execute while for CLR took 1550.333 (44.29 seconds per query) showing an impressive enhancement in the computational time required to retrieve documents, a key issue in document retrieval. Both these times include lattice construction. Using better measures which consider the correlation among terms, or including external knowledge sources like term taxonomies may improve greatly the quality of the answers provided by our approach. These issues are currently planned as future work. These experiments were performed in an Intel Xeon machine running at 2.27 GHz with 62 GB of RAM memory.

There are many perspectives for our approach, however the most important is the full exploitation of the ip-lattice structure to improve the quality in the answers. While our principal goal in this article is to describe a general process to directly support numeric term-document datasets in a concept lattice-based information retrieval system, we argue that different IR tasks (some already supported on CL4IR systems) can be also supported on ip-CL4IR for example, document clustering [START_REF] Carpineto | A survey of Web clustering engines[END_REF], user feedback inclusion [START_REF] Ferré | Camelis: a logical information system to organise and browse a collection of documents[END_REF] and recommendation [START_REF] Ignatov | Concept-based Recommendations for Internet Advertisement[END_REF].

Conclusions

In this article we introduce a CL4IR approach which is able to deal directly with numerical datasets through the use of the pattern structure framework (ip-CL4IR). We provide a method and a process to construct an interval pattern concept lattice (ip-concept lattice) which can be used as a document index. We present the idea of an ip-concept lattice as a query space which can be navigated in order to find relevant documents. We also provide means to rank these documents using vector-based distances. The feasibility of our approach is validated through its application on a popular IR dataset for which we present precision and recall values contrasted to those reported in the literature showing a better performance in the overall list of ranked documents and an impressive enhancement in the time needed to answer a single query.

The perspectives for our approach are numerous, ranging from the improvement of its answers, its application on different real-world datasets, but most importantly, the full exploitation of the lattice structure to support different IR tasks.

Fig. 1 :

 1 Fig. 1: Concept lattice in reduced notation derived from a document-term formal context including the query.

  , namely Z 1 = ({q, A, B, C}, [2, 7][2, 7] ) (clear rectangle) and Z 2 = ({q, A, B, C, D}, [1, 7][1, 7] ) (dark rectangle).

Table 2 :

 2 Many-valued document term context (including query).a Grey row represents the query concept.

Fig. 2 :

 2 Fig. 2: Two interval patterns in the query space.

  -][-][0, 0.16][0, 0.16][0, 0.16][0, 0.16][0, 0.16][-][0, 0.16][0, 0.5][0, 0.5][-] 0.808 6 q, d3, d7 [-][0, 0.25][-][0, 0.25][0, 0.25][-][-][0, 0.25][-][0, 0.5][0, 0.5][-] 0.866 7 q, d1, d7 [0, 0.33][0, 0.33][0, 0.33][-][-][-][-][-][-][0, 0.5][0, 0.5][-] 0.909 8 q, d5, d7 [-][-][-][0, 0.33][-][0, 0.33][0, 0.33][-][-][0, 0.5][0, 0.5][-] 0.909 9 q, d4, d7 [0, 0.25][-][-][-][0, 0.5][-][-][0, 0.25][-][0, 0.5][0, 0.5][-] 0.935 * Grey row represents the query concept.

aFig. 3 :

 3 Fig. 3: Interpolated precision in 11 points of recall Table4reports the results in 8 measures for ip-CL4IR, a reported CL4IR system called concept lattice-based ranking (CLR)[START_REF] Carpineto | Order theoretical ranking[END_REF] and a naive approach called exact matching (EM) where documents are ranked according to how many terms have in common w.r.t. the query. The second row contains the values of the interpolated average precision (IAP) over 11-points of recall illustrated on Figure3. Interpolated precision in a given recall point r i in Figure3indicates the best precision value in the interval [r i , r i+1 [. From Figure3, the interpolated precision in the recall point 0 for ip-CL4IR is the best precision obtained in the recall interval [0, 1[ equal to 0.51. The third row contains the values of the mean average precision (MAP) calculated over the precision values for each valid document found in the ranked documents retrieved by a system for each query. For example, given query if the first valid document is found in the third position of the ranking it has a precision value of 0.3. If the second is found in the fifth position its precision is 0.2 and the MAP is 0.25. IAP and MAP are standard information retrieval measures[START_REF] Manning | Introduction to Information Retrieval[END_REF] to evaluate ranked results from a retrieval system. The remaining

  Table 1 illustrates a document-term formal context created from a corpus of 9 documents and 12 terms.

	human	interface	computer	user	system	response	time	EPS survey	tree	graph	minor

Table 4 :

 4 CISI dataset. Results for 35 queries.

		ip-CL4IR CLR EM
	11-point IAP a	0.232 0.191 0.174
	MAP b	0.202 0.163 0.145
	Precision@5	0.257 0.206 0.285
	Precision@10	0.251 0.174 0.257
	Precision@20	0.245 0.174 0.207
	Recall@5	0.032 0.049 0.057
	Recall@10	0.060 0.073 0.079
	Recall@20	0.146 0.112 0.123

http://ftp.cs.cornell.edu/pub/smart/cisi/

⋆ Part of the Quaero Programme, funded by OSEO, French State agency for innovation. ⋆⋆ Supported by the National Research Fund, Luxembourg, and cofunded under the Marie Curie Actions of the European Commission (FP7-COFUND).


Nadir Farhi
email: nadir.farhi@ifsttar.fr

Piecewise linear car-following modeling

Keywords: Car-following modeling, Optimal control, Variational formulations

We present a traffic model that extends the linear car-following model as well as the minplus traffic model (a model based on the min-plus algebra). A discrete-time car-dynamics describing the traffic on a 1-lane road without passing is interpreted as a dynamic programming equation of a stochastic optimal control problem of a Markov chain. This variational formulation permits to characterize the stability of the car-dynamics and to calculte the stationary regimes when they exist. The model is based on a piecewise linear approximation of the fundamental traffic diagram.

Introduction

Car-following models are microscopic traffic models that describe the car-dynamics with stimulus-response equations expressing the drivers' behavior. Each driver responds, by choosing its speed or acceleration, to a given stimulus that can be composed of many factors such as inter-vehicular distances, relative velocities, instantaneous velocities, etc. We present in this article a car-following model that extends the linear car-following model [START_REF] Chandler | Traffic dynamics: Studies in car following[END_REF][START_REF] Herman | Traffic dynamics: Analysis of stability in car following[END_REF][START_REF] Denos | Car-Following Theory of Steady-State Traffic Flow[END_REF][START_REF] Gazis | Nonlinear follow-the-leader models of traffic flow[END_REF], as well as the min-plus traffic model [START_REF] Lotito | A min-plus derivation of the fundamental car-traffic law[END_REF].

The vehicular traffic on a 1-lane road without passing is described by discrete-time dynamics, which are interpreted as dynamic programming equations associated to stochastic optimal control problems of Markov chains. The discrete-time variational formulation we make here is similar to the time-continuous one used by Daganzo and Geroliminis [START_REF] Daganzo | An analytical approximation for the macroscopic fundamental diagram of urban traffic[END_REF] to show the existence of a concave macroscopic fundamental diagram.

We are concerned in this article by microscopic traffic modeling with a Lagrangian description of the traffic dynamics, where the function x(n, t), giving the position of car n at time t (or the cumulated distance traveled by a car n up to time t), is used. In the macroscopic kinematic traffic modeling, Eulerian descriptions of the traffic dynamics are usually used, with the function n(t, x) giving the cumulated number of cars passing through position x up to time t (which coincides with the Moscowitz function [START_REF] Daganzo | On the variational theory of traffic flow: well-posedness, duality and applications[END_REF] in the case of traffic without passing). The combination of a conservation law with an equilibrium law gives the well known first order traffic model of Lighthill, Whitham and Richards [START_REF] Lighthill | A min-plus derivation of the fundamental car-traffic law[END_REF][START_REF] Richards | Shock waves on the highway[END_REF].

In this introduction, we first notice that the same approach used in macroscopic traffic modeling, combining a conservation law with an equilibrium law, can be used to derive microscopic traffic models. By this, we introduce car-following models and give a review on basic and most important existing ones. In particular, we recall the linear and the min-plus car-following models, which are particular cases of the model we present here. Finally, we recall a theoretical result on non-expansive and connected dynamic systems which we need in our developments, and give the outline of this article.

The first order partial derivative of the function x(n, t) in time, denoted ẋ(n, t) expresses the velocity v(n, t) of car n at time t. The first order differentiation of x(n, t) in the car numbers ∆x(n, t) expresses the inverse of the inter-vehicular distance y(n, t) = x(n -1, t)x(n, t) between cars n and n -1 at time t. The equality of the second derivatives ∆ ẋ(n, t) and ∆x(n, t) gives then the following conservation law of distance. ẏ(n, t) = -∆v(n, t).

(

) 1
If we assume that a fundamental diagram V e , giving the velocity v as a function of the inter-vehicular distance y (v = V e (y)) at the stationary traffic, exists, and that the diagram V e holds also on the transient traffic, then we have

ẏ(n, t) = v(n, t)/V ′ e (y), (2)
where V ′ e (y) denotes the derivative of V e with respect to y. By combining (1) and ( 2) we obtain the model:

v(n, t) = -V ′ e (y(n, t))∆v(n, t). (3)
(3) is a car-following model that gives the acceleration of car n at time t as a response to a stimulus composed of the relative speed ∆v(n, t) and the term V ′ e (y(n, t)). For example, if V e (y) = v 0 exp -a/y, where v 0 denotes the free (or desired) velocity, and a is a parameter, then V ′ (y) = aV (y)/y 2 and (3) gives a particular case of the Gazis, Herman, and Rothery model [START_REF] Gazis | Nonlinear follow-the-leader models of traffic flow[END_REF].

The simplest car-following model is the linear one, where the car dynamics are written

ẋn (t + T ) = a(x n-1 (t) -x n (t)) + b, ( 4
)
where T is the reaction time, a is a sensitivity parameter, and b is a constant. That model can be derived from (3) with a linear fundamental diagram V e . The stability of the linear car-following model (4) and the existence of a stationary regime have been treated in [START_REF] Herman | Traffic dynamics: Analysis of stability in car following[END_REF]. Almost all car following models are based on the assumption of the existence of a behavioral law V e . The latter has been taken linear in [START_REF] Greenshields | A study of traffic capacity[END_REF][START_REF] Herman | Traffic dynamics: Analysis of stability in car following[END_REF], logarithmic in [START_REF] Greenber | An analysis of traffic flow[END_REF], exponential in [START_REF] Newell | Nonlinear effects in the dynamics of car following[END_REF], and with more complicated forms in other works. Bando et al. [START_REF] Bando | Dynamical model of traffic congestion and numerical simulation[END_REF] used the sigmiudal function

V e (y) = tanh(y -h) + tanh(h), (5)
where tanh denotes the hyperbolic tangent function, and h is a constant.

Kerner and Konhäuser [START_REF] Kerner | Cluster effect in initially homogeneous traffic flow[END_REF], Hermann and Kerner [START_REF] Herrmann | Local cluster effect in different traffic flow models[END_REF], and then Lenz et al. [START_REF] Lenz | Multi-anticipative car-following model[END_REF], and Hoogendoorn et al. [START_REF] Serge P Hoogendoorn | Empirics of multianticipative car-following behavior[END_REF] have used the function

V e (y) = v 0 1 + exp 1, 000 γ • y - 10 2.1 -1 -5.34 • 10 -9 , (6)
where free velocity v 0 and γ are parameters estimated from data. In [START_REF] Lenz | Multi-anticipative car-following model[END_REF], γ is taken equal to 7.5. See also [START_REF] Helly | Simulation of bottlenecks in single lane traffic flow[END_REF][START_REF] Helly | Simulation of bottlenecks in single lane traffic flow[END_REF][START_REF] Treiber | Congested traffic states in empirical observations and microscopic simulations[END_REF].

The min-plus traffic model [START_REF] Lotito | A min-plus derivation of the fundamental car-traffic law[END_REF] is a microscopic discrete-time car-following model based on the min-plus algebra [START_REF] Baccelli | Synchronization and Linearity[END_REF]. It consists in the following dynamics.

x n (t + 1) = min{x n (t) + v 0 , x n-1 (t) -σ}, (7)
where v 0 is the free velocity and σ is a safety distance.

The idea of the model ( 7) is that the car dynamics is linear in the min-plus algebra [START_REF] Baccelli | Synchronization and Linearity[END_REF], where the addition is the operation "min" and the product is the standard addition "+". In [START_REF] Lotito | A min-plus derivation of the fundamental car-traffic law[END_REF], the dynamic system ( 7) is written in min-plus notations x(t) = A ⊗ x(t -1), where A is a min-plus matrix and ⊗ is the min-plus product of matrices. It is then proved that the average growth rate vector per time unit of the system, defined by χ = lim t→∞ x(t)/t satisfies χ = (v, v, • • • , v), where v is the unique min-plus eigenvalue of the matrix A, interpreted as the stationary car-speed. The fundamental diagram is then obtained

v = min(v 0 , ȳ -σ) (8) q = min(v 0 ρ, 1 -σ ρ), (9)
where ȳ, q and ρ denote respectively the equilibrium inter-vehicular distance, car-flow and car-density. In [START_REF] Daganzo | An analytical approximation for the macroscopic fundamental diagram of urban traffic[END_REF], for t ≥ 0, if

x n-1 (t) -x n (t) > v 0 + σ, then the dynamics is x n (t + 1) -x n (t) = v 0 . If x n-1 (t) -x n (t) ≤ v 0 + σ then the dynamics is x n (t + 1) -x n (t) = x n-1 (t) -x n (t) -σ.
Therefore, [START_REF] Daganzo | An analytical approximation for the macroscopic fundamental diagram of urban traffic[END_REF] is linear in both phases of free and congested traffic. The min-plus model [START_REF] Daganzo | An analytical approximation for the macroscopic fundamental diagram of urban traffic[END_REF] permits to distinguish two phases in which the traffic dynamics is linear, but with a sensitivity parameter (a in (4)) equals to 1 for each phase. The linear model ( 4) is not constrained in the sensitivity parameter value, but it permits the modeling of only one traffic phase. The model we present here extends (4) and [START_REF] Daganzo | An analytical approximation for the macroscopic fundamental diagram of urban traffic[END_REF] in a way that an arbitrary number of traffic phases can be modeled, with flexibility in the sensitivity parameter value on each phase.

For our model, we apply a similar but more general approach than the min-plus one used to analyze the dynamic system [START_REF] Daganzo | An analytical approximation for the macroscopic fundamental diagram of urban traffic[END_REF]. Indeed, the dynamics (7) is additive homogeneous of degree one1 and is monotone2 . It is then non expansive3 [START_REF] Candrall | Some relations between nonexpansive and order preserving mappings[END_REF]. The stability of the dynamic system [START_REF] Daganzo | An analytical approximation for the macroscopic fundamental diagram of urban traffic[END_REF] is thus guaranteed from its non expansiveness. Moreover, [START_REF] Daganzo | An analytical approximation for the macroscopic fundamental diagram of urban traffic[END_REF] is connected (or communicating)4 [START_REF] Gaubert | A non-linear hierarchy for discrete event dynamical systems[END_REF][START_REF] Gaubert | Existence of eigenvectors for monotone homogeneous functions[END_REF]. An important result from [START_REF] Gunawardena | On the existence of cycle times for some nonexpansive maps[END_REF][START_REF] Gaubert | A non-linear hierarchy for discrete event dynamical systems[END_REF] (Theorem 1 below) permits the analysis of non expansive and connected dynamic systems. Theorem 1. [START_REF] Gunawardena | On the existence of cycle times for some nonexpansive maps[END_REF][START_REF] Gaubert | A non-linear hierarchy for discrete event dynamical systems[END_REF] If a dynamic system x(t) = f (x(t-1)) is non expansive and connected, then the additive eigenvalue problem v + x = f (x) admits a solution (v, x), where x is defined up to an additive constant, not necessarily in a unique way, and v ∈ R n is unique. Moreover, the dynamic system admits an average growth rate vector χ, which is unique (independent of the initial condition) and given by χ(f

) = t (v, v, • • • , v).
The model treated in this article can be seen as an extension of the min-plus model [START_REF] Daganzo | An analytical approximation for the macroscopic fundamental diagram of urban traffic[END_REF]. In Section 2, we present the model. It is called piecewise linear car-following model because it is based on a piecewise linear fundamental diagram V e . The model describes the traffic of cars on a ring road of one lane without passing. The stability conditions of the dynamic system describing the traffic are determined. Under those conditions, the car-dynamics are interpreted as a dynamic programming equation (DPE) associated to a stochastic optimal control problem of a Markov chain. The DPE is solved analytically. We show that the individual behavior law V e supposed in the model is realized on the collective stationary regime. Finally, the effect of the stability condition on the shape of the fundamental diagram is shown.

In section 3, we give equivalent results of those given in section 2 for the traffic on an "open" road (a highway stretch for example), and conclude with an example, where we simulate the transient traffic, basing on a piecewise linear approximation of the diagram [START_REF] Daganzo | On the variational theory of traffic flow: well-posedness, duality and applications[END_REF].

In Appendix B, we give more details on the duality in traffic modeling, of using the functions n(t, x), x(n, t) and t(n, x), where t(n, x) denotes the time of passage of the nth car by position x.

Piecewise linear car following model

The behavioral law V e is an increasing curve bounded by the free speed v 0 . Moreover, V e (y) = 0 for y ∈ [0, y j ] where y j denotes the jam inter-vehicular distance. We propose here to approximate the curve V e with a piecewise-linear curve

V e (y) = min u∈U max w∈W {α uw y + β uw }, (10)
where U and W are two finite sets of indices. Since V e is increasing, we have

α uw ≥ 0, ∀(u, w) ∈ U × W.
We are interested here on the discrete-time first-order dynamics

x n (t + 1) = x n (t) + min u∈U {α u (x n-1 (t) -x n (t)) + β u }, (11)
and

x n (t + 1) = x n (t) + min u∈U max w∈W {α uw (x n-1 (t) -x n (t)) + β uw }. (12)
It is clear that [START_REF] Gaubert | Existence of eigenvectors for monotone homogeneous functions[END_REF] extends [START_REF] Gaubert | A non-linear hierarchy for discrete event dynamical systems[END_REF]. The model ( 12) is also an extension of both linear model ( 4) and min-plus model [START_REF] Daganzo | An analytical approximation for the macroscopic fundamental diagram of urban traffic[END_REF].

In this article, we characterize the stability of the dynamics [START_REF] Gaubert | Existence of eigenvectors for monotone homogeneous functions[END_REF], calculate the stationary regimes, show that the fundamental diagrams are effectively realized at the stationary regime, and analyze the transient traffic. We will distinguish two cases: Traffic on a ring road and traffic on an "open" road.

Traffic on a ring road

We follow here the modeling of [START_REF] Lotito | A min-plus derivation of the fundamental car-traffic law[END_REF]. Let us consider ν cars moving a one-lane ring road in one direction without passing. We assume that the cars have the same length that we take here as the unity of distance. The road is assumed to be of size µ; that is, it can contain at most µ cars. The car density on the road is thus ρ = ν/µ.

Stochastic optimal control model

We consider here the car dynamics [START_REF] Gaubert | A non-linear hierarchy for discrete event dynamical systems[END_REF]. That is to say that each car n maximizes its velocity at time t under the constraints

x n (t + 1) ≤ x n (t) + α u (x n-1 (t) -x n (t)) + β u , ∀u ∈ U. (13)
Each constraint of (13) bounds the velocity x n (t + 1)x n (t) by a sum of a fixed term β u and a term depending linearly on the inter-vehicular distance.

Let us first notice that [START_REF] Gaubert | A non-linear hierarchy for discrete event dynamical systems[END_REF], on the ring road, is written

x n (t + 1) = x n (t) + min u∈U {α u (x n-1 (t) -x n (t)) + β u }, for n ≥ 2, x 1 (t + 1) = x 1 (t) + min u∈U {α u (x n (t) + µ -x 1 (t)) + β u },
which can also be written

x n (t + 1) = min u∈U {(1 -α u )x n (t) + α u x n-1 (t) + β u }, for n ≥ 2, x 1 (t + 1) = min u∈U {(1 -α u )x 1 (t) + α u x n (t) + α u ν/ρ + β u }.
Let us denote by M u , u ∈ U the family of matrices defined by

M u =      1 -α u 0 • • • α u α u 1 -α u 0 . . . . . . . . . 0 0 α u 1 -α u     
, and by c u , u ∈ U, the family of vectors defined by

c u = t [α u ν/ρ + β u , β u , • • • , β u ].
The dynamics [START_REF] Gaubert | A non-linear hierarchy for discrete event dynamical systems[END_REF] are then written :

x n (t + 1) = min u∈U {[M u x(t)] n + c u n }, 1 ≤ n ≤ ν . (14)
The system ( 14) is additive homogeneous of degree 1 by the definition of the matrices M u , u ∈ U. It is monotone under the condition that all the components of M u , u ∈ U are non negative, which is equivalent to α u ∈ [0, 1], ∀u ∈ U. Hence, under that condition, the system ( 14) is non expansive.

Moreover, the matrices M u , u ∈ U are stochastic 5 . Those matrices can then be seen as transition matrices of a controlled Markov chain, where the set of controls is U . The connectedness of the system ( 14), as defined in the previous section, is related to the irreducibility of the Markov chain with transition matrices M u , u ∈ U. It is easy to check that ( 14) is connected if and only if ∃u ∈ U , α u ∈ (0, 1]; see Appendix A for the proof. That condition is interpreted in term of traffic by saying that every car moves by taking into account the position of the car ahead.

Consequently, under the condition ∀u ∈ U , α u ∈ [0, 1] and ∃u ∈ U , α u ∈ (0, 1], the dynamic system ( 14) is non expansive and is connected. Therefore, by Theorem 1, we conclude that the additive eigenvalue problem

v + x n = min u∈U {[M u x] n + c u n }, 1 ≤ n ≤ ν , (15)
describing the stationary regime of the dynamic system [START_REF] Denos | Car-Following Theory of Steady-State Traffic Flow[END_REF], admits a solution (v, x), where x is defined up to an additive constant, not necessarily in a unique way, and v ∈ R n is unique. Moreover, the dynamic system admits a unique average growth rate per time unit χ, whose components are all equal and coincide with v. The average growth rate per time unit χ of the system ( 14) is interpreted in term of traffic as the stationary car-velocity. The additive eigenvector x gives the asymptotic distribution of cars on the ring. x is given up to an additive constant, since the car-dynamics ( 14) is additive homogeneous of degree 1. That is to say that if (v, x) is a solution of ( 15) then (v, e + x) is also a solution for [START_REF] Geroliminis | Hysteresis phenomena of a macroscopic fundamental diagram in freeway networks[END_REF], for every constant e ∈ R.

Let us now give an interpretation of the model in term of ergodic stochastic optimal control. Indeed, (15) can be seen as a dynamic programming equation of an ergodic stochastic optimal control problem of a Markov chain with transition matrices M u , u ∈ U and costs c u , u ∈ U, and with a set of states N = {1, 2, • • • , ν}. The stochastic optimal control problem of the chain is written

min s∈S E lim T →+∞ 1 T T t=0 c ut nt , ( 16
)
where S is a set of feedback strategies on N . A strategy s ∈ S associates to every state n ∈ N a control u ∈ U (that is u t = s(n t )).

The following result gives one solution (v, x) for the dynamic programming equation ( 15).

Theorem 2. The system (15) admits a solution (v, x) given by:

v = min u∈U {α u ȳ + β u }, x = t [0 ȳ 2ȳ • • • (ν -1)ȳ].
Proof. First, because of the symmetry of the system [START_REF] Geroliminis | Hysteresis phenomena of a macroscopic fundamental diagram in freeway networks[END_REF], it is natural that the asymptotic car-positions x n , 1 ≤ n ≤ ν are uniformly distributed on the ring, and that the optimal strategy is independent of the state x. Let us prove it. Let ū ∈ U be defined by α ū ȳ + β ū = min u∈U {α u ȳ + β u } = v. Let x be the vector given in Theorem 2. Then ∀n ∈ {1, 2, • • • , ν} we have

[M ūx] n + c ū n = (α ū ȳ + β ū) + x n = min u∈U (α u ȳ + β u ) + x n = min u∈U {[M u x] n + c u n } = v + x n .
In term of traffic, Theorem 2 shows that the car-dynamics is stable under the condition α u ∈ [0, 1], and the average car speed is given by the additive eigenvalue of the asymptotic dynamics in the case where the system is connected. Moreover, it affirms that the fundamental diagram supposed in the model is realized at the stationary regime.

v = min u∈U {α u ȳ + β u }, (17) q
= min u∈U {α u + β u ρ}. ( 18
)
It is important to note here that, up to the assumption α u ∈ [0, 1], ∀u ∈ U, every concave curve V e or Q e can be approximated with [START_REF] Greenshields | A study of traffic capacity[END_REF] or [START_REF] Gunawardena | On the existence of cycle times for some nonexpansive maps[END_REF]. Indeed, approximating fundamental diagrams using those formulas is nothing but computing Fenchel transforms; see [START_REF] Daganzo | On the variational theory of traffic flow: well-posedness, duality and applications[END_REF][START_REF] Aubin | Dirichlet problems for some hamilton-jacobi equations with inequality constraints[END_REF]. More precisely, if we denote by V the set V = {β u , u ∈ U} and define the function g by:

g : V → R v = β u → -α u , then q = Q e (ρ) = min v∈V (ρv -g(v)) = g * (ρ),
where g * denotes the Fenchel transform of g. Finally, we note that the min-plus linear model is a particular case of the model presented in this section, where U = {u 1 , u 2 } with (α 1 , β 1 ) = (0, v) and (α 2 , β 2 ) = (1, -σ). In this case, the fundamental traffic diagram is approximated with a piecewise linear curve with two segments.

Stochastic game model

We consider in this section the car dynamics [START_REF] Gaubert | Existence of eigenvectors for monotone homogeneous functions[END_REF], again with the assumption ∀(u, w) ∈ U × W, α uw ∈ [0, 1] and ∃(u, w) ∈ U × W, α uw ∈ (0, 1]. The dynamic system ( 12) is interpreted as a stochastic dynamic programming equation associated to a stochastic game problem on a controlled Markov chain. As above, a generalized eigenvalue problem is solved. The extension we make here approximates non concave fundamental diagrams.

In term of traffic, we take into account the drivers' behavior changing from low densities to high ones. The difference between these two situations is that in low densities, drivers, moving, or being able to move with high velocities, they try to leave large safety distances between each other, so the safety distances are maximized; whilst in high densities, drivers, moving, or having to move with low velocities, they try to leave small safety distances between each other in order to avoid jams; so they minimize safety distances.

To illustrate this idea, let us consider the following two dynamics of a given car n.

x

n (t + 1) = min{x n (t) + v, x n-1 (t) -σ}, (19)
x n (t + 1) = min{x n (t) + v, max{x n-1 (t) -σ, (x n (t) + x n-1 (t))/2}}. ( 20
)
The dynamics ( 19) is a min-plus dynamics which grossly tell that cars move with their desired velocity v at the fluid regime and they keep a safety distance σ at the congested regime. The dynamics [START_REF] Helly | Simulation of bottlenecks in single lane traffic flow[END_REF] distinguishes two situations at the congested regime:

• In a relatively low density situation where the cars are separated by a distance that equals at least to 2σ we have max{x n-1 (t)σ, (x n (t) + x n-1 (t))/2} = x n-1 (t)σ.

• In a high density situation, where the cars are separated by distances less than 2σ we have max{x n-1 (t)σ, (x n (t) + x n-1 (t))/2} = (x n (t) + x n-1 (t))/2.

In this case, we accept the cars moving closer but by reducing the approach speed in order to avoid collisions. This is realistic.

The situation we have considered in ( 20) is realistic and very simple, but, it cannot be obtained without introducing a maximum operator in the dynamics (i.e. with only minimum operators). Indeed, with only minimum operators the approach is mechanically reduced with the increasing of the car-density (in fact this is the concaveness of the fundamental diagram). Because of the realness of such scenarios, we think that the fundamental traffic diagram should be composed of two parts, a concave part at the fluid regime, and a convex part at the congested regime. The dynamics [START_REF] Gaubert | Existence of eigenvectors for monotone homogeneous functions[END_REF] generalizes this idea.

The dynamics (12) can be written

x n (t + 1) = min u∈U max w∈W {[M uw x(t)] n + c uw n }, 1 ≤ n ≤ ν , (21)
where

M uw =      1 -α uw 0 • • • α uw α uw 1 -α uw 0 . . . . . . . . . 0 0 α uw 1 -α uw      , and c u = t [α uw ν/ρ + β uw , β uw , • • • , β uw ].
Similarly, we can easily check that the dynamic system ( 21) is non expansive under the condition α uw ∈ [0, 1], ∀(u, w) ∈ U ×W. Its stability is thus guaranteed under that condition. If, in addition, ∃(u, w) ∈ U × W, α uw ∈ (0, 1], then the system is connected. In this case, we get the same results as in Theorem 2. That is, the eigenvalue problem

v + x n = min u∈U max w∈W {[M uw x] n + c uw n }, 1 ≤ n ≤ ν (22)
admits a solution (v, x) given by: v = min u∈U max w∈W {α uw ȳ + β uw },

x = t [0 ȳ 2ȳ • • • (ν -1)ȳ].
Moreover, the dynamic system (21) admits a unique average growth rate vector χ, whose components are all equal to v. The car-dynamics is then stable under the condition ∀(u, w) ∈ U × W, α uw ∈ [0, 1], and the average car speed is given by the additive eigenvalue of the asymptotic dynamics in the case where the system is connected (that is, if ∃(u, w) ∈ U × W, α uw ∈ (0, 1]). The behavior law supposed in the model is realized at the stationary regime.

In term of stochastic optimal control, the system ( 22) can be seen as a dynamic programming equation associated to a stochastic game, with two players, on a Markov chain. The set of states of the chain is again N = {1, 2, • • • , ν}. The chain is controlled by two players, a minimizer one with a finite set U of controls, and a maximizer one with a finite set W of controls. The transitions and the costs of the chain are given by the matrices M uw and the vectors c uw , (u, w) ∈ U × W defined above.

The stochastic optimal control problem is

min max | s∈S E lim T →+∞ 1 T T t=0 c utwt n(t) , ( 25
)
where S is the set of strategies assoicating to every state n ∈ N a couple of commands (u, w) ∈ U × W. It is assumed here that the maximizer knows at each step the decision of the minimizer. We now give a consequence of the stability condition α uw ∈ [0, 1], ∀(u, w) ∈ U × W, on the shape of the fundamental diagrams ( 23) and [START_REF] Kerner | Cluster effect in initially homogeneous traffic flow[END_REF]. As shown in Figure 1, where we have drawn the fundamental diagram (6) (with v 0 = 14 meter by half second, and γ = 7.5), the stability condition puts the curves ( 23) and ( 24) in specific respective regions in the plan. Indeed, for the diagram ( 23), if we assume that V e is bounded by v 0 , V e (y) = 0, ∀y ∈ [0, y j ], and that V e is continuous (and increasing), then starting by the point (y j , 0), one cannot join any point above the line passing by (y j , 0) and having the slope 1, with any sequence of segments of slopes α uw ∈ [0, 1]. We can write V e (y) ≤ max(0, min(v 0 , yy 0 )).

Similarly, on the diagram ( 24), if we assume that Q e is continuous and Q e (ρ) = 0, ∀ρ ∈ [ρ j , 1], then going back from the point (ρ j , 0), one cannot attain any point above the line passing by (ρ j , 0) and (0, 1), with a sequence of segments having their ordinates at the origin (α uw ) in [0, 1]. We can write Q e (ρ) ≤ max(0, min(v 0 ρ, 1ρ/ρ j )).

Traffic on an open road

We study in this section the traffic on an open road with one lane and without passing. We are interested in the following dynamics.

x 1 (t + 1) = x 1 (t) + v 1 (t), x n (t + 1) = min u∈U max w∈W {x n (t) + α uw [x n-1 (t) -x n (t)] + β uw }. ( 26
)
If we denote by M uw the matrices

M uw =      1 0 • • • 0 α uw 1 -α uw 0 . . . . . . . . . 0 0 α uw 1 -α uw     
, and by c uw (t) the vectors

c uw (t) = t [v 1 (t), β uw , • • • , β uw , β uw ],
for (u, w) ∈ U × W and t ∈ N, then the dynamic system ( 26) is written

x n (t + 1) = min u∈U max w∈W {[M uw x(t)] n + c uw n }, 1 ≤ n ≤ ν . ( 27
)
It is easy to check that the dynamic system ( 27) is additive homogeneous of degree 1, and is monotone under the condition ∀(u, w) ∈ U × W, α uw ∈ [0, 1]. Therefore, under that condition, ( 27) is non expansive. However, ( 27) is not connected for every (u, w) ∈ U × W.

We will be interested here, in particular, in the stationary regime, where v 1 (t) reaches a fixed value v 1 . For this case, the eigenvalue problem associated to [START_REF] Lighthill | A min-plus derivation of the fundamental car-traffic law[END_REF]

is v + x 1 = x 1 + v 1 , v + x n = min u∈U max w∈W {x n + α uw [x n-1 -x n ] + β uw }. (28)
The system (28) is also written

v + x n = min u∈U max w∈W {[M uw x] n + c uw n }, 1 ≤ n ≤ ν , (29)
where

c uw = t [v 1 , β uw , • • • , β uw , β uw ].
Then we have the following result.

Theorem 3. For all y ∈ R satisfying min u∈U max w∈W (α uw y + β uw ) = v 1 , the couple (v, x) is a solution for the system [START_REF] Newell | Nonlinear effects in the dynamics of car following[END_REF], where v = v 1 and x is given up to an additive constant by

x = t [(n -1)y, (n -2)y, • • • , y, 0]. (30)
Proof. The proof is similar to that of Theorem 2. Let y ∈ R satisfying min u∈U max w∈W (α uw y+ β uw ) = v 1 . Let (ū, w) ∈ U × W such that α ū wy + β ū w = v 1 . Let x be given by [START_REF] Treiber | Congested traffic states in empirical observations and microscopic simulations[END_REF]. Then

∀n ∈ {1, 2, • • • , ν} we have [M ū wx] n + c ū w n = (α ū wy + β ū w) + x n = min u∈U max w∈W (α uw y + β uw ) + x n = min u∈U max w∈W [M uw x] n + c uw n = v 1 + x n .
We can easily check that for (u, w) ∈ U × W such that α uw = 0 and β uw = v 1 , every intervehicular distance y ∈ R satisfies the condition min u∈U max w∈W (α uw y + β uw ) = v 1 . Thus, such couples (u, w) do not count for that condition. Theorem (3) can then be announced differently. Let us denote by W u for u ∈ U the family of index sets

W u = {w ∈ W, (α uw , β uw ) = (0, v 1 )},
and by ỹ the asymptotic average car-inter-vehicular distance:

ỹ = max u∈U min w∈Wu v 1 -β uw α uw , (31)
where we use the convention a/0 = +∞ if a > 0 and a/0 = -∞ if a < 0. Then Theorem 3 tells simply that if ỹ ∈ R (i.e. -∞ < ỹ < +∞), then the dynamic system (28) admits a solution (v, x) where v = v 1 is unique, and where x is not necessarily unique and is given up to an additive constant by

x = t [(n -1)ỹ, (n -2)ỹ, • • • , ỹ, 0].
Non-uniform asymptotic car-distributions can also be obtained. Let us clarify the following three cases.

• If ∃u ∈ U , ∀w ∈ W u , α uw = 0 and β uw < v 1 , then ỹ = +∞. In this case, the distance between the first car and the other cars increases over time and goes to +∞. The asymptotic car-distribution on the road is not uniform.

• If ∀u ∈ U , ∃w ∈ W u , α uw = 0 and β uw > v 1 , then ỹ = -∞. In this case, the first car is passed by all other cars, and the distance between the first car and the other cars increases over time and goes to +∞. The asymptotic car-distribution on the road is not uniform.

• If ∀u ∈ U, ∀w ∈ W u , α uw = 0 and if min u∈U max w∈Wu β uw = v 1 , then for all x ∈ R ν , (v 1 , x) is a solution for the system [START_REF] Newell | Nonlinear effects in the dynamics of car following[END_REF]. In this case, every distribution of the cars moving all with the constant velocity v 1 is stationary.

The formula [START_REF] Treiterer | The hysteresis phenomena in traffic flow[END_REF] is the fundamental traffic diagram expressing the average inter-vehicular distance as a function of the car speed at the stationary regime. In the case where only a minimum operator is used in [START_REF] Lighthill | A min-plus derivation of the fundamental car-traffic law[END_REF], the formula (31) is reduced to the convex fundamental diagram

y = max u∈U v 1 -β u α u . ( 32
)
Example 1. In order to understand the transient traffic, let us simulate the car-dynamics [START_REF] Lighthill | A min-plus derivation of the fundamental car-traffic law[END_REF]. We take as the time unit half a second (1/2 s), and as the distance unit 1 meter (m). The parameters of the model are determined by approximating the behavior law [START_REF] Daganzo | On the variational theory of traffic flow: well-posedness, duality and applications[END_REF], with a free velocity v 0 = 14 m/ 1/2s (which is about 100 km/h) and γ = 7.5 as in [START_REF] Lenz | Multi-anticipative car-following model[END_REF]; see Figure 2. We simulate the piecewise linear car-following model associated to the approximation above.

x

1 (t) = x 1 (t -1) + v 1 (t), x n (t) = x n (t -1) + Ṽ (x n-1 (t -1) -x n (t -1)). ( 33
)
The velocity of the first car v 1 (t), t ≥ 0 is varied in the time interval [0, 1000], then fixed to the free velocity v 0 = 14 m/ 1/2s in the time interval [1000, 3000], and finally fixed on a velocity that exceeds v 0 in the remaining time [3000,7200]. The average inter-vehicular distance is then computed at every time t, and the results are shown in Figure 3.

The simple simulation we made here permits to have an idea of the traffic in the transient regime. Figure 3 shows how the average of the inter-vehicular distance is changed due to a changing in the velocity of the first car. In the right side of Figure 3, we compare the fundamental law assumed in the model with the diagram giving the average inter-vehicular distance (with respect to the number of cars) function of the velocity of the first car (a kind of macroscopic fundamental diagram). We observe that loops are obtained on that diagram in the transient traffic. The loops are interpreted by the fact that once the velocity of the first car is temporarily stationary, the velocities of the following cars, and thus also the average velocity of the cars, make some time to attain the first car velocity. It can also be interpreted by saying that even though the cars have, individually, the same response to a changing in inter-vehicular distance; their collective response depends on whether the inter-vehicular distance is increasing or decreasing. The apparition of such loops is due to the reaction time of drivers. It can also be related to the number of anticipation cars in case of multi-anticipative modeling. However, one may measure on a given section, different car-flows for the same car density (or occupancy rate) depending on the traffic acceleration or deceleration, and interpret it as the hysteresis phenomenon [START_REF] Edie | Car-Following and Steady-State Theory for Noncongested Traffic[END_REF][START_REF] Treiterer | The hysteresis phenomena in traffic flow[END_REF][START_REF] Zhang | A mathematical theory of traffic hysteresis[END_REF][START_REF] Geroliminis | Hysteresis phenomena of a macroscopic fundamental diagram in freeway networks[END_REF].

Conclusion

We proposed in this article a car-following model which extends the linear car-following model as well as the min-plus model. The stability and the stationary regimes of the model are characterized thanks to a variational formulation of the car-dynamics. This formulation, although already made with continuous-time models, it permits to clarify the stimulusresponse process in microscopic discrete-time traffic models, and to interpret it in term of stochastic optimal control. Among the important questions to be treated in the future, the impacts of heterogeneity and anticipation in driving, on the transient and stationary traffic regimes, based on the model proposed in this article.

Appendix A. Connectedness of system [START_REF] Denos | Car-Following Theory of Steady-State Traffic Flow[END_REF] Let x ∈ R ν . We denote by h : R ν → R ν the operator defined by h(x(t)) = x(t + 1), where x n (t + 1), for 1 ≤ n ≤ ν are given by the definition of the system [START_REF] Denos | Car-Following Theory of Steady-State Traffic Flow[END_REF]. That is

x n (t + 1) = min u∈U {[M u x(t)] n + c u n }, 1 ≤ n ≤ ν .
• If ∃u ∈ U , such that α u ∈ (0, 1], then for all n ∈ {1, 2, • • • , ν}, there exists an arc, on the graph associated to h, going from n -1 to n (n being cyclic in {1, 2, • • • , ν}). Indeed,

x n (t + 1) = (1 -α u )x n (t) + α u x n-1 (t) + β u .
Then since α u > 0, we get:

lim ν→∞ h n (νe n-1 ) = lim ν→∞ [α u ν + β u ] = ∞.
where e n-1 denotes the (n -1) th vector of the canonic basis of R ν . Therefore the graph associated to h is strongly connected.

• If ∀u ∈ U, α u = 0, then we can easily check that all arcs of the graph associated to h are loops. Hence that graph is not strongly connected.

Appendix B. Duality in traffic modeling

We show in this appendix the duality in traffic modeling of using the three functions

• n(t, x): cumulated number of cars passed through position x from time 0 up to time t.

• x(n, t): position of car n at time t (or cumulated traveled distance of car n from time 0 up to time t).

• t(n, x): the time that car n passes by position x.

We base on the Lagrangian traffic descriptions given in the introduction, and give the equivalent traffic descriptions by using the functions n(t, x) and t(n, x), in both cases of discretetime and continuous-time modeling.

1. In Eulerian traffic descriptions, the function n(t, x) is used. The partial derivative ∂ t n(t, x) expresses the car-flow q(t, x) at time t and position x, while -∂ x n(t, x) expresses the car-density ρ(t, x) at time t and position x. The equality ∂ tx n(t, x) = ∂ xt n(t, x) gives the car conservative law:

∂ t k(t, x) + ∂ x q(t, x) = 0. (B.1)
The first order traffic model LWR [START_REF] Lighthill | A min-plus derivation of the fundamental car-traffic law[END_REF][START_REF] Richards | Shock waves on the highway[END_REF] supposes the existence of a fundamental diagram of traffic giving the car-flow q as a function of the car-density ρ at the stationary regime, through a function Q e , and that the diagram also holds for the transient traffic : q(t, x) = Q e (ρ(t, x)). Also discrete-time and -space Eulerian traffic models exist. Those models are in general derived from Petri nets as in [START_REF] Baccelli | Synchronization and Linearity[END_REF][START_REF] Farhi | Modélisation Minplus et Commande du Trafic de Villes Régulières[END_REF][START_REF] Farhi | The traffic phases of road networks[END_REF]. For example the traffic on a 1-lane road without passing can be described by n(t, x) = min{a x + n(tτ x , xδx), āx+δx + n(t -τx+δx , x + δx)}, (B.4) where a x denotes the number of cars being in (xδx, x) at time zero.

τ x denotes the free travel-time of a car from xδx to x.

āx denotes the space non occupied by cars in (x-δx, x) at time zero. If we denote by c x the maximum number of cars that can be in (xδx, x), then we have simply āx = c xa x .

τx denotes the reaction time of drivers in (xδx, x). That is the time interval between the time when (xδx, x) is free of cars and the time when a car being in (x -2δx, xδx) starts moving to (xδx, x). If we denote by T x the total traveling time (reaction time + moving time) of a car from (x -2δx, xδx) to (xδx, x), then we have simply τx = T xτ x .

2. By using the variable t(n, x), the first order differentiation of t(n, x) with respect to n, denoted z is z(n, x) = -(t(n -1, x)t(n, x)), while the derivative of t(n, x) in x, denoted r is r(n, x) = ∂ x t(n, x). We notice here that z and r are interpreted respectively as the inverse flow and the inverse velocity of vehicles. A conservation law (of time) is then written ∂ where ∆r(n, x) = r(n -1, x)r(n, x). Note that, having a fundamental diagram v = V e (q) giving the stationary velocity as a function of the stationary flow, the diagram R e is nothing but R e (z) = 1/V e (1/z). Discrete-time-and-space modeling with the function t(n, x) also exist. The models are also inspired from Petri net, and dual dynamics to (B.4) are obtained. For example, using the same notations as in (B.4), the traffic on a 1-lane road without passing can be described by t(n, x) = max{τ x + t(na x , xδx), τx+δx + t(n + āx+δx , x + δx)}. (B.7)

Note here that a max operator is used rather than a min one. For more details on the duality of (B.4) and (B.7) and the meanings in term of Petri nets, event graphs and min-plus or max-plus algebras, see [START_REF] Baccelli | Synchronization and Linearity[END_REF].

  uw + β uw ρ}.

Figure 1 :

 1 Figure 1: The effect of the stability condition α uw ∈ [0, 1] on the shape of the fundamental diagram.

Figure 2 :

 2 Figure 2: Approximation of the behavioral law (6) with a piecewise linear curve.

Figure 3 :

 3 Figure 3: Simulation results. On the left-side: the first car velocity (solid line), and the average inter-vehicular distance (dash line) functions of time. On the right side: the approximation of the behavior law (6) (dash line), and the average inter-vehicular distance obtained by simulation in function of the velocity of the first car (solid line).

(B. 2 )

 2 Then (B.1) and (B.2) give the well known LWR model∂ t ρ(t, x) + ∂ x ρ(t, x)Q ′ e (ρ) = 0. (B.3)

  x z(n, x) + r(n, x)r(n -1, x) = 0. (B.5) The law (B.5) combined with the fundamental diagram r = R e (z) gives the model ∂ x r(n, x) = R ′ (z(n, x))∆r(n, x), (B.6)

A dynamic system x(t) = f (x(t -1)) is additive homogeneous of degree 1 if f is so, that is if ∀x ∈ R n , ∀λ ∈ R, f (λ + x) = λ + f (x).

A dynamic system x(t) = f (x(t -1)) is monotone if f is so, that is if ∀x 1 , x 2 ∈ R n , x 1 ≤ x 2 ⇒ f (x 1 ) ≤ f (x 2 ), where the order ≤ is pointwise in R n .

A dynamic system x(t) = f (x(t -1)) is non expansive if f is so, that is if there exists a norm || • || in R n such that ∀x 1 , x 2 ∈ R n , ||f (x 2 )f (x 1 )|| ≤ ||x 2x 1 ||.

An additive homogeneous of degree 1 and monotone dynamic system x(t) = f (x(t -1)) with x ∈ R n is connected if its associated graph is strongly connected. The graph associated to that dynamic system is the graph with n nodes and whose arcs are determined as follows. There exists an arc from a node i to a node j if lim ν→∞ f j (νe i ) = ∞, where e i denotes the i th vector of the canonic basis of R n .

We mean here M u ij ≥ 0, ∀i, j and j M u ij = 1, ∀i.