Marie C F Favre
email: 1.marie.favre@isima.fr2.wagler@isima.fr

Annegret K Wagler

Reconstructing extended Petri nets with priorities -handling priority conicts revisited

Keywords: Petri nets, time-series data, priority relations, control-arcs Résumé Réseaux de Petri, données de séries temporelles, relations de priorités, arêtes de control

This work aims at reconstructing Petri net models for biological systems from experimental time-series data. The reconstructed models shall reproduce the experimentally observed dynamic behavior in a simulation. For that, we consider Petri nets with priority relations among the transitions and control-arcs, to obtain additional activation rules for transitions to control the dynamic behavior.

An integrative reconstruction method, taking both priority relations and controlarcs into account, was proposed by Favre and Wagler in 2013. Here, we detail the aspect of choosing priorities and control-arcs such that dynamic conicts can be resolved to nally arrive at the experimentally observed behavior.

Introduction

Systems biology aims at the integrated experimental and theoretical analysis of molecular or cellular networks to achieve a holistic understanding of biological systems and processes. To gain the required insight into the underlying biological processes, experiments are performed and experimental data are interpreted in terms of models. Depending on the biological aim, the type and quality of the available data, dierent types of mathematical models are used and corresponding reconstruction methods have been developed. Our work is dedicated to Petri nets which turned out to coherently model both static interactions in terms of networks and dynamic processes in terms of state changes, see e.g. [START_REF] Koch | Petri nets[END_REF][START_REF] Pinney | Petri net representations in systems biology[END_REF].

In fact, a network P = (P, T, A, w) reects the involved components by places p ∈ P and their interactions by transitions t ∈ T , linked by weighted directed arcs (p, t), (t, p) ∈ A. Each place p ∈ P can be marked with an integral number x p of tokens dening a system state x ∈ Z |P | + , i.e., we obtain X := {x ∈ Z |P | : x p ≥ 0} as set of potential states. A transition t ∈ T is enabled in a state x if x p ≥ w(p, t) for all p with (p, t) ∈ A, we denote the set of all such transitions by T (x). Switching t ∈ T (x) yields a successor state succ(x) = x with x p = x pw(p, t) for all (p, t) ∈ A and x p = x p + w(t, p) for all (t, p) ∈ A. Dynamic processes are represented by sequences of such state changes.

Our central question is to reconstruct models of this type from experimental time-series data by means of an exact, exclusively data-driven approach. This approach takes as input a set P of places and discrete time-series data X given by sequences (x 0 , x 1 , . . . , x k ) of experimentally observed system states. The goal is to determine all Petri nets (P, T, A, w) that are able to reproduce the data, i.e., that perform for each x j ∈ X the experimentally observed state change to x j+1 ∈ X in a simulation. Hence, in contrast to the normally used stochastic simulation, we require that for states where at least two transitions are enabled, the decision between the alternatives is not taken randomly, but a specic transition is selected. Thus, (standard) Petri nets have to be equipped with additional activation rules to force the switching of special transitions (to reach x j+1 from x j ), and to prevent all others from switching. For that, dierent types of additional activation rules are possible.

On the one hand, in [START_REF] Durzinsky | Reconstruction of extended Petri nets from time-series data by using logical control functions[END_REF] the concept of control-arcs is used to represent catalytic or inhibitory dependencies. An extended Petri net P = (P, T, (A ∪ A R ∪ A I ), w) is a Petri net which has, besides the (standard) arcs in A, two additional sets of so-called control-arcs: the set of read-arcs A R ⊂ P × T and the set of inhibitor-arcs A I ⊂ P × T ; we denote the set of all arcs by A = A ∪ A R ∪ A I . Here, a transition t ∈ T (x) coupled with a read-arc (resp. an inhibitor-arc) to a place p ∈ P can switch only if at least w(p, t) tokens (resp. less than w(p, t) tokens) are present in p; we denote by T A (x) the set of all such transitions.

On the other hand, in [START_REF] Marwan | A mathematical approach to solve the network reconstruction problem[END_REF][START_REF] Torres | Encoding the dynamics of deterministic systems[END_REF][START_REF] Wagler | Prediction of network structure[END_REF] priority relations among the transitions of a network are employed to reect the rate of the corresponding reactions, where the fastest reaction has highest priority and, thus, is taken. In Marwan et al. [START_REF] Marwan | A mathematical approach to solve the network reconstruction problem[END_REF] it is proposed to model such priorities with the help of partial orders O on the transitions. We call (P, O) an (extended) Petri net with priorities, if P = (P, T, A, w) is an (extended) Petri net and O a priority relation on T . Priorities can prevent enabled transitions from switching: For each state x, a transition t ∈ T A (x) is allowed to switch only if there is no other enabled transition in T A (x) with higher priority; we denote by T A,O (x) the set of all such transitions.

To enforce a deterministic behavior, T A,O (x) must contain at most one element for each x ∈ X to enforce that x has a unique successor succ X (x), see [START_REF] Torres | Encoding the dynamics of deterministic systems[END_REF] for more details. For our purpose, we consider a relaxed condition, namely that T A,O (x) contains at most one element for each experimentally observed state x ∈ X , but T A,O (x) may contain several elements for non-observed states

x ∈ X \ X . We call such Petri nets X -deterministic.

Based on earlier results in [START_REF] Durzinsky | Reconstruction of extended Petri nets from time-series data by using logical control functions[END_REF][START_REF] Durzinsky | A combinatorial approach to reconstruct Petri nets from experimental data[END_REF][START_REF] Durzinsky | An algorithmic framework for network reconstruction[END_REF][START_REF] Marwan | A mathematical approach to solve the network reconstruction problem[END_REF][START_REF] Wagler | Prediction of network structure[END_REF], we proposed in [START_REF] Favre | Reconstructing X -deterministic extended Petri nets from experimental time-series data X (extended abstract)[END_REF] an integrative method to reconstruct all X -deterministic extended Petri nets with priorities tting given experimental time-series data X (see Section 2). The contribution of this paper is to detail the aspect of choosing priorities and control-arcs: we discuss the mathematical structures and underlying combinatorial problems which allow us to eectively resolve dynamic conicts in order to nally arrive at the experimentally observed dynamic behavior (see Section 3). We close with some concluding remarks and lines of future research.

Reconstructing extended Petri nets with priorities

We describe the input, the main ideas, and the output of our approach from [START_REF] Favre | Reconstructing X -deterministic extended Petri nets from experimental time-series data X (extended abstract)[END_REF].

Input. A set of components P (standing for proteins, enzymes, genes, receptors or their conformational states, later represented by the set of places) is chosen which is expected to be crucial for the studied phenomenon.

To perform an experiment, one rst triggeres the system in some state x 0 (by external stimuli like the change of nutrient concentrations or the exposition to some pathogens), to generate an initial state x 1 . Then the system's response to the stimulation is observed and the resulting state changes are measured for all components at certain time points. This yields a sequence of (discrete or discretized) states x j ∈ Z |P | reecting the time-dependent response of the system to the stimulation in x 1 , which typically terminates in a terminal state x k where no further changes are observed. The corresponding experiment is

X (x 1 , x k ) = (x 0 ; x 1 , . . . , x k ).
Several experiments starting from dierent initial states in a set X ini ⊆ X , reporting the observed state changes for all components p ∈ P at certain time points, and ending at dierent terminal states in a set X term ⊆ X describe the studied phenomenon, and yield experimental time-series data of the form

X = {X (x 1 , x k ) : x 1 ∈ X ini , x k ∈ X term }.
Thus, the input of the reconstruction approach is given by (P, X ).

Example 1. As running example, we will consider experimental biological data from the light-induced sporulation of Physarum polycephalum as in [START_REF] Favre | Reconstructing X -deterministic extended Petri nets from experimental time-series data X (extended abstract)[END_REF][START_REF] Wagler | Prediction of network structure[END_REF]. In P. polycephalum plasmodia, the photoreceptor involved in the control of sporulation Spo is a protein which occurs in two stages P F R and P R . The developmental decision of starving P. polycephalum plasmodia to enter the sporulation pathway is controlled by environmental factors like visible light [START_REF] Starostzik | Functional mapping of the branched signal transduction pathway that controls sporulation in Physarum polycephalum[END_REF]. If the darkadapted form P F R absorbs far-red light F R, the receptor is converted into its red-absorbing form P R , which causes sporulation [START_REF] Lamparter | Spectroscopic detection of a phytochrome-like photoreceptor in the myxomycete physarum polycephalum and the kinetic mechanism for the photocontrol of sporulation[END_REF]. If P R is exposed to red light R, it is photoconverted back to the initial stage P F R , which prevents sporulation. The experimental setting consists of

P = {F R, R, PF R, PR, Spo}, X (x 1 , x 3 ) = (x 0 ; x 1 , x 2 , x 3 ), X ini = {x 1 , x 4 }, X (x 4 , x 0 ) = (x 2 ; x 4 , x 0 ), X term = {x 3 , x 0 }
as input for the algorithm, we present all observed states schematically in Fig 1 .   x

      x F R x R x PF R x PR x Spo       x 0       0 0 1 0 0       x 1       1 0 1 0 0       x 2       0 0 0 1 0       x 3       0 0 0 1 1             0 1 0 1 0       x 4 FR R d 1 d 2 d 4
Fig. 1. A scheme illustrating the experimental time-series data described in Exp. 1 concerning the light-induced sporulation of Physarum polycephalum, where the entries of the state vectors are interpreted as shown on the left (dashed arrows represent stimulations x 0 → x 1 , solid arrows responses x j → x j+1 ).

For a successful reconstruction, the data X need to satisfy two properties: reproducibility and monotonicity.

The data X are reproducible if for each x j ∈ X there is a unique observed successor state succ X (x j ) = x j+1 ∈ X .

Reproducibility is obviously necessary and can be ensured by a preprocessing step [START_REF] Wagler | Preprocessing for network reconstruction: Feasibility test and handling infeasibilty[END_REF].

Note that a state x j ∈ X and its observed successor succ X (x j ) = x j+1 ∈ X are not necessarily also consecutive system states (this depends on the chosen time points to measure the states in X ). Instead, x j+1 may be obtained from x j by a switching sequence of some length, where the intermediate states are not reported in X . The data X are monotone if for each pair (x j , x j+1 ) ∈ X , the values of the elements do not oscillate in the possible intermediate states between

x j and x j+1 . It was shown in [START_REF] Durzinsky | A combinatorial approach to reconstruct Petri nets from experimental data[END_REF] that monotonicity has to be required, too (which is equivalent to demand that all essential responses are indeed reported in X ).

Output. An extended Petri net with priorities (P, O) with P = (P, T, A, w) ts the given data X when it is able to perform every observed state change from

x j ∈ X to x j+1 ∈ X . This can be interpreted as follows. With P, an incidence matrix M ∈ Z |P |×|T | is associated, where each row corresponds to a place p ∈ P of the network, and each column M •t to the update vector r t of a transition t ∈ T :

r t p = M pt :=      -w(p, t) if (p, t) ∈ A, +w(t, p) if (t, p) ∈ A, 0 otherwise.
Reaching x j+1 from x j by a switching sequence using the transitions from a subset T ⊆ T is equivalent to obtain the state vector x j+1 from x j by adding the corresponding columns M •t of M for all t ∈ T :

x j + t∈T M •t = x j+1 .
T has to contain enough transitions to perform all experimentally observed switching sequences. The underlying standard network P = (P, T, A, w) is conformal with X if, for any two consecutive states x j+1 ∈ X , the linear equation system x j+1x j = M λ has an integral solution λ ∈ N |T | such that λ is the incidence vector of a sequence (t

(P, O) is X -deterministic if {t l } = T A,O (y l )
holds for all y l .

The desired output of the reconstruction approach consists of the set of all X -deterministic extended Petri nets (P, O) (all having the same set P of places as part of the input).

Example 2. We represent in Fig. 3 (page 10) the 8 alternative X -deterministic extended Petri nets tting the experimental data X from our running example.

We now briey sketch the reconstruction procedure.

Representation of observed responses. As initial step, extract the observed changes of states from the experimental data. For that, dene the set

D := d j = x j+1 -x j : x j+1 = succ X (x j ) ∈ X .
Generating the complete list of all X -deterministic extended Petri nets P = (P, T, A, w) includes nding the corresponding standard networks and their incidence matrices M ∈ Z |P |×|T | . Hence, the rst step is to describe the set of potential columns of M . Due to monotonicity [START_REF] Durzinsky | A combinatorial approach to reconstruct Petri nets from experimental data[END_REF], it suces to represent any d j ∈ D using sign-compatible vectors from the following set only:

Box(d j ) =    r ∈ Z |P | : 0 ≤ r p ≤ d p if d j p > 0 d p ≤ r p ≤ 0 if d j p < 0 r p = 0 if d j p = 0    \ {0}.
Next, we determine for any d j ∈ D, the set Λ(d j ) of all integral solutions of

d j = r t ∈ Box(d j ) λ t r t , λ t ∈ Z + ,
and for each λ ∈ Λ(d j ), the (multi-)set R(d j , λ) = {r t ∈ Box(d j ) : λ t = 0} of update vectors used for this solution λ. By construction, Box(d j ) and Λ(d j ) are always non-empty since d j itself is always a solution due to reproducibility [START_REF] Favre | Reconstructing X -deterministic extended Petri nets from experimental time-series data X (extended abstract)[END_REF].

Every permutation π = (r t1 , . . . , r tm ) of the elements of a set R(d j , λ) gives rise to a sequence of intermediate states

x j = y 1 , y 2 , ..., y m , y m+1 = x j+1 with σ = σ π,λ (x j , d j ) = (y 1 , r t1 ), (y 2 , r t2 ), . . . , (y m , r tm )
which induces a priority relation O σ since transition t i resulting from r ti is supposed to have highest priority in y i for 1 ≤ i ≤ m.

Example 3. For the running example we obtain as sequences

x 0 x 1 x 2 x 3 x 4 x 5 x 6 x 0 x 2 FR R d 1 d 2 d 4 r 1 r 2 r 3 r 4 r 1 r 2 r 3 r 4 with x 5 = (1, 0, 0, 1, 0) T and x 6 = (0, 1, 1, 0, 0) T .
Sequences and their conicts. Two sequences σ and σ are in priority conict if there are update vectors r t = r t and intermediate states y, y such that t, t ∈ T (y) ∩ T (y ) and (y, r t ) ∈ σ but (y , r t ) ∈ σ (since this implies t > t in O σ but t > t in O σ ). We have a weak (resp. strong) priority conict if y = y (resp. y = y ) which can (resp. cannot) be resolved by adding control-arcs.

Priority conict graph. Construct a priority conict graph

G = (V D ∪V term , E D ∪ E W ∪ E S )
whose nodes correspond to all possible sequences σ π,λ (x j , d j ) and whose edges reect weak and strong priority conicts:

-V D contains the sequences σ π,λ (x j , d j ) for all x j ∈ X \ X term and the difference vector d j = succ X (x i )x i , for all λ ∈ Λ(d j ) and all permutations π of R(d j , λ). -V term contains for all x k ∈ X term the trivial sequence σ(x k , 0).

-E D contains all edges between two sequences σ, σ stemming from the same dierence vector -E S (resp. E W ) reects all SPCs (resp. WPCs) between sequences σ, σ stemming from distinct dierence vectors.

The edges in E D induce a clique partition Q of V D in as many cliques 3 as there are observed states in X \X term resp. dierence vectors in D:

V D = Q 1 ∪. . .∪Q |D| . Moreover, each node in V term corresponds to a clique of size 1, so that G is partitioned into |X | many cliques.
For illustration, we present in Fig. 2 the WPCs and SPCs between sequences of our running example.

Selection of suitable sequences. In G, all node subsets S are generated that select exactly one sequence σ π,λ (x j , d j ) per dierence vector d j ∈ D such that no SPCs occur between the selected sequences. The set of all such solutions S ∪ V term can be encoded by all vectors x ∈ {0, 1} |V D ∪Vterm| satisfying

σ∈Qj x σ = 1 ∀Q j ∈ Q (1a) x σ = 1 ∀σ ∈ V term (1b) x σ + x σ ≤ 1 ∀σσ ∈ E S (1c) x σ ∈ {0, 1} ∀σ ∈ V D ∪ V term . (1d) Q 3 Q 1 Q 3 Q 2 Q 0 Q 4 σ(x 1 , d 1 ) σ 2 (x 1 , d 1 ) σ 3 (x 1 , d 1 ) σ(x 3 , 0) σ(x 2 , d 2 ) σ(x 0 , 0) σ(x 4 , d 4 ) σ 2 (x 4 , d 4 ) σ 3 (x 4 , d 4 )
Fig. 2. The priority conict graph resulting from the running example, where bold edges indicate SPCs, thin edges WPCs and gray boxes the clique partition Q.

3.

A clique is a subset of mutually adjacent nodes.

Example 4. From G shown in Fig. 2, we obtain as feasible subsets S i ∪ V term :

S1 = {σ1(x 1 , d 1 ), σ1(x 2 , d 2 ), σ1(x 4 , d 4 )}, S3 = {σ1(x 1 , d 1 ), σ1(x 2 , d 2 ), σ3(x 4 , d 4 )}, S2 = {σ3(x 1 , d 1 ), σ1(x 2 , d 2 ), σ1(x 4 , d 4 )}, S4 = {σ3(x 1 , d 1 ), σ1(x 2 , d 2 ), σ3(x 4 , d 4 )}.
Construction of standard networks, inserting control-arcs. Each subset S gives rise to a standard network P S = (P, T S , A S , w) which is conformal with X and can be made X -deterministic by inserting appropriate control-arcs and combining the priority relations O σ ∀σ ∈ S. Let P (y, y ) = {p ∈ P : y p = y p }:

-we obtain the columns of the incidence matrix M S of P S by taking the union of all sets R(d j , λ) of the sequences σ = σ π,λ (x j , d j ) selected by σ ∈ S; -for each WPC between σ, σ ∈ S involving update vectors r t = r t and intermediate states y = y , include either a read-arc (p, t) ∈ A R with weight w(p, t) > y p for some p ∈ P (y, y ) with y p > y p or an inhibitor-arc (p, t) ∈ A I with weight w(p, t) < y p for some p ∈ P (y, y ) with y p < y p to disable transition t resulting from r t at y , -for each σ ∈ S,

dene O σ = {t i > t : t ∈ T A S ∪A R ∪A I (y i ) \ {t i }, 1 ≤ i ≤ m}
and let O S = σ∈S O σ be the studied partial order. This implies nally that every extended network P S = (P, T S , A S ∪ A R ∪ A I , w) together with the partial order O S is X -deterministic, see [START_REF] Favre | Reconstructing X -deterministic extended Petri nets from experimental time-series data X (extended abstract)[END_REF] for details.

Example 5. We apply the method only to the feasible set S 4 ∪V term from Exp. 4.

The standard network P S4 = (P, T S4 , A S4 ) has T S4 = {r 1 , r 2 , d 2 , r 3 , r 4 }. There are four WPCs between sequences of S 4 : WPC1 between σ 3 (x 1 , d 1 ) and σ(x 0 , 0) due to r 2 , 0 ∈ T (x 1 ) ∩ T (x 0 ) WPC2 between σ(x 2 , d 2 ) and σ 3 (x 4 , d 4 ) due to d 2 , r 4 ∈ T (x 2 ) ∩ T (x 4 ) WPC3 between σ(x 2 , d 2 ) and σ(x 0 , 0) due to d 2 , 0 ∈ T (x 2 ) ∩ T (x 0 ) WPC4 between σ(x 3 , 0) and σ 3 (x 4 , d 4 ) due to 0, r 4 ∈ T (x 3 ) ∩ T (x 4 ) For WPC1, we obtain P (

x 1 , x 0 ) = {F R}, by x 1 F R > x 0 F R , the read-arc (F R, r 2 ) disables r 2 at x 0 ∈ X τ . For WPC2, we have P (x 2 , x 4 ) = {R}, by x 2 R < x 4 R ,
the read-arc (R, r 4 ) disables r 4 at x 2 or, alternatively, the inhibitor-arc (R, d 2 ) disables d 2 at x 4 . For WPC3, we obtain P (

x 2 , x 0 ) = {P F R , P R }, to disable d 2 at x 0 ∈ X τ , by x 2 P R > x 0 P R , the read-arc (P R , d 2 ) or, by x 2 P F R < x 0 P F R
, the inhibitor-arc (P F R , d 2 ) can be used. For WPC4, we have

P (x 3 , x 4 ) = {R, Spo}, to disable r 4 at x 3 ∈ X τ , by x 4 R > x 3 R , the read-arc (R, r 4 ) or, by x 4 Spo < x 3
Spo , the inhibitor-arc (Spo, r 4 ) can be used. All possible control-arcs have weight 1.

The priority relation O 4 = {(r 2 > r 1 ), (r 4 > r 3 )} is required, the resulting 8 alternative X -deterministic extended Petri nets are presented in Fig. 3.

PR F R R Spo PF R r 1 r 2 d 2 r 4 r 3 PR F R R Spo PF R r 1 r 2 d 2 r 4 r 3 PF R R F R Spo PR r 4 r 3 d 2 r 1 r 2 (a) (b) (c) PF R R F R Spo PR r 4 r 3 d 2 r 1 r 2 PR F R R Spo PF R r 1 r 2 d 2 r 4 r 3 PR F R R Spo PF R r 1 r 2 d 2 r 4 r 3 (d) (e) (f ) PF R R F R Spo PR r 4 r 3 d 2 r 1 r 2 PF R R F R Spo PR r 4 r 3 d 2 r 1 r 2 (g) (h)
Fig. 3. The eight X -deterministic extended Petri nets resulting from PS 4 .

Handling and resolving priority conicts

In this section, we discuss the underlying mathematical structures and combinatorial problems of the two main reconstruction steps.

The priority conict graph and selecting sequences

By construction of the priority conict graph G = (V D ∪V term , E D ∪E W ∪E S ) and the selection of S ⊆ V D according to system (1), we note the following. Every solution S∪V term of (1) corresponds to a stable set 4 in the strong priority conict graph G S = (V D ∪ V term , E D ∪ E S ). In particular, the two constraints (1a) and (1b) enforce to select exactly one node from each of the cliques Q 1 , . . . Q |D| and all nodes from V term , resp. Since Q 1 , . . . Q |D| together with the nodes from V term 4. A stable set is a subset of pairwise non-adjacent nodes. built a clique partition Q of G S by construction, we aim at nding a stable set S ∪ V term of the same size as the clique cover number χ(G S ) is. In general, not every graph G has a stable set of size χ(G), but making use of the reproducibility of the given data X , we can ensure that at least the selection of all sequences σ 1 (x j , d j ) = ((x j , d j )) in G S , called canonical solution S 1 , always satises (1).

This implies:

Theorem 1. G S has at least one stable set of size χ(G S ) and, thus, system [START_REF] Berge | Hypergraphs[END_REF] is always feasible.

Finding all solutions of (1) means to enumerate all stables sets of size χ(G S ) in G S , i.e., all maximum stable stets of G S . We next discuss which nodes of G S can never enter any solution of (1) and propose a corresponding reduction of G S . Lemma 1. A node σ ∈ V D can never be selected for any solution S if there is a clique Q in Q so that σ is in strong conict with all sequences σ ∈ Q.

Corollary 1. No σ ∈ V D can be selected for any solution S if the sequence contains a terminal state as intermediate state.

This leads to the following reduction of the priority conict graph: We obtain the reduced priority conict graph

G = (V D ∪ V term , E D ∪ E S ∪ E W ) from G by
recursively removing from V D all nodes which are completely joined to a clique in Q and the edges being adjacent to them. Example 6. The reduced priority conict graph G of the running example can be obtained as follows: We remove σ 2 (x 1 , d 1 ) since it is in SPC with (the only sequence σ(x 0 , 0)) in Q 0 due to r 2 , 0 ∈ T (x 0 ). We omit σ 2 (x 4 , d 4 ) since it is in SPC with (the only sequence σ(x 2 , d 2 )) in Q 2 due to d 2 , r 4 ∈ T (x 2 ).

Furthermore, let G S = (V D ∪ V term , E D ∪ E S ) be the reduced strong priority conict graph. We nally obtain from the above considerations: Theorem 2. The sets of maximum stable sets in G S and G S are equal.

Hence, we can also reduce system (1) based on G S and obtain the same solutions.

Interpretation of resolving WPCs as set cover problem

For each WPC between two sequences σ, σ , there are update vectors r t = r t and intermediate states y = y with t, t ∈ T (y) ∩ T (y ) s.t. (y, r t ) ∈ σ but (y , r t ) ∈ σ . We denote this for short by WPC(σ, σ ). This priority conict can be solved by adding control-arcs which -either turn r t into a transition t which is disabled at y (then t > t forces t to switch in y whereas only t is enabled at y ), -or turn r t into a transition t which is disabled at y (then t > t forces t to switch in y whereas only t is enabled at y). For that, consider for each WPC the set P (y, y ) of places where y and y dier.

Remark 1. If one of y, y is a terminal state, say y , one of the alternatives is not possible, then t has to be disabled at y and t > t = 0 holds automatically. Note that if y = y then P (y, y ) = ∅ follows which is the reason why SPCs cannot be resolved by adding control-arcs.

Let CA(σ, σ ) be the set of all possible read-arcs that can resolve W P C(σ, σ ), involving r t = r t and states y = y by either disabling t at y or t at y then CA(σ, σ ) contains:

-a read-arc (p, t) ∈ A R with weight w(p, t) > y p ∀p ∈ P (y, y ) with y p > y p , -an inhibitor-arc (p, t) ∈ A I with w(p, t) < y p ∀p ∈ P (y, y ) with y p < y p , -a read-arc (p, t ) ∈ A R with weight w(p, t ) > y p ∀p ∈ P (y, y ) with y p > y p , -an inhibitor-arc (p, t ) ∈ A I with w(p, t ) < y p ∀p ∈ P (y, y ) with y p < y p . Lemma 2. Inserting in P S any non-empty subset A ⊆ CA(σ, σ ) resolves the weak priority conict WPC(σ, σ ).

We next discuss which subsets of control-arcs for all WPCs are suitable to turn P S into a catalytical conformal extended Petri net. On the one hand, a controlarc (p, t) ∈ CA(σ, σ ) might disable t at a state in a sequence σ ∈ S \σ, σ where t is supposed to switch. In this case, (p, t) has to be removed from CA(σ, σ ), resulting in a reduced set CA S (σ, σ ). On the other hand, one control-arc may resolve several WPCs in P S if the corresponding sets CA S (σ, σ ) intersect.

This motivates the following consideration: Introduce one variable z (p,t) ∈ {0, 1} for each possible control-arc (p, t) ∈ CA S (σ, σ ) for all WPCs in P S . Construct a 0/1-matrix A S whose columns correspond to all those variables (resp. control-arcs) and whose rows encode the incidence vectors of the sets CA S (σ, σ ) for all WPCs in P S . Then any 0/1-solution z of A S z ≥ 1 encodes a suitable set of control-arcs resolving all WPCs in P S and, thus, a hitting set or cover of A S . Lemma 3. Any cover of A S corresponds to a set of control-arcs making P S catalytical conformal with X .

According to [START_REF] Wagler | On minimality and equivalence of Petri nets[END_REF], we are only interested in nding minimal models tting X , where minimality is interpreted in the sense that all non-minimal models contain another one also tting the data. Based on results in [START_REF] Wagler | On minimality and equivalence of Petri nets[END_REF], we can show: Lemma 4. Non-minimal covers of A S yield extended Peri nets with unnecessary control-arcs and, thus, being not minimal.

Hence, it suces to only consider minimal covers of A S but, for the sake of completeness, we are interested in nding all of them. The set of all minimal covers of a matrix A is called its blocker b(A). This nally implies: Theorem 3. All minimal catalytical conformal extended Petri nets based on P S can be obtained by computing the blocker b(A S ).

Example 7. For the feasible set S 4 ∪ V term , we obtain as matrix A S4 :

(FR,r 2 ) ∈ AR (PF R, d 2 ) ∈ AI (PR, d 2 ) ∈ AR (Spo,r 4 ) ∈ AI (R,r 4 ) ∈ AR (R,d 2 ) ∈ AI WPC1 X WPC2 X X WPC3 X X WPC4 X X
The 15 covers of A S4 are shown in the table below. The 8 X -deterministic extended Petri nets from Fig. 3 correspond to the 8 covers (a-h) of A S4 where we chose one by one, one control-arc to solve one WPC. Note that P e , P f , P g and P h

are not minimal since they contain unnecessary control-arcs, whereas the minimal covers from b(A S4 ) correspond to the four minimal solutions P a , P b , P c , P d . Note that b(A S ) is non-empty if and only if none of the sets CA S (σ, σ ) is empty. Finally, one can show that b(A S1 ) = ∅ always holds for the canonical solution S 1 , so there is at least one catalytical conformal network for any given X . By construction, all catalytic conformal extended Petri nets based on P S can be made X -deterministic by taking all the priorities O σ for all σ ∈ S.

(F R, r 2 ) ∈ AR (PF R, d 2 ) ∈ AI (PR, d 2 ) ∈ AR (Spo, r 4 ) ∈ AI (R, r 4 ) ∈ AR (R, d 2 ) ∈ AI Pa WCP1 WCP3 WCP4 WCP2 Pb WCP1 WCP3 WCP2

Concluding Remarks

In [START_REF] Favre | Reconstructing X -deterministic extended Petri nets from experimental time-series data X (extended abstract)[END_REF], an integrative method to reconstruct all X -deterministic extended Petri nets with priorities tting given experimental time series data is proposed.

We detailed here the aspect of handling priority conicts and choosing controlarcs by discussing the underlying mathematical structures and related combinatorial problems, feasibility as well as minimality issues. For that, we interpreted -the selection of suitable sequences from the priority conict graph G S as the problem of nding all stable sets S of size χ(G S ) to obtain all conformal standard networks P S (Thm. 1); -resolving all WPCs in a standard network P S as hitting set or set cover problem involving a matrix A S whose blocker b(A S ) yields all minimal catalytic conformal extended Petri nets based on P S (Thm. 3).

These interpretations in terms of two classical combinatorial problems open us

the possibility to apply eective techniques known from the literature to compute the blocker of a matrix [START_REF] Berge | Hypergraphs[END_REF][START_REF] Eiter | Computational aspects of monotone dualization: A brief survey[END_REF][START_REF] Murakami | Ecient algorithms for dualizing large-scale hypergraphs[END_REF] or to enumerate all maximal stable sets of a graph [START_REF] Johansson | Nlc2-decomposition in polynomial time[END_REF][START_REF] Tsukiyama | A new algorithm for generating all the maximal independent sets[END_REF], which include all maximum ones.

Moreover, we can ensure the existence of at least one conformal network outgoing from reproducible data (Thm. 1), since we allow the occurrence of WPCs in P S which can be later resolved by inserting control-arcs. In contrast, not using control-arcs does not always result in a solution [START_REF] Marwan | A mathematical approach to solve the network reconstruction problem[END_REF][START_REF] Durzinsky | An algorithmic framework for network reconstruction[END_REF], whereas not using priorities may force the insertion of articial control-arcs [START_REF] Durzinsky | Reconstruction of extended Petri nets from time-series data by using logical control functions[END_REF].

Concluding Remarks: Long version

In [START_REF] Favre | Reconstructing X -deterministic extended Petri nets from experimental time-series data X (extended abstract)[END_REF], an integrative method to reconstruct all X -deterministic extended Petri nets with priorities tting given experimental time series data is proposed.

We detailed here the aspect of handling priority conicts and choosing controlarcs by discussing the underlying mathematical structures and related combinatorial problems, feasibility as well as minimality issues. For that, we interpreted -the selection of suitable sequences from the priority conict graph as the problem of nding all stable sets S of size χ(G S ) in the priority conict graph G S to obtain all conformal standard networks P S ; -resolving WPCs as set cover problem involving a matrix A S encoding all possible control-arcs to resolve all WPCs in a standard network P S and showed that computing the blocker b(A S ) yields all minimal catalytic conformal extended Petri nets based on P in terms of two well-known combinatorial optimization problems open us the possibility to apply eective techniques known from the literature, e.g., the classical algorithm of Berge [START_REF] Berge | Hypergraphs[END_REF] or one of its recent, more ecient variants [START_REF] Eiter | Computational aspects of monotone dualization: A brief survey[END_REF][START_REF] Murakami | Ecient algorithms for dualizing large-scale hypergraphs[END_REF] to compute the blocker of a matrix, or algorithms to enumerate all maximal stable sets of a graph [START_REF] Johansson | Nlc2-decomposition in polynomial time[END_REF][START_REF] Tsukiyama | A new algorithm for generating all the maximal independent sets[END_REF], which include all maximum ones. Here, it could be interesting to design a specialized algorithm for enumerating all stable sets of size χ(G), based on a known clique partition of G of the same size χ(G).

Moreover, we can ensure the existence of at least one conformal network outgoing from reproducible data (Thm. 1), since we allow the occurrence of WPCs in P S which can be later resolved by inserting control-arcs. In contrast, during the reconstruction of standard networks without control-arcs, all priority conicts have to be excluded so that we obtain a solution outgoing from reproducible data only if none of the observed dierences d j is enabled at a terminal state

x k [12] (since the resulting WPC(σ, σ ) between (x j , d j ) ∈ σ and (x k , 0) ∈ σ cannot be resolved in standard networks).

On the other hand, we always obtain an extended network being conformal with reproducible data, since a catalytical conformal extended network exists if none of the observed dierences d j starts at a terminal state x j [2], and this property is guaranteed by the preprocessing [START_REF] Wagler | Preprocessing for network reconstruction: Feasibility test and handling infeasibilty[END_REF] (otherwise, x j would have two dierent successors x j + d j and x j + 0).

During the reconstruction of extended networks without priorities in [START_REF] Durzinsky | Reconstruction of extended Petri nets from time-series data by using logical control functions[END_REF], all occuring WPCs are resolved by inserting control-arcs only: a WPC(σ, σ ) between (y, r t ) ∈ σ and (y , r t ) ∈ σ is resolved by disabling t at y and disabling t at y (since no priorities are at hand to force the desired switch). Hence, the resulting networks may contain more control-arcs than catalytic or inhibitory dependencies indeed exist, since several switches are not controled by reaction rates (reected by priorities), but by additional control-arcs.

In contrast, during the reconstruction of extended networks with priorities we only introduce control-arcs if the experimentally observed behavior cannot be forced by priorities alone. Moreover, only using minimal sets of control-arcs needed to resolve all WPCs in a network P S has a further advantage: instead of rstly computing all possible solutions (in terms of all possible covers of the matrix A S ) and later removing non-minimal solutions in a postprocessing step (as described in [START_REF] Wagler | On minimality and equivalence of Petri nets[END_REF]), we avoid to generate such solutions already during the reconstruction process.

Our further goal is to avoid not only generating non-minimal solutions, but also minimal solutions which are technically correct but would be ruled out later during a subsequent verication process to check whether the returned solutions are biological meaningful or contradict well-established biological preknowledge (e.g. on catalysts or inhibitors of certain reactions). This could be done by integrating further biological pre-knowledge (beyond the information given with the experimental data) into the reconstruction process.

For standard networks, we already provided an implementation of the reconstruction approach using Answer Set Programming [START_REF] Durzinsky | Automatic network reconstruction using asp[END_REF]. The nal goal is to provide such an implementation also for extended Petri nets with priorities and to apply the presented reconstruction approach to dierent biological experimental data. We indeed expect an important impact of Automatic Network Reconstruction in order to support the integrated experimental and theoretical analysis of biological systems and processes towards their holistic understanding.

In [START_REF] Favre | Reconstructing X -deterministic extended Petri nets from experimental time-series data X (extended abstract)[END_REF], an integrative method to reconstruct all X -deterministic extended Petri nets with priorities tting given experimental time series data is proposed.

We detailed here the aspect of handling priority conicts and choosing controlarcs by discussing the underlying mathematical structures and related combinatorial problems: we interpreted -the selection of suitable sequences from the priority conict graph as the problem of nding a stable set of size χ(G S ) in G S and ensured the existence of such a stable set (Thm. 1).

-resolving WPCs as set cover problem involving a matrix A S encoding all possible control-arcs to resolve all WPCs in a standard network P S and showed that computing the blocker b(A S ) yields all minimal catalytic conformal extended Petri nets based on P S (Thm. 3).

These interpretations in terms of two well-known combinatorial optimization

problems open us the possibility to apply eective techniques known from the literature, e.g., the classical algorithm of Berge [START_REF] Berge | Hypergraphs[END_REF] or one of its recent, more ecient variants [START_REF] Eiter | Computational aspects of monotone dualization: A brief survey[END_REF][START_REF] Murakami | Ecient algorithms for dualizing large-scale hypergraphs[END_REF], to compute the blocker of a matrix.

On the other hand, there exist algorithms to enumerate all maximal stable sets of a graph [START_REF] Johansson | Nlc2-decomposition in polynomial time[END_REF][START_REF] Makino | New algorithms for enumerating all maximal cliques[END_REF][START_REF] Tsukiyama | A new algorithm for generating all the maximal independent sets[END_REF], which include all maximum ones. Here, it could be interesting to design a specializes algorithm for enumerating all stable sets of size χ(G), based on a known clique partition of G of the same size χ(G).

Appendix

The following appendix should not be considered as part of the paper, but only as condential supplementary information for the program committee.

6.1 The priority conict graph and selecting sequences

For any graph G, the maximum size of a stable set in a graph, called its stability number α(G), is a lower bound for its clique cover number χ(G) (since a stable can meet a clique in at most one node). In general, we do not have equality (e.g., the chordless cycle C 5 on 5 nodes has α(C 5 ) = 2 but χ(C 5 ) = 3).

Theorem 4. We have α(G S ) = χ(G S ) for the strong priority conict graph G S and, thus, system (1) is always feasible.

Proof of Theorem 4. Making use of the reproducibility of the given data X

guaranteed by the preprocessing [START_REF] Wagler | Preprocessing for network reconstruction: Feasibility test and handling infeasibilty[END_REF], we show that the canonical solution S 1 , the selection of all canonical sequences σ 1 (x j , d j ) = ((x j , d j )) ∀ d j ∈ D, is always a solution of [START_REF] Berge | Hypergraphs[END_REF].

For that we have to verify that σ 1 (x j , d j ) is neither in strong priority conict with any other canonical sequence σ 1 (x i , d i ) for some d i ∈ D \ d j , nor with any trivial sequence σ(x, 0) for some x ∈ X term .

Recall that the reproducibility of X guarantees that each x j ∈ X has a unique successor x j+1 = x j + d j ∈ X , and that this includes d j = 0 ∀ d j ∈ D (otherwise, if d j = 0, then x j+1 = succ(x j ) = x j + 0 = x j holds and, thus, x j has two dierent successors x j+1 = x j and succ(x j+1 ) = x j , a contradiction).

Case 1: Consider two canonical sequences σ 1 (x i , d i ) and σ 1 (x j , d j ) in priority conict, i.e., we have d i = d j and d i , d j ∈ T (x i ) ∩ T (x j ).

Then x i = x j follows from reproducibility (otherwise, x i = x j would have two dierent successors x i + d i = x j + d j in X by d i = d j ), hence the priority conict is not strong.

Case 2: Consider a canonical sequence σ 1 (x i , d i ) and a trivial sequence σ(x, 0) for some x ∈ X term in priority conict, i.e., we have d i ∈ T (x).

We infer x = x i from the reproducibility of X (otherwise x = x i would have two dierent successors x + d i = x + 0 in X by d i = 0), hence the priority conict is not strong.

Finally, observe that neither two canonical sequences σ 1 (x i , d) and σ 1 (x j , d) nor two trivial sequences σ(x, 0) and σ(x , 0) can be in any priority conict (since d = d and 0 = 0 holds, resp.).

2

Theorem 1 is clearly a corrollary from the more general Theorem 4.

Proof of Lemma 1. A node σ ∈ V D being in SPC with all sequences from some Q ∈ Q is adjacent to all nodes in Q. Since exactly one node, say σ ∈ Q, has to be selected from Q by (1a) or (1b), inequality (1c) forces x σ = 0 (by x σ = 1 and x σ + x σ ≤ 1) due to the SPC between σ and σ . Hence, σ cannot be selected for any solution S of (1). 2

Note that Lemma 1 includes the case addressed in [START_REF] Durzinsky | Reconstruction of extended Petri nets from time-series data by using logical control functions[END_REF] that no sequence σ containing a terminal state x as intermediate state is appropriate: Then σ contains a reaction vector r t = 0 which is supposed to switch in x, leading to a SPC between σ and the trivial sequence σ(x, 0) since t ∈ T (x) holds.

Since σ(x, 0) is a clique Q x in G S of size 1 and σ is in SPC with the whole clique Q x , Lemma 1 implies the assertion of Corollary 1.

The reduced version of the original priority conict graph from Fig. 2 is presented in Fig. 4.

Q 3 Q 1 Q 3 Q 2 Q 0 Q 4 σ(x 1 , d 1 ) σ 3 (x 1 , d 1 ) σ(x 3 , 0) σ(x 2 , d 2 ) σ(x 0 , 0) σ(x 4 , d 4 ) σ 3 (x 4 , d 4 )
Fig. 4. The reduced priority conict graph resulting from the running example, where bold edges indicate SPCs, thin edges WPCs and gray boxes the clique partition Q.

Theorem 5. We have α(G S ) = χ(G S ) for the reduced strong priority conict graph and the sets of maximum stable sets in G S and G S are equal.

Proof of Theorem 5. By construction, G is an induced subgraph of G, hence G S is an induced subgraph of G S as well.

Since from G and G S , only nodes are deleted during the reduction step which cannot occur in any maximum stable set of G S by Lemma 1, we have α(G S ) = α(G S ).

None of the cliques in Q turns into the empty set by applying the reduction (since at least the canonical sequence σ 1 (x j , d j ) remains in Q j and all trivial sequences σ(x, 0) from V term remain in G due to Theorem 4 and Lemma 1).

This implies χ(G S ) = χ(G S ), and the assertion α(G S ) = χ(G S ) follows from Theorem 4.

2

Theorem 2 is a direct consequence of the more general Theorem 5.

We nally obtain the reduced system to compute all maximum stable sets in G S .

σ∈Qj x σ = 1 ∀Q j ∈ Q (2a) x σ = 1 ∀σ ∈ V term (2b) x σ + x σ ≤ 1 ∀σσ ∈ E S (2c)
x σ ∈ {0, 1} ∀σ ∈ V D ∪ V term .

(2d)

Interpretation of resolving WPCs as set cover problem

Proof of Lemma 2. We can partition the set CA(σ, σ ) in two dierent subsets:

-CA t,y (σ, σ ) containing all control-arcs that disable t at y , -CA t ,y (σ, σ ) containing all control-arcs that disable t at y.

We distinguish the following cases:

Case 1: A ⊆ CA t,y (σ, σ ). In this case, the control-arcs in A disable t at y (such that only t remains in T (y )), but still t, t ∈ T (y) holds. Adding the priority t > t forces t to switch in y and, thus, the WPC(σ, σ ) is resolved by adding A and t > t .

Case 2: A ⊆ CA t ,y (σ, σ ). This case is analogously to Case 1, by interchanging the roles of t and t resp. y and y .

Case 3: A intersects both CA t,y (σ, σ ) and CA t ,y (σ, σ ). In this case, the control-arcs in A disable t at y and t at y (such that only transition t remains in T (y) and transition t in T (y )). This already forces t to switch in y and t in y , thus, the WPC(σ, σ ) is resolved by adding A , without adding a further priority between t and t . 2

Proof of Lemma 3. Any cover C of the matrix A S encoding row-wise all sets CA S (σ, σ ) for all WPCs in P S selects, by construction, a non-empty subset A ⊆ CA S (σ, σ ) for each WPC. According to Lemma 2, the union of these sets A resolves all WPCs in P S . Moreover, it is ensured for all sequences σ ∈ S, that r t l ∈ T A (y l ) holds for all reaction vectors r t l and intermediate states y l in σ = σ π,λ (x j , d j ) = ((y 1 , r t1 ), . . . , (y m , r tm ), since the control-arcs do not remove t l from T A (y l ) for any t l involved in a WPC at y l by construction of CA(σ, σ ) and for any t l not eected by a WPC at y l by the reduction of the sets CA(σ, σ ) to CA S (σ, σ ), if necessary. Hence, inserting the control-arcs selected by C in P S indeed yields a catalytical conformal extended Petri net.

2

Note: A S does not necessarily have a cover (namely, not if CA S (σ, σ ) is empty for one WPC(σ, σ )). On the other hand, if there is a cover C for A S , then the resulting catalytical conformal extended Petri net can be made X -deterministic by adding appropriate priorities (as in the proof of Lemma 2).

Proof of Lemma 4. According to [START_REF] Wagler | On minimality and equivalence of Petri nets[END_REF], two X -deterministic extended Petri nets with priorities are M -equivalent if they have the same incidence matrix M .

In particular, all X -deterministic extended Petri nets with priorities stemming from the same standard network P S are M -equivalent (since they dier only in their sets of control-arcs or priorities).

We call a control-arc essential if the network is not X -deterministic anymore after its removal (since at least one of the WPCs in P S remains unresolved), and unnecessary otherwise.

We ensure that a cover C of the matrix A S encoding row-wise all sets CA S (σ, σ ) for all WPCs in P S is minimal if and only if it only contains essential control-arcs: Case 1: Each CA S (σ, σ ) intersects C in exactly one element. Then all controlarcs selected by C are clearly essential and C is a minimal cover.

Case 2: There is a set CA S (σ i , σ i ) having with C at least 2 elements in common.

Case 2.1: (At least) one control-arc in CA S (σ i , σ i ) does not show up in the intersection of C with any other CA S (σ j , σ j ), say (p i , t i ). Then C \ {(p i , t i )} is still a cover of A S and, thus, C is not minimal and contains an unnecessary control-arc (p i , t i ).

Case 2.2: All control-arcs in CA S (σ i , σ i )∩C show up in the intersection of C with another set CA S (σ j , σ j ). If each of them is the only control-arc in CA S (σ j , σ j ) ∩ C, then all of them are essential and C is minimal. Otherwise, at least one of them, say (p, t), is not the only control-arc in CA S (σ j , σ j ) ∩ C (for each WPC with (p, t) ∈ CA S (σ j , σ j )). Then C \ {(p, t)} is still a cover of A S , C not minimal and (p, t) ∈ C unnecessary.

2

  1 , ..., t m ) of transition switches, i.e., there are intermediate statesx j = y 1 , y 2 , ..., y m+1 = x j+1 with y l + M •t l = y l+1 for 1 ≤ l ≤ m. The extended Petri net P = (P, T, A, w) is catalytic conformal with X if t l ∈ T A (y l ) for each intermediate state y l , and the extended Petri net with priorities

This work was founded by the French National Research Agency, the European Commission (Feder funds) and the Région Auvergne within the LabEx IMobS 3 .


Lina Deambrogio
email: deambrogio@recherche.enac.fr

Olivier Julien
email: ojulien@recherche.enac.fr

Characterization of Carrier Phase Measurement Quality in Urban Environments

Keywords: Carrier phase, Tracking, Multipath, DLR multipath model, Mask angles I

The feasibility of precise positioning techniques in urban scenarios is dependent on the quality of carrier phase measurements. Given the lack of robustness of carrier phase tracking and its limitations in constrained scenarios, it is hence important to be able to characterize carrier phase measurement quality and define guidelines for measurement selection prior to computing the receiver position. In this paper, an analysis of optimal tracking settings is carried out and phase measurement quality is investigated by considering the effects of multipath in an exemplary urban scenario.

INTRODUCTION

Carrier-phase tracking is an important operation in a GNSS receiver since it allows data demodulation but also because it can provide very precise, although ambiguous, pseudorange measurements to the navigation processor. Carrier-phase-based measurements can in fact be used to improve the positioning solution either through their direct use in the position computation or by filtering the less accurate code measurements.

However, carrier phase tracking is also well-known as being one of the weakest stages in a GNSS receiver due to its lack of robustness in environments where fading and high dynamics cause sudden changes in the signal parameters. In order to overcome this drawback, most of the current GPS receivers destined to work in urban environment can rely to track the carrier frequency on the use of a FLL, which is more robust but less accurate than carrier-phase tracking, and/or using external links to get the navigation message.

It is quite clear, however, that the ability for the receiver to use the precise carrier-phase measurement would provide a strong advantage since it could significantly improve the positioning accuracy of the receiver, even in difficult environments. This feature could clearly be a strong differentiator from present mass-market receivers.

In this context, in order to evaluate the feasibility of carrier phase positioning techniques in urban environments, two different axes should be considered: signal processing, in order to improve the quality of the carrier phase tracking and deliver healthy measurements, and measurement processing, to filter and select the measurements that will be used for position computation. It is then important as a first step to consider carefully the choice of suitable tracking loop settings to provide optimal tracking performance in an urban scenario without impacting on receiver complexity. To this end it is important to identify the tracking settings through the theoretical analysis of the Phase Lock Loop (PLL) tracking sensitivity as a function of the PLL loop bandwidth and integration time [START_REF] Kaplan | Understanding GPS: principles and applications, second edition[END_REF].

The second step is to analyze the quality of carrier phase measurements in a typical urban scenario in order to obtain a characterization of their quality and deduce guidelines for their selection. In fact, by determining a possible mask for the satellite angles and received signal-power-to-noise-densityratio C/N 0 it can be possible to exclude from the precise positioning algorithm highly deteriorated measurements.

To test as extensively and accurately as possible the effect of multipath, a specific receiver platform, referred to as GeneIQ, was developed. This platform is based on the concept of semi-analytic receiver simulators, meaning that the receiver simulator is built based on the accurate modeling of correlator outputs.

Simulations have been carried out by employing signals which have been modified by the effects of the DLR Land Mobile Satellite (LMS) Channel Model [START_REF] Steingass | Measuring the Navigation Multipath Channel -A Statistical Analysis[END_REF] [3] and injecting them in the GeneIQ simulator.

The characterization of carrier phase measurement quality has been conducted considering the impact of multipath on the tracking stage in terms of tracking error but also of PLL loss of lock [START_REF] Parkinson | Global Positioning Systems: Theory and Applications. Volume I[END_REF].

II. SELECTION OF TRACKING SETTINGS

In general, the decision on the choice of the PLL settings (loop bandwidth, correlation duration, discriminator, etc.) is based on the computation of the PLL tracking threshold. A conservative rule of thumb is that the 3-sigma jitter must not exceed half of the phase pull-in range of the PLL discriminator. The typical criterion to assess this threshold is given by [START_REF] Kaplan | Understanding GPS: principles and applications, second edition[END_REF] as: [START_REF] Kaplan | Understanding GPS: principles and applications, second edition[END_REF] where:  √ is the total phase tracking error standard deviation



is the variance due to thermal noise  is the variance of the phase tracking error due to the oscillator vibrations



is the variance of the phase tracking error due to the oscillator phase noise



is the phase tracking bias due to a signal dynamics  is the two-sided discriminator linear tracking region

The justification behind [START_REF] Kaplan | Understanding GPS: principles and applications, second edition[END_REF] is that the tracking error should remain within the carrier phase discriminator linear range in order for the loop to have a normal behavior and for the tracking to be feasible.

For a data signal and a pilot signal, different types of discriminators can be selected allowing achieving different performance. For data signals, the discriminator needs to be chosen so as to be insensitive to data bit transitions [START_REF] Julien | Design of Galileo L1F Receiver Tracking Loops[END_REF]. The most widely used discriminator is in this case the Dot Product (DP), which is expressed as the product between in-phase and quadra-phase prompt correlation components:

(

The linear tracking region of this discriminator is

[ ] [1][5].
On the other hand, for pilot signals, there is no longer the need to be robust against bit transitions and the coherent discriminator can be used:

(

The stability domain of the coherent discriminator is twice as large as for the DP phase discriminator as it tracks the phase error directly yielding [ ] [START_REF] Kaplan | Understanding GPS: principles and applications, second edition[END_REF]. Both presented data and pilot phase discriminators require a normalization to remove the impact of the signal power.

Having defined the tracking threshold, it is then possible to identify the optimal loop bandwidth and integration time for given maximum signal dynamics, oscillator phase noise and thermal noise, by considering the impact of each error against the threshold.

The presence of thermal noise creates a tracking error that can be expressed for data and pilot signals respectively as [START_REF] Kaplan | Understanding GPS: principles and applications, second edition[END_REF][6] [START_REF] Van Dierendonck | GPS Receivers in Global Positioning System: Theory and Application Volume I[END_REF][8]:

) (4) (5)
With defining the loop bandwidth in Hz, ⁄ the carrier to noise power density ratio in dBHz and is the coherent integration time in s. It should be noted that in the case of a pilot signal, a degradation of 3dB should be considered when processing only the pilot signal. As evidenced by ( 4) and ( 5), the tracking error variance due to thermal noise can be limited by reducing the equivalent loop bandwidth or extending the integration time. In Fig. 1, the effect of the loop bandwidth on the PLL phase jitter is exemplified for a data signal and fixed integration time =20 ms, showing that in order to limit the effect of noise, smaller bandwidth should be considered. Conversely, receiver oscillator phase noise, vibrations and signal dynamics can all be modelled as having analogous effects: they are perceived by the receiver as creating delay and phase variations that translate in an additive term in the instantaneous incoming signal Doppler. As a consequence, the PLL has to track also this additional phase variation in order not to lose lock, requiring the PLL to react very fast to phase variations (caused by low quality oscillators or high dynamics). The PLL loop bandwidth has then to be quite large or equivalently the correlation time needs to be fairly small in order to have a limited phase variation during the correlation operation. The computation of , and can be obtained following [START_REF] Irsigler | PLL Tracking Performance in Presence of Oscillator Phase Noise[END_REF] and [START_REF] Stephens | Controlled-Root Formulation for Digital Phase-Locked Loops[END_REF].

It is then clear that a trade-off needs to be reached between robustness against thermal noise and reactiveness to changes in the received signal due to dynamics and oscillator instabilities.

For a third order PLL, given a fixed integration time =20 ms and ⁄ = 40dBHz, a TCXO oscillator with parameters =2e-20 (1/s), =1e-20, = 1e-21(s), assuming constant values for the oscillator g-sensitivity ( =1e-9 (1/g)) and power spectral density ( 0.05 (g^2/Hz)) [START_REF] Irsigler | PLL Tracking Performance in Presence of Oscillator Phase Noise[END_REF] and maximum dynamics characterized by jerk=1 (g/s) it is possible to obtain the behaviors reported in Fig. 1 and Fig. 2 for the different error contributions and the total error. Fig. 1 and Fig. 2 show the individual phase jitter contributions and the total phase jitter against the tracking threshold. Consequently, it is intuitive to determine the range of possible bandwidth that can be selected to allow tracking as the bandwidths that guarantee that the total error is below the tracking threshold.

In urban environments, also the effect of multipath should be taken into account. To this end, it is then important to notice that multipath components have an inherent phase variation that distinguishes them in the frequency domain from the Line Of Sight (LOS), allowing filtering the multipath out and concentrating only on the LOS. This filter can be realized either by selecting a very narrow loop bandwidth or by extending the correlation time, obtaining a low pass filter that attenuates multipath with a Doppler component differing from the Doppler of the local replica.

Among the bandwidths identified through the sensitivity analysis carried out above without including multipath and considering a standard integration time of 20ms, the lowest possible value of bandwidth should be chosen as the one better suited for rejecting the impact of multipath.

As a conclusion:

 the GPS L1 C/A PLL should use a Dot Product and a loop bandwidth as narrow as possible comprised within [15; 20] Hz;

 the Galileo E1 OS PLL could use either the coherent and a loop bandwidth as narrow as possible comprised between 10 and 15 Hz.

III. SCENARIO DESCRIPTION

The DLR Land Mobile Satellite (LMS) Channel Model [2] [START_REF] Steingass | A Novel Channel Model for Land Mobile Satellite Naviagtion[END_REF] has been used to simulate an urban environment consisting of a user moving with constant velocity along a street surrounded by buildings, trees, and lampposts that can hinder the reception of the signal transmitted by a satellite with fixed elevation and azimuth angles. This model has been used to obtain the delays, amplitudes and phase shifts of the LOS and reflected path signals. A combination of a deterministic and a statistic approaches is considered in the model: obstacles are placed and shaped following a Gaussian distribution. Once placed, however, they present a deterministic behavior.

The direct path component is determined by physical deterministic effects generated by house fronts, trees and lampposts. House front diffraction is modeled as a knife edge model, tree attenuation is modeled as proportional to the path length through the tree canopy plus a stochastic fading process and lampposts are modeled through a double knife edge model. The multipath signals are caused by reflectors that are generated following statistical data obtained through a measurement campaign carried out by DLR.

A typical urban scenario has been tested considering:

 A vehicular user moving with constant velocity along the street;

 The street is assumed to be 15 meters wide;

 The size of the buildings follow a Gaussian distribution with the width with and the height with ;

 The gap between buildings appears with probability and a gap width with ; To assess the robustness of the carrier phase tracking block to multipath and fading, a database of received rays has been processed. The database contains the time series of received rays from a satellite at different positions generated with the DLR LMS. The elevation angles considered are comprised within [10°-80°] with 10° steps and the azimuth angles are within the range [0° -90°] with 45° steps, considering the street axis as azimuth 0°. Simulations of 20s duration have been performed for each satellite's azimuth and elevation angle pair. The number and length of the simulations has been chosen according to criteria of computation time, output data size and accuracy of the model. Moreover, considering a receiver moving along the street (azimuth angle of 0°) at 50 km/h speed, the considered sampling rate for the DLR model has been set to 1 KHz as reported in Table 1 [START_REF] Perez-Fontan | Statistical modeling of the LMS channel[END_REF]:


⁄ (6)
Where:

 is the signal wavelength (m)
 is the receiver velocity (m/s)

IV. SIMULATOR DESCRIPTION

In order to test as extensively and accurately as possible the proposed algorithms, a specific receiver platform, referred to as GeneIQ, was consolidated. This platform is based on the concept of semi-analytic receiver simulators, meaning that the receiver simulator is built based on the accurate modeling of correlator outputs. Being able to model accurately correlator outputs means that the correlation operation, the most demanding in a GNSS receiver, does not need to be performed, saving a lot of simulation time. The correlator output model for a data component is given by:

( ( (
 (7) ( ( ( (8)
Where:  is the incoming signal amplitude  is the correlation function between the incoming PRN including its modulation and the local replica



is the correlation duration  is the data bit value, or secondary code value during the integration interval  is the time shift between the incoming and local PRN codes



is the frequency shift between the incoming and local carriers



represents the phase difference between the incoming and local carrier in the middle of the correlation interval  and are the in-phase and quadrature phase correlator output noise components due to thermal noise. These noise components are independent and follow a Gaussian distribution with a power equal to Such a model is valid as long as the amplitude and frequency of the incoming signal remain constant during the correlation interval. This hypothesis is generally fulfilled for correlation duration on the order of a millisecond, which is the case for GNSS. However, these assumptions should be tested whenever the propagation channel is expected to have high frequency components (fast changing parameters) as it could be the case for an urban environment.

Because the correlator output rate is in the order of the kHz, it is easy to understand that the simulation duration will be much lower than when simulating the true received signal with a sampling frequency on the order of a few MHz. It is thus an interesting tool to have a first performance analysis of specific techniques.

Based on [START_REF] Van Dierendonck | GPS Receivers in Global Positioning System: Theory and Application Volume I[END_REF] and [START_REF] Holmes | Coherent Spread Spectrum Systems[END_REF] it is then possible to model most of the degradations affecting the correlator output used to track the signal:

 signal strength (based on an adapted link budget)

 signal modulation (by modifying the shape of the correlation function)

 RF front-end filtering (by modifying the shape of the resulting correlation function)

 signal dynamics (such as receiver motion, satellite motion, atmosphere variation)

 receiver clock phase noise (by accurately modeling the clock phase noise coming from the receiver clock, as performed in [START_REF] Irsigler | PLL Tracking Performance in Presence of Oscillator Phase Noise[END_REF])

 thermal noise (by adding a noise term with the correct variance to the correlator output model)

 multipath (by summing as many correlator outputs as there are multi-paths, given that the amplitude, delay and phase of the multipath are known and that the associated with the multipath is constant over the correlation duration)  RF interfering (either as a reduction of the C/N0, or as a specific model in case of a CW)

Following the accurate modeling of the correlator output, it is then possible to implement tracking loops and to output measurements such as code, phase and Doppler measurements. In order to assess the robustness of the carrier phase tracking block to multipath and fading, the database of received signal rays has been processed with a similar approach to [START_REF] Salós Andrés | Integrity monitoring applied to the reception of GNSS signals in urban environments[END_REF] within the GeneIQ module to provide the tracking errors and additional data like the percentage of lock.

V. MEASUREMENT QUALITY ANALYSIS

In order to use carrier phase measurements for precise positioning, it is finally important to address the issue of measurement quality. Indeed, in urban scenarios, the presence of multipath and fading can severely impact the feasibility of precise positioning techniques by degrading the quality of carrier phase measurements and by limiting their availability.

In the following three different metrics have been applied for characterizing carrier phase measurement quality:  Tracking error standard deviation, to describe measurement accuracy;

 Number of cycle slips, identifying discontinuity of the measured carrier phase resulting from a temporary loss of lock in the carrier tracking loop of a GNSS receiver that requires re-initializing the ambiguity estimation block in order to avoid erroneous results in high precision solutions [START_REF] Kim | Instantaneous Real-Time Cycle-Slip Correction for Quality Control of GPS Carrier-Phase Measurements[END_REF];

 Percentage of successful tracking, defining the availability of the measurements. The results show that an elevation mask angle equal to 40° should be applied to guarantee tracking of the carrier phase and availability of the carrier phase measurement. Analogous results can be obtained for other azimuth angles.

In order to show in a clearer manner the behavior of the PLL in the presence of multipath, in the following the tracking error time series and estimated ⁄ values are depicted for the worst case elevation angle 10° and for the mask angle case of 40°. Only the epochs in which carrier phase tracking is available have been plotted. It is then clear that at low elevation angles tracking is impossible and performance are clearly degraded as can be seen from Fig. 5, reporting the estimated ⁄ . Conversely, has shown in Fig. 6 and Fig. 7, at 40° of elevation performance clearly improve suggesting both in terms of tracking error performance and estimated ⁄ . This analysis shows the vulnerability of the PLL in difficult environments. In this context, in order to use precise positioning techniques, it becomes thus fundamental to be able to increase carrier phase measurements availability and reduce the occurrence of cycle slips.

The analysis shows that a measurement selection should be carried out through the use of a mask angles. Simulations identify the elevation angle equal to 40° as a mask angle good.

VI. CONCLUSIONS

This paper has presented an analysis of carrier phase tracking in urban scenarios. The analysis has been carried out to identify tracking settings and a selection criterion for the carrier phase measurement. The analysis has shown that higher elevation angles generally yield better performance in terms of carrier tracking loss of lock events and has identified elevation angle equal to 40° as a good candidate for a masking angle. Other types of measurement selection could also be considered by using estimated ⁄ masks. It should be noted that a selection of measurements can have an effect on the position by degrading the satellite geometry. However, with the availability of future constellations including GPS, GLONASS and Galileo, the low availability of measurements in urban areas should be less problematic.

Fig. 1 PLL

 1 Fig. 1 PLL Thermal noise jitter vs PLL loop bandwidth

Fig. 2 .

 2 Fig. 2. PLL phase jitter contributions and Threshold for a Dot Product tracking loop



  Trees have a constant height of 8 m and a diameter of 5 m. Tree trunks have a constant length of 2 m a diameter of 0.2 m. Leafs are assumed to cause an attenuation of 1.1 dB/m. The distance between the trees and the buildings is 2 m. The distance between trees follows a normal distribution with ; Lampposts have a constant height of 8 m and a diameter of 0.2 m. The distance between lampposts follows a normal distribution with ; sigma (°) PLL Loop Bandwidth (Hz) Pilot Signal -CN0=37dBHz, TCXO clock, jerk=1 [g/s] Reflected signals are considered up to a maximum attenuation of -45 dB

Fig. 4

 4 Fig. 4 Carrier phase tracking error time serie at elevation angle 10°

Fig. 5

 5 Fig. 5 Estimated ⁄ for the elevation angle 10°

Fig. 6 Fig. 7

 67 Fig. 6 Carrier phase tracking error time serie at elevation angle 40°

  (rad) Carrier-phase tracking error -Elevation angle 40°

TABLE 1

 1

			SAMPLING INTERVALS
			Frequency Band
			L1/E1	L5	E5a	E5b
	Velocity	50	1.7 ms	2.3 ms	2.3 ms	2.2 ms
	(km/h)	90	0.95 ms	1.3 ms	1.3 ms	1.2 ms

ACKNOWLEDGMENT

This work has been developed within the framework of the e-Himalaya, European Commission FP7 funded Collaborative Project aiming at developing high performance Galileo ready receiver technologies.

Tracking is locked according to the phase lock detector [START_REF] Parkinson | Global Positioning Systems: Theory and Applications. Volume I[END_REF]. The detector is based on the concept that, if the incoming signal is being correctly tracked, then the in-phase component of the prompt correlator is maximum, and its quadrature component is minimum:

Where:

 is the carrier phase;

 M is the number of coherent integrations.

In lock conditions ( . When lock is lost, then we suppose going to reacquisition.

The following results have been computed considering:




Muhammad Muzzamil Luqman
email: muhammad_muzzamil.luqman@univ-lr.fr

Nam Hoang
email: hoang_nam.ho@univ-lr.fr

Jean-Christophe Ho
email: jean-christophe.burie@univ-lr.fr

Jean-Marc Burie
email: jean-marc.ogier@univ-lr.fr

Ogier

Automatic indexing of comic page images for query by example based focused content retrieval

Automatic indexing of comic-page-image repositories has evolved as an interesting research problem for graphics recognition research community. In this paper we present a system for automatically indexing the comic-page-images in order to achieve query by example (QBE) based focused content retrieval.

In our system we represent the comic-page-images by attributed graphs and translate the problem of automatic indexing / QBE based focused content retrieval as a subgraph spotting problem. Our system uses an explicit graph embedding technique to embed the comic-page-image graphs into numeric feature vectors and then employs state-of-the-art machine learning tools for automatic indexing / QBE based focused content retrieval. Experimental results are presented for automatic indexing and QBE based focused content retrieval in a comic-page-image repository.

I. INTRODUCTION

In recent years the automatic indexing and content based focused retrieval in comic-page-image repositories, has emerged as an interesting research problem for graphics recognition research community. Comics represent an important heritage in many countries. The digitization of paper based comic archives give rise to interesting research challenges. Considering the increasing size of comic-page-image repositories, unsupervised algorithms are desired for automatic indexing, so that the liberty of natural ways of querying the graphics content in these repositories (i.e. query by example (QBE) based focused retrieval, instead of traditional text based information retrieval) could be provided to the users.

The comic pages are rich in structured graphics content and in our point of view the research problem of content retrieval in comic pages provides an opportunity to apply existing methodologies of graphics recognition. Graph based representations are the natural, most powerful and widely used data structures for structured data [START_REF] Conte | Thirty years of graph matching in pattern recognition[END_REF]. Graphs provide unmatched advantages for representing the topological and geometric details of underlying data but graphs have limited computational efficient tools to process them. Modern approaches of embedding graphs in vector spaces allow to overcome the computational expensiveness of graphs [START_REF] Foggia | Graph Embedding for Pattern Recognition[END_REF][3] and enable graph based indexing and retrieval of image repositories.

An interesting recent work on (Japanese comic) manga retrieval is presented in [START_REF] Sun | Similar manga retrieval using visual vocabulary based on regions of interest[END_REF]. The authors have used bagof-features method using visual words based on face ROIs and clusters of generic ROIs, for similar manga retrieval. We believe that graph based representation of comic pages provides a natural way to perform many high level semantic operations in comic-page-image repositories. Our current work is inspired by the work in [START_REF] Sun | Similar manga retrieval using visual vocabulary based on regions of interest[END_REF] and we have investigated a graph based methodology for comic retrieval.

In this paper we present a system for automatic indexing and QBE based focused content retrieval in comic-page-image repositories. The block diagram of our system is presented in Figure 1. In our system the comic pages are represented by region adjacency graphs (RAGs) -automatic and unsupervised indexing is achieved by employing graph embedding and machine learning tools -and QBE based focused content retrieval is achieved through subgraph spotting. The work presented in this paper is an advancement of our research on subgraph spotting [START_REF] Luqman | Subgraph spotting through explicit graph embedding: An application to content spotting in graphic document images[END_REF]. The novel contributions of this paper are the RAG based graph representation for comic pages, adaptation of our subgraph spotting system to comic page graphs and experimental evaluation of the new system for comic-page-image repository. In Section II we introduce the notations and definitions of the concepts used in this paper. Section III details the graph representation phase of our system, the automatic indexing phase and QBE based focused content retrieval in comic-pageimage repositories. Experimental results and discussion are presented in Section IV. The paper concludes in Section V with futures lines of work.

II. DEFINITIONS AND NOTATIONS

Attributed Graph (AG): Let A V and A E denote the domains of possible values for attributed vertices and edges. These domains are assumed to include a special value that represents a null value of a vertex or an edge. An attributed graph AG over (A V , A E ) is defined to be a four-tuple:

AG = (V, E, µ V , µ E )
where, V is a set of vertices, E ⊆ V × V is a set of edges, µ V : V -→ A V is function assigning attributes to vertices and µ E : E -→ A E is a function assigning attributes to edges.

In an attributed graph AG: |V | is graph order, |E| is graph size and degree of a node is number of edges connected to it.

Resemblance attributes: The resemblance attributes are new attributes that we compute from the attributes of nodes and edges in a graph. These attributes provide a measure of homogeneity among the surrounding nodes of an edge and vice versa.

An edge connects exactly two nodes in a graph. For an edge, the resemblance attributes are computed from respective attributes of its nodes. For example, for an edge between nodes, "1" and "2", resemblance between a numeric attribute "a" is computed by Equation 1 and resemblance between a symbolic attribute "b" is computed by Equation 2.

resemblance = min(|a 1 |, |a 2 |)/max(|a 1 |, |a 2 |) (1) resemblance = 1 b 1 = b 2 0 otherwise (2)
A node can have many edges connecting it to other nodes in the graph. For a node, the resemblance attributes are computed as the mean of the resemblance between all pairs of its edges. The latter is computed by Equation 1 for a numeric attribute "a" and by Equation 2 for a symbolic attribute "b".

Graph Embedding: Graph Embedding is a methodology aimed at representing a whole graph (with attributes attached to its nodes and edges) as a point in a suitable vector space; preserving the similarity of the graphs i.e. the more two graphs are considered similar, the closer should be the corresponding points in the vector space. The graph embedding methods are formally categorized as implicit and explicit graph embedding. The implicit graph embedding methods are based on graph kernels, and actually are functions that perform scalar product between the vectors associated to two graphs. Such an embedding satisfies the main mathematical properties of scalar product but does not permit all the operations that could be defined on vector spaces. On the other hand, the more useful, explicit graph embedding methods map a graph to a point in suitable vector space. It encodes the graphs by equal size vectors and produces one vector per graph; thus enabling the use of all the methodologies, techniques and operations devised for vector spaces. The vectors for two graphs which are obtained by an explicit graph embedding method can also be employed in a standard dot product for defining an implicit graph embedding function between them.

Fuzzy Multilevel Graph Embedding (FMGE): Fuzzy

Multilevel Graph Embedding (FMGE) is a method of explicit graph embedding, which has been proposed in [START_REF] Luqman | Fuzzy multilevel graph embedding[END_REF]. FMGE exploits structural and statistical significant details of an attributed graph for embedding it into a feature vector. Its resulting feature vector is termed as Fuzzy Structural Multilevel Feature Vector (FSMFV). As shown in Figure 2 FSMFV contains graph level features, node level features and edge level features. The graph level features are graph order and graph size. Node level features are fuzzy histogram of node degree and fuzzy histogram of each distribution of the values taken by node attributes. And the edge level features are fuzzy histogram of each distribution of the values taken by edge attributes. FMGE employs fuzzy overlapping trapezoidal intervals for minimizing the information loss while mapping from continuous graph space to discrete vector space. FMGE permits graphs to benefit from state of the art computational efficient, clustering and classification tools, which originally is not possible in graph space.

Graph retrieval and subgraph spotting: Graph retrieval deals with retrieving a graph G from a graph repository, based on the similarity of graph G with an example (or query) graph.

Subgraph spotting takes the definition of graph retrieval to further granularity. Subgraph spotting refers to retrieving graph G from graph repository based on the similarity of a subgraph in G with the example (or query) graph.

III. AUTOMATIC INDEXING AND QBE BASED FOCUSED CONTENT RETRIEVAL SYSTEM

This section details our proposed system for automatic indexing and QBE based focused content retrieval in comicpage-image repositories. In Section III-A we discuss the graph representation phase of comic pages and in Section III-B we outline the indexing/retrieval phase of the system.

A. Graph representation phase

This section describes our approach for representing comicpage-images by graphs. We first extract the regions of interest in the comic-page-image and then construct an attributed region adjacency graph (RAG) for each panel in the comicpage-image.

Preprocessing comics page images: A comic-page-image contains several panels. In order to represent each panel by a RAG, we first extract the panels in the comic-page-image. For this step we employ the method proposed by Rigaud et al. in [START_REF] Rigaud | Robust Frame and Text Extraction from Comic Books[END_REF]. The method of Rigaud et al. exploits surrounding black lines of panels and text balloons in comic-page-images and uses a connected-component labeling analysis for automatically extracting the panels and text.

After splitting a page into panels, in the next step we segment each panel into regions according to selected criteria as detailed in Figure 3. The segmentation of panels into regions is a very important step and it has a great influence on construction of graphs.

In Figure 3 filtering regions refers to eliminating areas that are not important. The segmentation step creates lots of regions in panels. The black lines delimiting the region's color are not essential in our approach. A lot of small regions are also created by the segmentation step. These small regions are not useful and must be ignored for limiting the size of the Graph order

Graph size

Embedding of node degree Embedding(s) of node attribute(s) Embedding(s) of edge attribute(s) Fig. 2. Feature vector of FMGE. The feature vector is comprised of exactly one feature for each of graph order and graph size, features for node degree, features for node attributes and features for edge attributes.

Fig. 3. Pre-processing comics.

resulting graph. We have defined the criteria of compactness for calculating the proportion between the surface of the region and the bounding box that contains it. If the proportion is less than a certain threshold we ignore the region.

The preprocessing step gives us a set of regions in a panel of the comic-page-image. Each region is characterized by a list of attributes including the color, the surface and the compactness of the region. A list detailing the adjacent regions is also maintained by each region. Figure 4 provides an example for the preprocessing step of comic-page-images.

Graph construction:

The extracted regions of a panel form the list of nodes of the graph i.e. each region is represented as a node in the graph. The nodes are labeled by color, compactness and shape attributes. The color is defined in CIE-Lab color space. This color space has been designed to approximate perceptually uniform color spaces. Each region is described by a vector of three dimensions where each element corresponds respectively to the values of L (Luminance), a and b (two colors channels). A second attribute associated to the nodes is the compactness of the region. This value is calculated during the preprocessing step. The shape of the region represented by a node is a very important discriminatory characteristic. We use Hu moments because of their ease of computation and robustness to rotation, translation and scaling. These properties are necessary in our case because the comics contains many complex objects (such as the comic characters) which can be of different size (close or distant view) and can be drawn in different orientation. We extract seven values of Hu moment for each region.

Thus a node in the graph (which is representing a region in the panel) is attributed by a vector of 11 attributes. These attributes include three attributes for color, one for compactness and seven Hu moments for shape of the underlying region. Each of the attributes are normalized separately. Suppose that x i is an observed value of an attribute, x the average value and Γ the standard deviation of the attribute. The normalization is performed as follows: (x i -x) / Γ.

The edges of the graph are obtained by the spatial relationships between the regions represented by nodes of the graph. This allows us to construct a region adjacency graph (RAG) which incorporates the topological relations between the regions of the comic-page-image panel.

Among the spatial relations given in RCC-8 [START_REF] Cohn | Representing and reasoning with qualitative spatial relations about regions[END_REF], the only ones that are relevant in the case of comics are the adjacency and inclusion properties. If we consider the drawings as a set of regions, a region can only be adjacent or included in another. In our case, we use only the adjacency relation between regions to define the edges of the graph.

The label of the edges is defined from the surface area ratio of adjacent regions. We assume that the proportions between regions are preserved whether they are viewed from near or far. The ratio between the surfaces of two adjacent regions is invariant to scale.

B. Indexing and subgraph spotting phase

The system outlined in this section is reproduced from our recent work in [START_REF] Luqman | Subgraph spotting through explicit graph embedding: An application to content spotting in graphic document images[END_REF] [START_REF] Luqman | Fuzzy multilevel graph embedding[END_REF]. We achieve graph retrieval and subgraph spotting through explicit graph embedding.

As outlined in Figure 5, in our system a graph repository is automatically indexed during an off-line learning phase; where we (i) compute resemblance attributes for each node and edge in graph, (ii) break the graphs into 2-node subgraphs (a.k.a. cliques of order 2), which are primitive building-blocks of a graph, (iii) embed the 2-node subgraphs into feature vectors by employing our recently proposed explicit graph embedding technique, (iv) cluster the feature vectors in classes by employing a classic agglomerative clustering technique, (v) build an index for the graph repository and (vi) learn a Bayesian network classifier.

The subgraph spotting is achieved during the on-line querying phase; where we (i) compute resemblance attributes for each node and edge in graph, (ii) break the query graph into 2-node subgraphs, (iii) embed them into feature vectors, (iv) employ the Bayesian network classifier for classifying the query 2-node subgraphs and (v) retrieve the respective graphs by looking-up in the index of the graph repository. The graphs containing all query 2-node subgraphs are retrieved to form the set of result graphs (AG result ) for the query (AG query ).

For spotting the query graph AG query in a result graph AG result , we employ the adjacency matrix of graph AG result along-with a score function. The adjacency matrix of graph AG result has a value of "0" if there is no edge between "node 1 " and "node 2 " in the original graph AG result , a value of "1" if there is an edge between "node 1 " and "node 2 " in the original graph AG result and a value of "2" if one of the query 2-node subgraphs is classified (by Bayesian network) as belonging to the cluster of this 2-node subgraph (which is comprising of edge between "node 1 " and "node 2 "). The query graph AG query is finally spotted in the result graph AG result , by looking up in the neighborhood of each 2-node subgraph of AG result which is in the result i.e. each "AG result (i, j) = 2" in the adjacency matrix of result graph AG result . We explore "o" connected neighbors of each "AG result (i, j) = 2". The parameter "o" is proportional to the graph order of query graph AG query (|V query |). We compute a score for each "AG result (i, j) = 2" using Equation 3. The computed score of "AG result (i, j) = 2" also gives a confidence value for subgraph spotting of query graph AG query in result graph

AG result . score = 2 z=0 (z × |z| o ) (3)
where , -z is a value in the adjacency matrix (either 0,1 or 2), -|z| is number of times value z occurs in neighborhood o is number of connected neighbors that are looked-up.

IV. EXPERIMENTATION

We have evaluated the empirical performance of our proposed system on a comic-page-image. The repository was comprised of a total of 216 panels extracted from 94 comicpage-images.

As outlined in Section III-A for each of the panel image, preprocessing step was performed to extract the distinct regions in the image. These regions were employed to construct an attributed region adjacency graph (RAG) representation for the panel from comic-page-image.

After representing the panels from comic-page-image by attributed region adjacency graphs (RAGs), we employ our system outlined in Section III-B for automatically indexing these graphs. During the off-line indexing phase, first new resemblance attributes are computed from the corresponding attributes of the nodes and edges in the graph for encoding the homogeneity of the neighborhood of the nodes and edges respectively. The cliques of order-2 are extracted from the graphs and are embedded into feature vectors by employing FMGE. The feature vectors are embedded into classes by hierarchical clustering. The clusters are used as classes for learning a Bayesian network classifier and an index is built for the RAG representation of the comic-page-image repository. This index maps the comic-page-image panels -→ their graphs representations -→ cliques of order-2 -→ feature vector embedding of cliques.

The QBE based focused content retrieval is achieved by querying the system with a selected part of a comic-pageimage panel. The system represents the query image by a region adjacency graph, computes the resemblance attributes for nodes and edges, extracts order-2 cliques from the graph, embeds the cliques by FMGE feature vector and employs the Bayesian network classifier for classifying each of the cliques in the query graph. The panels containing all of the cliques of the query graph are retrieved as results of the query. Finally we employ the score function presented in Equation 3 for focusing on the interesting part of the retrieved panel.

We have tested our system for 25 query images. Figure 6 presents the precision and recall plot for the retrieval results of our system. For a 100% recall the system achieves a precision of approximately 50%. The preliminary experimentation has been performed on a limited set of comic-page-images but results are encouraging and illustrates the applicability of the proposed approach for comic-page-image indexing and QBE based focused retrieval. Given the fact that due to propriety issues there is a lack of public comic-page-image repositories, we have experimented with a home-available moderate size comic-page-image repository.

V. CONCLUSION

We have presented a system for automatic indexing of comic-page-image repository for query by example based focused content retrieval. We have modeled the problem of comic-page-image retrieval as a subgraph spotting problem. The system provides unsupervised indexing of comic-pageimage repositories and offers the ease of query by example along-with the granularity of focused retrieval. Our preliminary experimentation results are very encouraging and in future we plan to take this work forward by investigating further into the application of existing graphics recognition techniques for comic-page-image indexing/retrieval. Our future direction of research is to take forward our work by exploring cliques of higher order (≥3) for building a multi-resolution index of a graph repository. We also plan to evaluate the performance of our system on more comic-page-image repositories.

Fig. 1 .

 1 Fig. 1. Block diagram of proposed system for comic retrieval.

Fig. 4 .

 4 Fig. 4. (a)A comic page. (b) An extracted panel. (c) Panel after preprocessing.

OUTPUT 1 .Fig. 5 .

 15 Fig. 5. Automatic indexation of a graph repository.

Fig. 6 .

 6 Fig. 6. Precision and recall plot for comic-page-image retrieval.