Natalia Dück

Irene Márquez-Corbella

Edgar Martínez-Moro

On the fan associated to a linear code *

Keywords: Linear code, Gröbner basis, Gröbner fan

We will show how one can compute all reduced Gröbner bases with respect to a degree compatible ordering for code ideals -even though these binomial ideals are not toric. To this end, the correspondence of linear codes and binomial ideals will be briefly described as well as their resemblance to toric ideals. Finally, we will hint at applications of the degree compatible Gröbner fan to the code equivalence problem.

Introduction

The Gröbner fan of an ideal in the commutative polynomial ring consists of polyhedral cones indexing the different leading ideals and is thus the geometric collection of all reduced Gröbner bases for this ideal. One application of the Gröbner fan is the so-called Gröbner walk which is the conversion of Gröbner bases.

With the software system TiGERS in [START_REF] Huber | Computing Gröbner fans of toric ideals[END_REF] (Toric Gröbner bases Enumeration by Reverse Search) an efficient alternative for computing the Gröbner fan has been provided for the special case of toric ideals. Indeed, by identifying a reverse search Natalia Dück Hamburg University of Technology, Germany e-mail: natalia.dueck@tuhh.de Irene Márquez-Corbella INRIA Saclay-École Polytechnique, France e-mail: irene.marquez-corbella@inria.fr Edgar Martínez-Moro Institute of Mathematics, University of Valladolid, Spain e-mail: edgar@maf.uva.es tree on the cones of the Gröbner fan, a memory-less combinatorial Gröbner walk can be established that furthermore, requires no cost weight vectors.

Linear codes, on the other hand, can be linked to this whole subject by associating to each linear code a binomial ideal that encodes the information about the code in the exponents. This correspondence proved to be very beneficial as it provided new approaches to several well-known problems in coding theory. Almost all applications, however, require the computation of a degree compatible Gröbner basis.

In this work, it will be shown how methods from the software system TiGERS developed by Rekha R. Thomas (see [START_REF] Huber | Computing Gröbner fans of toric ideals[END_REF]) can be modified in order to compute all reduced Gröbner bases with respect to a degree compatible ordering for code ideals -even though these binomial ideals are not toric. To this end, the correspondence of linear codes and binomial ideals will be briefly described as well as their resemblance to toric ideals. Finally, we will hint at applications of the degree compatible Gröbner fan to the code equivalence problem.

The degree compatible Gröbner fan

In this work we shall use the notion of Gröbner basis and the ideal associated to a linear code. Due to the restriction of the space we will not define what a Gröbner basis is, the reader can find a good introductory text for example in [START_REF] Cox | Ideals, varieties, and algorithms: An introduction to computational algebraic geometry and commutative algebra[END_REF]. Also for simplicity we will restrict ourselves to binary linear codes even if all the computation could be done in general (see [START_REF] Márquez-Corbella | On the ideal associated to any linear code[END_REF] for the ideal associated to a q-ary linear code).

Let K[x] be the polynomial ring with variables x = x 1 , . . . , x n and coefficients an arbitrary field K. We will define the ideal associated to a binary linear code C of length n as

I = I(C ) = {x ∆ a -x ∆ b | a -b ∈ C } ⊆ K[x],
where the operation ∆ means substitute the 0, 1 elements in the binary field F 2 by the corresponding 0, 1 in the set of integers Z. In this extended abstract the ∆ will be omitted if no confusion arises to simplify the notation.

This binomial ideal has been proved valuable for several applications and captures the combinatorial properties of the code (see [START_REF] Márquez-Corbella | Algebraic structure of the minimal support codewords set of some linear codes[END_REF] and the references therein). Note that for those applications K can be the binary field, which is the usual election, and in this case we must explicitly mark which terms are the leading terms.

In this paper it shall be assumed that the leading term of a binomial is the one with coefficient 1 and the non leading term has coefficient -1. Abusing the notation if K is the binary field, since 1 ≡ -1, this writing of the binomials will be assumed as a formal pointer (in [START_REF] Huber | Computing Gröbner fans of toric ideals[END_REF] the leading terms were underlined).

Note also that the explicit knowledge of the underlying term order is not necessary. In fact, in all the following computations only the leading term of each binomial has to be known.

In the rest of the paper we will use the following notation and concepts from [START_REF] Huber | Computing Gröbner fans of toric ideals[END_REF]:

• G (I) is the reduced Gröbner basis for the ideal I w.r.t. the monomial order , • C (I) is the Gröbner cone corresponding to G (I).

• T (I) is the reverse search tree for the ideal I as constructed in [START_REF] Huber | Computing Gröbner fans of toric ideals[END_REF]Definition 2.5] Note that in [START_REF] Huber | Computing Gröbner fans of toric ideals[END_REF] the complete Gröbner fan is considered, i.e., the whole R n , since the considered toric ideals are homogeneous w.r.t. a certain grading. This is not the case for our code ideal and so here the Gröbner fan is considered only in R n + .

Proposition 1.

[4] Let be a term order and v ∈ C (I). For any u ∈ R n holds

lt u (I) = lt v (I) ⇐⇒ lt u (g) = lt v (g) ∀ g ∈ G (I),
where lt u stands for the leading (initial) term (ideal) induced by the order given by the weight vector u.

Note that it is a well known fact that a reduced Gröbner basis for an ideal I w.r.t. a certain monomial order is degree compatible if and only if the corresponding Gröbner cone contains the all-one vector 1. From a coding-theory point of view, degree compatible orderings are the ones one must analyze since the weight of a vector is translated on the degree of a monomial. In this sense degree compatible orderings provide us a test set for the code and therefore a gradient descent decoding algorithm, see [START_REF] Borges-Quintana | Gröbner bases and combinatorics for binary codes[END_REF]. The following proposition characterizes when there is a unique degree compatible Gröbner basis. (1)

Proof. Assume that (1) holds but there is another Gröbner basis G for I(C ) w.r.t. another degree compatible order . Since is degree compatible, lt (g) = lt (g) for all g ∈ G . And by Proposition 1 we see that lt (I(C )) = lt (I(C )) and thus, G = G . Or equivalently, we can argue that the all-one vector is in the interior of the cone C (I(C )) and so clearly it cannot be contained in another cone in the Gröbner fan.

In order to show the other direction assume that (1) does not hold, i.e., there is at least one binomial

x a -x b in G such that deg(x a ) = deg(x b ). Then 1 / ∈ Int(C (I(C ))
) and in particular, there must be a neighbouring cone that also contains 1 and thus corresponds to a degree compatible ordering.

In terms of the Gröbner fan the above proposition can also be expressed as follows: A reduced Gröbner basis G w.r.t. a degree compatible ordering is the only degree compatible Gröbner basis if and only if the all-one vector 1 lies in the interior of the Gröbner cone of G .

We say that two binary linear codes C 1 and C 2 are permutation equivalent provided there is a permutation of coordinates which sends C 1 to C 2 . In the same fashion two binomial degree compatible Gröbner bases are permutation equivalent if there is a permutation of the variables that transforms one into the other. There is a close relationship between code equivalence and the equivalence of the degree compatible Gröbner bases associated to their code ideals stated as follows: If the two degree compatible Gröbner bases are permutation equivalent so are the codes, unfortunately the converse is not true, given two permutation equivalent codes not all the degree compatible Gröbner bases are permutation equivalent (only two of them should be). The reader can see [START_REF] Borges-Quintana | On a Gröbner bases structure associated to linear codes[END_REF] for a proof of this discussion.

Indeed if one has only a unique degree compatible Gröbner basis for a given code (Proposition 2) checking permutation equivalence is reduced to checking if the two unique bases are permutation equivalent using the techniques in [START_REF] Borges-Quintana | On a Gröbner bases structure associated to linear codes[END_REF]. If this is not the case one needs to compute the whole set of degree compatible Gröbner bases which we call the degree compatible Gröbner fan. We will tackle this task in the following section.

Adapting the TiGERS strategy

We can adapt the TiGERS Algorithm in [START_REF] Huber | Computing Gröbner fans of toric ideals[END_REF] for computing the degree compatible Gröbner fan for I(C ) as follows: We start with a degree compatible Gröbner basis (note that this basis can be computed by the algorithm stated in [START_REF] Borges-Quintana | On a Gröbner bases structure associated to linear codes[END_REF]). By Proposition 2 we can determine whether it is the only degree compatible Gröbner basis or not. If not, we flip only those facet binomials where both terms have the same degree and recompute the Gröbner basis. Unfortunately due the lack of space these steps can not be detailed in this extended abstract but they are showed in [START_REF] Huber | Computing Gröbner fans of toric ideals[END_REF]. Lemma 1 below guarantees that we will always find at least one facet binomial where both terms have the same degree. Additionally, we can employ the reverse search tree defined in [START_REF] Huber | Computing Gröbner fans of toric ideals[END_REF] for traversing the Gröbner cones that are degree compatible.

Lemma 1. Let G be the reduced Gröbner basis for I(C ) w.r.t. a degree compatible ordering. If G is not the only degree compatible Gröbner basis, that is 1 / ∈ Int(C(I(C ))), then among all the facet binomials of G is at least one binomial

x α -x β such that deg(x α ) = deg(x β ). Proof. Let G = x α i -x β i | 1 ≤ i ≤ j + k and order the binomials such that deg(x α i ) > deg(x β i ) for 1 ≤ i ≤ j and deg(x α i ) = deg(x β i ) for 1 + j ≤ i ≤ j + k.
Assume that all facet binomials are such that the degree of the leading term is strictly greater than the degree of the other term. Then the cone

C = u ∈ R n + | α i • u ≥ β i • u for all 1 ≤ i ≤ j equals the Gröbner cone C(I(C )) of the Gröbner basis G . But then 1 ∈ Int(C ) = Int(C(I(C )))
, which is a contradiction.

Lemma 2. Let G new be the reduced Gröbner basis obtained from G old by flipping the facet binomial x αx β . Any new leading terms in G new , i.e., leading terms of G new that do not appear in G old , are divisible by x α .

Proof. Any new leading terms arise from the Gröbner basis computation of the quasi-monomial ideal

T := x β -x α ∪ T , T := x α i | x α i -x β i ∈ G old
that consists of the designated flipping binomial with changed leading term and all the other leading terms in G old . To be more precise, a new leading term arises from an S-polynomial of the form

S x β -x α , x α i = x γ x α , where x γ = lcm(x β , x α i )/x β ,
which is not being reduced to zero by the elements in T . When computing Gröbner basis, then this S-polynomial is either reduced to zero or its remainder on division by the set T is added to the Gröbner basis of T . We distinguish the following situations:

1. Neither x β nor any monomial in T divides x γ x α : The monomial x γ x α cannot be further reduced and thus is being attached to the Gröbner basis of T . 2. A monomial in T divides x γ x α : The monomial x γ x α is being reduced to zero and thus, this S-polynomial results in no new term. 3. The monomial x β divides x γ x α : Since x α and x β have disjoint support (see [START_REF] Borges-Quintana | Gröbner bases and combinatorics for binary codes[END_REF]),

x β has to divide x γ , the monomial x γ x α is reduced to

x γ x α -x α x γ x β x β -x α = x γ x β (x α ) 2 .
So, whenever the S-polynomial cannot be reduced to zero, we obtain a monomial which is divisible by x α .

Proposition 3. T (I(C )) is an acyclic directed graph with a unique sink that we will call the reverse search tree.

Proof. We prove that T (I(C )) is a tree by showing that there is no cycle in this construction. We show this by contradiction. For the other claims see the proof of [START_REF] Huber | Computing Gröbner fans of toric ideals[END_REF]Theorem 2.6].

Assume that there is a cycle in the reverse search tree, say

G 1 -→ G 2 -→ . . . -→ G -→ G 1
, where G i+1 is obtained from G i by flipping along x α i -x β i . Then G i contains this binomial with leading term x α i and G i+1 with leading term x β i . Inspecting the cycle we see that the binomial x α 1 -x β 1 lies in G 1 with leading term x α 1 and appears in G 2 with leading term x β 1 . Then no binomial in G 2 has the leading term x α 1 . However, as we arrive at G 1 after flipping steps, we conclude that x α 1 -x β 1 must be inserted at some successive flipping step. Assume that this happens in the i 1 th flipping process, 1 < i 1 ≤ . Then by Lem. 2, x α 1 is divisible by x α i 1 . And since G 1 is a Gröbner basis this implies that x α i 1 cannot be the leading term of any element in G 1 ; it must have been inserted as a new leading term during some preceding flipping step, say i 2 < i 1 . By the same argument the monomial x α i 1 is divisible by x α i 2 and then x α i 2 cannot appear as the leading term of any element in G 1 . Continuing this process we get a decreasing sequence of indices i 1 > i 2 > i 3 > . . . which eventually must terminate, say after k steps, i.e., i k = 1. Then x α i k = x α 1 and from the divisibility relations

x α i k | x α i k-1 | . . . | x α i 2 | x α i 1 |
x α 1 we actually obtain equality of all leading terms of the flipping binomials. However, this is a contradiction.

The following proposition states the discussion at the end of Section 2.

Proposition 4. Two linear codes C 1 and C 2 are permutation-equivalent if and only if they have the same degree compatible Gröbner fan structure, i.e., there is permutation σ ∈ S n such that σ (G f an(C 1 )) = G f an(C 2 ), where σ (G f an(C 1 )) means permuting the variables in each of the degree compatible Gröbner basis within the fan.

Example 1. Consider two binary [START_REF] Márquez-Corbella | Algebraic structure of the minimal support codewords set of some linear codes[END_REF][START_REF] Cox | Ideals, varieties, and algorithms: An introduction to computational algebraic geometry and commutative algebra[END_REF] codes C 1 and C 2 with respective parity check matrices Example 2 and 5] it is shown that these codes are not permutation-equivalent. Here, we show how the degree compatible Gröbner fans of both codes can be employed to show their non-equivalence. The degree compatible Gröbner fan for C 1 consists of 8 Gröbner basis which are all of cardinality 6 (see Ex. 2). The Gröbner basis for C 2 w.r.t. the grevlex basis is given by

H 1 =   1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1   , H 2 =   1 1 1 1 1 1 0 0 0 1 0 1 0 1 0 1 0 0   In [2,
{x 3 -x 5 , x 1 -x 5 , x 4 x 5 -x 2 x 6 , x 2 x 5 -x 4 x 6 , x 2 x 4 -x 5 x 6 } ∪ x 2 i -1 | i = 2, 4, 5, 6
and consists of 9 elements. Thus, we can already conclude that these two codes cannot be permutation-equivalent.

Example 2. The reverse search tree T (I(C )) for the binary [START_REF] Márquez-Corbella | Algebraic structure of the minimal support codewords set of some linear codes[END_REF][START_REF] Cox | Ideals, varieties, and algorithms: An introduction to computational algebraic geometry and commutative algebra[END_REF] code C 1 from the previous example with being pure lex is given in Fig. 1.

And the Gröbner bases are (the flipping binomials are underlined)

G 1 = x 1 -x 2 , x 3 -x 4 , x 5 -x 6 , x 2 2 -1, x 2 4 -1, x 2 6 -1 G 2 = x 1 -x 2 , x 4 -x 3 , x 5 -x 6 , x 2 2 -1, x 2 3 -1, x 2 6 -1 G 3 = x 2 -x 1 , x 4 -x 3 , x 5 -x 6 , x 2 1 -1, x 2 3 -1, x 2 6 -1 G 4 = x 1 -x 2 , x 3 -x 4 , x 6 -x 5 , x 2 2 -1, x 2 4 -1, x 2 5 -1 G 5 = x 1 -x 2 , x 4 -x 3 , x 6 -x 5 , x 2 2 -1, x 2 3 -1, x 2 5 -1 G 6 = x 2 -x 1 , x 4 -x 3 , x 6 -x 5 , x 2 1 -1, x 2 3 -1, x 2 5 -1 G 7 = x 2 -x 1 , x 3 -x 4 , x 6 -x 5 , x 2 1 -1, x 2 4 -1, x 2 5 -1 G 8 = x 2 -x 1 , x 3 -x 4 , x 5 -x 6 , x 2 1 -1, x 2 4 -1, x 2 6 -1 . G 1 G 2 G 4 G 8 G 3 G 5 G 7 G 6
Fig. 1 The reverse search tree for C 1

Conclusions

We have shown how the computation of the degree compatible Gröbner fan of a code is useful for determining the code equivalence problem. Anyway one can not forget that this is an NP-problem and therefore the Gröbner basis computation comprises a hard step. Further research in the topic points toward analyzing heuristic techniques for eliminating the need of transverse the whole fan or at least for trying to deduce the answer from partial information about the initial Gröbner basis.

Proposition 2 .

 2 Let G be a reduced Gröbner basis for I(C ) w.r.t. a certain degree compatible ordering . The Gröbner basis G is the only reduced degree compatible Gröbner basis for I(C ) if and only if deg(x a ) > deg(x b ) for all x ax b ∈ G .

* First author is partially supported by a grant of the Deutscher Akademischer Austauschdienst. Second and third authors are supported by the Spanish MINECO grant MTM2012-36917-C03-03. 1


Irene Márquez-Corbella
email: irene.marquez-corbella@inria.fr

Ruud Pellikaan

Error-correcting pairs: a new approach to code-based cryptography

Keywords: Code-based cryptography, error-correcting pairs, McEliece cryptosystem

McEliece proposed the first public-key cryptosystem based on linear error-correcting codes. A code with an efficient bounded distance decoding algorithm is chosen as secret key. It is assumed that the chosen code looks like a random code. The known efficient bounded distance decoding algorithms of the families of codes proposed for code-based cryptography, like Reed-Solomon codes, Goppa codes, alternant codes or algebraic geometry codes, can be described in terms of error-correcting pairs (ECP). That means that, the McEliece cryptosystem is not only based on the intractability of bounded distance decoding but also on the problem of retrieving an error-correcting pair from the public code. In this article we propose the class of codes with a t-ECP whose error-correcting pair that is not easily reconstructed from of a given generator matrix.

Introduction

The notion of Public Key Cryptography was first introduced in 1976 by Diffie and Helman. The problem of building Public Key Cryptosystems (PKC) is tied to the problem of making trapdoor primitives. Roughly, a trapdoor function is easy to compute but hard to invert except if you possess some "trapdoor" information. It is stated that "At the heart of any public-key cryptosystem is a one-way function -a function y = f (x) that is easy to evaluate but for which is computationally infeasible (one hopes) to find the inverse x = f -1 (y)".

The most famous trapdoor one-way functions are:

• Integer factorization where x = (p, q) is a pair of prime numbers and y = pq is its product. The best-known example of PKC is the Rivest-Shamir-Adleman (RSA) cryptosystem whose security is based on the hardness of factoring prime numbers from composite number, i.e. the intractability of inverting this one-way function.

• Discrete logarithm for which a group G (written multiplicatively) and an element a ∈ G are required, then x is an integer and y = a x . The security of the ElGamal cryptosystem or the Diffie-Hellman key exchange depends on the difficulty of finding discrete logarithms modulo a large prime.

• Elliptic curve discrete logarithm which it is actually a particular case of the previous function when G (written additively) is taken as an elliptic curve group. Then x = P is a point on the curve and y = kP is another point on the curve obtained by the multiplication of P with a scalar k. Elliptic Curve Cryptography (ECC) proposed independently by Koblitz and Miller in 1985 is based on the difficulty of this function in the group of points on an elliptic curve over a finite field.

Only two years after the introduction of PKC, McEliece proposed the first PKC based on the theory of Error-correcting codes. Compared to RSA and discrete logarithm based schemes, McEliece has the advantage to resist quantum attacks so far, this property makes this scheme an interesting candidate for post-quantum cryptography. The security of this scheme relies on the difficulty of decoding a random code. Another advantage consists of its fast encryption and decryption schemes. However, its major drawback is the large size of the keys required to have a good security level.

McEliece encryption scheme: Let F be any family of linear codes with an efficient decoding algorithm. Every element of this family is represented by the triple (C, A C , t) where A C denotes an efficient decoding algorithm for C ∈ F correcting all patterns of t errors. The McEliece scheme can be summarized as follows:

Key generation: Consider any element (C, A C , t) ∈ F. Let G be a generator matrix of C. Then the public key and the private key are given respectively by

K pub = (G, t) and K secret = A C .
Encryption: y = mG + e where m is the message and e is a random error vector of weight at most t.

Decryption: Using K secret , the receiver obtains m.

Let K be the collection of all generator matrices of a chosen class of codes that have an efficient decoding algorithm that corrects all patterns of t errors. The security of McEliece cryptosystem is based on two assumptions: A.1 In the average it is difficult to decode t errors for all codes that have the same parameters as the codes used as key.

A.2 It is difficult to distinguish arbitrary codes from those coming from K.

Concerning the first assumption it might be that the class of codes is too small or too rigid. Recent progress is made with respect to the second assumption by [START_REF] Faugere | A distinguisher for high-rate McEliece cryptosystems[END_REF][START_REF] Couvreur | Distinguisherbased attacks on public-key cryptosystems using Reed-Solomon codes. Designs, Codes and Cryptography[END_REF] where it is shown that one can distinguish between high rate Goppa, alternant and random codes.

In its original algorithm McEliece proposed the use of binary Goppa codes. Many attempts to replace Goppa codes by different families of codes have been proven to be insecure such as Generalized Reed-Solomon codes proposed in [START_REF] Niederreiter | Knapsack-type cryptosystems and algebraic coding theory[END_REF], subcodes of them in [START_REF] Berger | How to mask the structure of codes for a cryptographic use[END_REF], Binary Reed-Muller codes in [START_REF] Sidelnikov | On the insecurity of cryptosystems based on generalized Reed-Solomon codes[END_REF] or Algebraic Geometry codes in [START_REF] Janwa | McEliece public cryptosystem using algebraic-geometric codes[END_REF]; all of these schemes are subject to polynomial or sub-exponential time attacks [START_REF] Sidelnikov | On the insecurity of cryptosystems based on generalized Reed-Solomon codes[END_REF][START_REF] Minder | Cryptanalysis of the Sidelnikov cryptosystem[END_REF][START_REF] Wieschebrink | Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes[END_REF][START_REF] Couvreur | A polynomial time attack against algebraic geometry code based public key cryptosystems[END_REF].

It was shown in [START_REF] Pellikaan | On decoding by error location and dependent sets of error positions[END_REF] that the known efficient bounded distance decoding algorithms of Reed-Solomon, BCH, Goppa and algebraic geometry codes can be described by a basic algorithm using an error correcting pair. That means that for such classes of codes the security of the McEliece cryptosystem is not only based on the inherent intractability of bounded distance decoding but also on the one-way function

x = (A, B) → y = A * B,
where (A, B) is a t-error-correcting pair. The aim of this paper is to study the subclass of linear codes formed by those linear codes C whose error correcting pair is not easily reconstructed from C. In [START_REF] Couvreur | Cryptanalysis of public-key cryptosystems that use subcodes of algebraic geometry codes[END_REF][START_REF] Couvreur | A polynomial time attack against algebraic geometry code based public key cryptosystems[END_REF] an attack is presented against algebraic geometry codes and subcodes of them, this attack consists of the computation of an ECP in order to decode the public code. Take notice that this attack is neither a generic decoding attack like Information Set Decoding, nor a structural attack as the structure of the code is not retrieved. It corresponds, rather, to a cryptanalysis of the new trapdoor function of code-based cryptography as presented above.

Error-correcting pairs

From now on the dimension of a linear code C will be denoted by k(C) and its minimum distance by d(C). Given two elements a and b in F n q , the Schur product is defined by coordinatewise multiplication, that is a * b = (a 1 b 1 , . . . , a n b n ). While the standard inner product is defined by a • b = n i=1 a i b i . In general, for two subsets A and B of F n q the set A * B is given by

A * B := a * b | a ∈ A and b ∈ B
For B = A, then A * A is denoted as A (2) . A new, we define A (t) by induction: A (1) = A and A (t+1) = A * A (t) for any positive integer t. Furthermore, we denote by A ⊥ B if a • b = 0 for all a ∈ A and b ∈ B.

Definition 1. Let C be a linear code in F n q . A pair (A, B) of F q m -linear codes of length n is called a t-error correcting pair (ECP) for C if the following conditions hold:

E.1 (A * B) ⊥ C, E.2 k(A) > t, E.3 d(B ⊥ ) > t, E.4 d(A) + d(C) > n.
The notion of an error-correcting pair for a linear code was introduced by Pellikaan [START_REF] Pellikaan | On decoding by error location and dependent sets of error positions[END_REF] and independently by Kötter [START_REF] Kötter | A unified description of an error locating procedure for linear codes[END_REF]. It is shown that a linear code in F n q with a t-error correcting pair has a decoding algorithm which corrects up to t errors with complexity O mn) 3 .

Examples of existence of ECP for many known codes

Example 1 (Generalized Reed-Solomon codes). Let a be an n-tuple of mutually distinct elements of F q and b be an n-tuple of nonzero elements of F q . Then the generalized Reed-Solomon code GRS k (a, b) is defined by

GRS k (a, b) = {(f (a 1 )b 1 , . . . , f (a n )b n ) | f (X) ∈ F q [X] and deg(f (X)) < k} .
Define by induction a 1 = a and a i+1 = a * a i . Then GRS k (a, b) is generated by the elements b * a i with i = 0, . . . , k -1. If k ≤ n ≤ q, then GRS k (a, b) is an [n, k, n -k + 1] code. Furthermore the dual of a GRS code is again a GRS code, in particular GRS k (a, b) ⊥ = GRS n-k (a, c) for some c that is explicitly known.

GRS codes are the prime examples of codes that have a t-ECP. Indeed, let

A = GRS t+1 (a, b), B = GRS t (a, c) and C = GRS 2t (a, b * c) ⊥ . Then (A, B) is a t-ECP for C. Conversely let C = GRS k (a, b), then A = GRS t+1 (a, c) and B = GRS t (a, 1) is a t-ECP for C where t = n-k 2 and c ∈ F n q is a nonzero vector such that GRS k (a, b) ⊥ = GRS n-k (a, c).
Moreover if C is an [n, n -2t, 2t + 1] code which has a t-error-correcting pair, then C is a GRS code. This is trivial if t = 1, proved for t = 2 in [17, Theorem 6.5] and for arbitrary t in [START_REF] Márquez-Corbella | A characterization of MDS codes that have an errorcorrecting pair[END_REF].

The family of GRS codes was mentioned by Niederreiter [START_REF] Niederreiter | Knapsack-type cryptosystems and algebraic coding theory[END_REF] for the McEliece cryptosystem as an attempt to shorten the key size (since GRS are MDS codes) while keeping the same security level in comparison to the classical binary Goppa codes. However GRS codes have been proven to be insecure by Sidelnikov-Shestakov [START_REF] Sidelnikov | On the insecurity of cryptosystems based on generalized Reed-Solomon codes[END_REF].

Example 2 (Algebraic geometry codes). Let X be a smooth projective geometrically connected curve over a finite field F q of genus g, P = (P 1 , . . . , P n ) be an n-tuple of mutually distinct F qrational points of X and E be a divisor of X of degree m with disjoint support from P.

The algebraic geometry (AG) code C L (X , P, E) of length n over F q is the image of the Riemann-Roch space L(E) of rational functions with prescribed behavior of zeros and poles at E under the evaluation map ev P : L(E) -→ F n q defined by ev P (f ) = (f (P 1 ), . . . , f (P n )). If A = C L (X , P, E) and B = C L (X , P, F ), then A * B ⊆ C L (X , P, E + F ), so there are abundant ways of constructing error-correcting pairs of an AG code. Indeed, the codes (A, B) defined by A = C L (X , P, F ) and B = C L (X , P, E -F ) with deg(E) > deg(F ) ≥ t + g is a t-ECP for C L (X , P, E) ⊥ , where g is the genus of the curve X , see [START_REF] Pellikaan | On decoding by error location and dependent sets of error positions[END_REF]Theorem 3.3]. Such a pair (A, B) for C L (X , P, E) ⊥ always exists whenever deg(E) > 2g -2. Moreover, if e is sufficiently large, then there exists a t-ECP over F q e with t = (d * -1)/2 by [17, Proposition 4.2].

AG codes have efficient decoding algorithms that correct up to half the designed minimum distance which makes them particularly appealing for code-based cryptography. Janwa and Moreno [START_REF] Janwa | McEliece public cryptosystem using algebraic-geometric codes[END_REF] proposed to use the collection of AG codes and their subfield subcodes for the McEliece cryptosystem. The proposal of using AG code is broken; firstly by Faure and Minder [START_REF] Faure | Cryptanalysis of the McEliece cryptosystem over hyperelliptic codes[END_REF] for codes on curves of genus g ≤ 2 and recently, for arbitrary genus in [START_REF] Márquez-Corbella | On the unique representation of very strong algebraic geometry codes[END_REF][START_REF] Márquez-Corbella | Computational aspects of retrieving a representation of an algebraic geometry code[END_REF] and [START_REF] Couvreur | A polynomial time attack against algebraic geometry code based public key cryptosystems[END_REF] where the authors propose a polynomial time attack on the code length.

Example 3 ((Subfield) subcodes). Let C be an F q -linear code that is a (subfield)subcode of an F q m -linear code D that has (A, B) as t-ECP. Then condition (E. Although the PKC with GRS codes is completely broken, subsequent variants [START_REF] Berger | How to mask the structure of codes for a cryptographic use[END_REF][START_REF] Wieschebrink | Two NP-complete Problems in Coding Theory with an Application in Code Based Cryptography[END_REF] were proposed in a bid to hide the strong algebraic structure of these codes but without success. The main idea is to use subcodes of the original GRS codes rather than the GRS code itself. See [START_REF] Wieschebrink | Cryptanalysis of the Niederreiter public key scheme based on GRS subcodes[END_REF][START_REF] Márquez-Corbella | The non-gap sequence of a subcode of a generalized Reed-Solomon code[END_REF][START_REF] Couvreur | Distinguisherbased attacks on public-key cryptosystems using Reed-Solomon codes. Designs, Codes and Cryptography[END_REF] for several cryptanalysis of these schemes. Recall that GRS codes is the subclass of AG codes on the projective line, that is the algebraic curve of genus zero. For the general case, the proposal of using subcodes of AG codes is also not secure [START_REF] Couvreur | Cryptanalysis of public-key cryptosystems that use subcodes of algebraic geometry codes[END_REF].

Example 4 (Alternant codes). Let C be a subfield subcode of a code D that has (A, B) as a t-ECP, then (A, B) is also a t-ECP for C.

Let a be an n-tuple of mutually distinct elements of F q m and b be an n-tuple of nonzero elements of F q m . The alternant code Alt r (a, b) is the F q -linear restriction: Alt r (a, b) = F n q ∩ GRS r (a, b) ⊥ . Therefore, let us define the codes A = GRS t+1 (a, 1) and B = GRS t (a, b) over F q m , then (A, B) is a t-ECP over F q m for Alt 2t (a, b).

Example 5 (Goppa codes). A Goppa code associated to a Goppa polynomial of degree r can be viewed as an alternant code.Therefore this family of codes has an r 2 -error correcting pair. In the binary case with an associated square free polynomial the Goppa code has an r-ECP.

The McEliece cryptosystem with Goppa codes is still unbroken for suitable parameters choices.

Distinguishing a code with an ECP

Let K be a collection of generator matrices of codes that have a t-ECP. In this section we address assumption A.2 whether we can distinguish arbitrary codes from those coming from K.

Theorem 1. Let C be an [n, k] code with n > k+1 2 chosen at random. Then the dimension of the square code C (2) is equal to k+1 2 with high probability.

Proof. See [START_REF] Márquez-Corbella | Error-correcting pairs for a public-key cryptosystem[END_REF]Proposition 2]. This theorem could be used for detecting the family of codes that have an ECP since this family have a different behavior from the one that one would expect from a random code. If t(t + 1) < n, then the dimension of A * B is at most t(t + 1). Moreover, in [13, Appendix A] we have shown that the dimension of C is equal to n -t(t + 1) for random choices of A and B.

Let D = C ⊥ , then dim(D (2) ) ≤ t + 2 2 t + 1 2

which is about half the expected t(t+1) 2 in case t(t+1)

2

< n by Theorem 1.

  1) holds for (A, B) with respect to D, i.e. a * b • d = 0 for all d in D. Hence a * b • c = 0 for all c in C, since C ⊆ D. Moreover, conditions (E.2), (E.3) and (E.4) hold. So (A, B) is also a t-ECP for C.

Remark 1 .

 1 Let (A, B) be a pair of codes with parameters [n, t + 1, n -1] and [n, t, n -t + 1], respectively; and define the code C = (A * B) ⊥ , then (A, B) is a t-ECP for C by [17, Corollary 3.4].


Mikhail Kryachkov

Andrey Polyakov

Graph-based Field Automata for Modeling of Sliding Mode Systems

A novel hybrid automaton admitting the modeling of both conventional and modern sliding mode systems is presented. A scheme for defining hybrid-automaton executions beyond Zeno points is proposed. Conventional and Filippov-like executions of the hybrid automaton are introduced and studied.

I. INTRODUCTION

Sliding mode control is an important branch of modern control theory attracting an interest of both research and practicing engineer communities [START_REF] Utkin | Sliding Mode Control in Electro-Mechanical Systems[END_REF], [START_REF] Shtessel | Sliding Mode Control and Observation[END_REF]. Sliding mode control systems are usually modeled by ordinary differential equations with discontinuous right hand sides [START_REF] Filippov | Differential equations with discontinuous right-hand sides, Mathematics and Its Applications[END_REF]. In this case, system dynamics is governed by a control feedback that is discontinuous with respect to the current state. Frequently, it is important to consider a wider class of control laws which depend on both current and previous states of the system. In particular, such control laws appear for time-delay systems with sliding modes, see for example, [START_REF] Polyakov | Minimization of Disturbances Effects in Time Delay Predictor-based Sliding Mode Control System[END_REF]. Another example is presented in the paper [START_REF] Bartolini | On the Finite-Time Stabilization of Uncertain Nonlinear Systems With Realtive Degree Three[END_REF], which introduces two control functions and a switching logic between them in order to stabilize the triple integrator. The resulting control law is a function of the state and its prehistory. It ensures finite-time reaching and existence of the 3rd order sliding mode at the origin of the closed-loop system. The sliding mode is realized by infinitely fast switching between the control functions. Expansion of the same ideas to integrator chains had required to introduce a special finite automaton describing the logic of switchings between several control functions [START_REF] Kryachkov | Finite-time stabilization of an integrator chain using only signs of the state variables[END_REF].

Systems combining continuous and discrete dynamics are known as hybrid automata [START_REF] Lygeros | Controllers for reachability specifications for hybrid systems[END_REF]. Although hybrid automata are widely studied, modeling of systems with sliding motion under this framework is a challenging problem [START_REF] Navarro-López | Hybrid-automaton models for simulating systems with sliding motion: Still a challenge[END_REF], [START_REF] Navarro-López | Hybrid automata: an insight into the discrete abstraction of discontinuous systems[END_REF], [START_REF] Drakunov | Sliding modes in hybrid systems -a semigroup approach[END_REF]. The main obstacle here is Zeno behavior: infinite number of switchings in a finite time interval. According to standard notion [START_REF] Lygeros | Dynamical properties of hybrid automata[END_REF], executions of hybrid automata are not defined beyond Zeno points. In fact, in the majority of works, Zeno behavior is considered pathological and avoided [START_REF] Heymann | Analysis of Zeno behaviors in a class of hybrid systems[END_REF]. However, Zeno-like behavior of sliding mode is one of the main working principles of VSS [START_REF] Utkin | Sliding Modes in Control and Optimization[END_REF].

In this paper we propose a systematic approach for defining hybrid-automaton executions beyond Zeno points, which is applicable to a wide class of hybrid automata, namely, automata with the identity reset relation.

The paper is organized as follows. The second section gives well-known definitions of hybrid automata, nondeterministic finite automata and their executions. In the third section some examples of Zeno hybrid automata are considered. It is shown that the set of switching instances can have a complicated structure preventing straightforward step-by-step prolongation of executions. The fourth section introduces a novel representation of non-resettable hybrid automata called graph-based field automata. The fifth section deals with graph-based field initial value problems which are discrete analogs for the Cauchy problem. In the sixth section, executions of graph-based field automata are defined. Peanolike existence theorem for executions of graph-based field automata is stated.

II. HYBRID AND NONDETERMINISTIC FINITE AUTOMATA A. Hybrid automata

Let us recall well-known definitions concerning hybrid systems [START_REF] Lygeros | Controllers for reachability specifications for hybrid systems[END_REF], [START_REF] Lygeros | Dynamical properties of hybrid automata[END_REF].

By P(S) denote the powerset of a set S, i.e., the set of all subsets of S. Throughout the paper, A ⊂ B means that A is a subset of B including the case A = B. By |S| denote the number of elements of S.

Definition 1: A hybrid automaton H is a tuple (Q, X, Init, Dom, f , E, G, R), where

• Q ⊂ N is a set of discrete states or locations; • X = R n is a set of continuous states; • Init ⊂ Q × X is a set of initial states; • Dom(•) : Q → P(X) is a domain; • f (•, •) : Q × X → R n is a vector field; • E ⊂ Q × Q is a set of edges; • G(•) : E → P(X) is a guard condition; • R(•, •) : E × X → P(X) is a reset map.
Elements of the tuple H have the following meaning. A domain Dom(q) and continuous dynamics described by f (q, •) are assigned to each location q ∈ Q. Usually, the functions f (q, •) : X → R n are Lipschitz continuous in X. But we don't address the uniqueness issues in this paper and f are only supposed to be continuous in X. Also suppose that Q is finite. The pair (Q, E) is a directed graph that defines possible discrete state transitions. A guard condition G(e) is assigned to each edge e ∈ E. The current state of the hybrid automaton is defined by a pair (q, x), where q ∈ Q and x ∈ X. H starts evolving at some state (q 0 , x 0 ) ∈ Init. Then a series of evolution steps follows. Each of these steps is either a continuous evolution of x or an instant discrete state transition. If x ∈ G(e), then the transition defined by e is allowed. If x leaves Dom(q), then the transition is obligatory.

Definition 2: A hybrid time trajectory τ = {I i } N i=0 is a finite or infinite sequence of intervals I i ⊂ R such that • for all 0 ≤ i < N, I i = [τ i , τ i+1 ] with τ i ≤ τ i+1 ; • if N < ∞, either I N = [τ N , τ N+1 ] with τ N ≤ τ N+1 < ∞, or I N = [τ N , τ N+1 ) with τ N < τ N+1 ≤ ∞. Definition 3:
An execution of a hybrid automaton H is a tuple (τ, q, x), where

• τ = {I i } N i=0 is a hybrid time trajectory; • q = {q i } N i=0 is a sequence of q i ∈ Q; • x = {x i (•)} N i=0 is a sequence of x i (•) : I i → X; • (q 0 , x 0 (τ 0 )) ∈ Init; • for all i < N, 1) (q i , q i+1 ) ∈ E, 2) x i (τ i+1 ) ∈ G(q i , q i+1 ), 3) x i+1 (τ i+1 ) ∈ R(q i , q i+1 , x i (τ i+1 ));
• for all i with τ i < τ i+1 , 1) for all t ∈ I i , ẋi

(t) = f (q i , x i (t)), 2) for all t ∈ [τ i , τ i+1 ), x i (t) ∈ Dom(q i ). An execution (τ, q, x) is called infinite if τ is an infinite sequence or ∑ N i=0 (τ i+1 -τ i ) = ∞. An execution (τ, q, x) is called Zeno if τ is an infinite sequence and ∑ ∞ i=0 (τ i+1 -τ i ) < ∞. The instant τ ∞ = τ 0 + ∑ ∞ i=0 (τ i+1 -τ i ) is called a Zeno point. A Zeno execution (τ, q, x) is called chattering Zeno if there exists a number C ∈ N such that τ i = τ i+1 for all i > C.
Otherwise, (τ, q, x) is called genuinely Zeno.

The following new definitions are introduced for the needs of this paper. Let D = q∈Q Dom(q). A hybrid automaton H is called uniformly non-blocking if Init = Q × D and for every (q , x ) ∈ Init there exists an infinite execution (τ, q, x) of H such that q 0 = q and x 0 (τ 0 ) = x . A hybrid automaton H is called non-resettable if for every e ∈ E and x ∈ X, R(e, x) = {x}. A hybrid automaton H is called closed if all sets Dom(q) and G(e) are closed in D.

B. Nondeterministic finite automata

Hybrid automata are based on nondeterministic finite automata, which will be exploited further in the paper.

Definition 4: A nondeterministic finite automaton is a tuple (Q, ∆, Init), where

• Q is a finite set of states; • ∆ : Q → P(Q) is a transition relation; • Init ⊂ Q is a set of initial states.
The transition relation ∆ defines a graph (Q, γ), where Q is the set of vertices and γ is the set of edges. Let (p, q) ∈ γ iff q ∈ ∆(p). Assume that P(q) is non-empty for every q ∈ Q.

Definition 5: A sequence {q i } N i=0 , where q i ∈ Q, is called an execution of a nondeterministic finite automaton (Q, ∆, Init) if 1) q 0 ∈ Init;

2) for all i < N, (q i , q i+1 ) ∈ γ.

It is natural to consider multivalued executions for nondeterministic finite automata.

Definition 6: A sequence {Q i } N i=0 , where

Q i ⊂ Q and Q i = / 0, is called a multivalued execution of a nondeterministic finite automaton (Q, ∆, Init) if 1) Q 0 ⊂ Init;
2) for all i < N and for every p ∈ Q i , there exists q ∈ Q i+1 such that (p, q) ∈ γ, 3) for all i < N and for every q ∈ Q i+1 , there exists p ∈ Q i such that (p, q) ∈ γ. Obviously, any multivalued execution {Q i } N i=0 is a union of single-valued executions {q i } N i=0 such that q 0 ∈ Q 0 . III. MOTIVATING EXAMPLES Let us consider some examples of uniformly non-blocking non-resettable hybrid automata that model well-known sliding mode systems, which behavior has been already studied. Therefore we know how executions of the considered automata should be prolonged beyond Zeno points. 1), R(e, x) = {x} (see Fig. 1). One can see that any infinite execution of H C is chattering Zeno. E.g., suppose a > 0 and (τ, q, x) is an infinite execution of H C such that τ 0 = 0, x 0 (0) = a, and q 0 = 2. The first time interval of τ is I 0 = [0, 0] and it corresponds to the instant transition from q = 2 to q = 1. After that, q 1 = 1 and continuous state x evolves on I 1 = [0, a]: x 1 (t) = at. As x reaches the origin, only instant transitions between q = 1 and q = 2 are possible. Hence q 2 j = 2, q 2 j+1 = 1, j = 0, 1, . . ., and I i = [a, a], i = 2, 3, . . .. Time in the hybrid time trajectory τ stops progressing and gets stuck at a Zeno point τ ∞ = a.

A. Chattering system

Consider a hybrid automaton

H C with Q = {1, 2}, X = R, Init = Q × X, Dom(1) = [0, +∞), Dom(2) = (-∞, 0], f (1, x) = -1, f (2, x) = 1, E = {(1, 2), (2, 1)}, G(1, 2) = Dom(2), G(2, 1) = Dom(
The automaton H C is a model for the following differential equation with a discontinuous right-hand side:

ẋ = -sgn x, (1)
which has a solution x ≡ 0 in the Filippov sense [START_REF] Filippov | Differential equations with discontinuous right-hand sides, Mathematics and Its Applications[END_REF]. The automaton H C can be augmented by an additional discrete state 3 with f (3, x) = 0 [START_REF] Johansson | Simulation of Zeno hybrid automata[END_REF], [START_REF] Navarro-López | Hybrid-automaton models for simulating systems with sliding motion: Still a challenge[END_REF]. In that case, executions of the augmented automaton can be continued beyond τ ∞ by the transition to the state 3.

q = 1 q = 2 x = -1 x = 1 x 0 ≥ x 0 ≤ . . x 0 ≤ x 0 ≥ e=(1,2) e=(2,1)

B. Twisting system

Consider the twisting controller [START_REF] Levant | Higher order sliding modes[END_REF] described by

ẍ = - b + s 2 sgn x - b -s 2 sgn ẋ, (2)
where b > s > 0 are positive constants. It can be modeled by a hybrid automaton

H T with Q = {1, 2, 3, 4}, X = R 2 = {x, ẋ}, Init = Q × X, Dom(1) = {(x, ẋ) : x ≥ 0, ẋ ≥ 0}, Dom(2) = {(x, ẋ) : x ≥ 0, ẋ ≤ 0}, Dom(3) = {(x, ẋ) : x ≤ 0, ẋ ≤ 0}, Dom(4) = {(x, ẋ) : x ≤ 0, ẋ ≥ 0}, f (1, x, ẋ) = ( ẋ, -b), f (2, x, ẋ) = ( ẋ, -s), f (3, x, ẋ) = ( ẋ, b), f (4, x, ẋ) = ( ẋ, s), E = {(i, j) : i ∈ Q, j ∈ Q, i = j}, G(i, j) = Dom( j), R(e, x, ẋ) = {(x, ẋ)}.
For any initial state (q 0 , x 0 , ẋ0 ), where x 0 = 0 or ẋ0 = 0, an infinite execution (τ, q, x, ẋ) of H T is genuinely Zeno (see Fig. 2). Discrete state q changes in a loop 1 → 2 → 3 → 4 → 1. Due to the homogeneity properties of (2), the lengths of the intervals

I i = [τ i , τ i+1 ] form a decreasing geometric progression: τ i+2 -τ i = α(τ i -τ i-2 ), i = 3, 4, . . ., where α = s/b < 1. Hence τ i → τ ∞ < ∞ as i → ∞.
In addition, x → 0 and ẋ → 0 as t → τ ∞ . After t = τ ∞ , x ≡ 0 is a second order sliding mode solution for (2). Similar to the example of the chattering system, an auxiliary discrete state (a Zeno state [START_REF] Zhang | Dynamical Systems Revisited: Hybrid Systems with Zeno Executions[END_REF]) z can be added to H T , but that is not enough for prolongation of executions beyond τ ∞ . One should amend the definitions of the hybrid time trajectory and execution to allow transitions to Zeno states after an infinite sequence of time intervals that converges to τ ∞ < ∞.

x x . x = -b x = -s x = b x = s q = 1 q = 2 q = 3 q = 4 .. .. .. ..

IV. GRAPH-BASED FIELD AUTOMATA

In this section we introduce a different representation of non-resettable hybrid automata that is helpful in the study of executions beyond Zeno points.

Definition 7: A graph-based field automaton H is a tuple (N m , R n , A, Init, f , γ), where

• N m = {1, 2, . . . , m} is a finite set of discrete states; • R n is a set of continuous states; • A ⊂ R × R n is a set of points (t, x) (a domain); • Init ⊂ N m × A is a set of initial states; • f (•, •) : N m × A → R n is a vector field; • γ(•) : A → P(N m × N m ) is a graph-based field assigning
a set of edges to each point (t, x) ∈ A. Notice that non-resettable hybrid automata and graphbased field automata are not the same technically. The former uses one graph (Q, E) and the latter exploits many graphs: a graph (N m , γ(t, x)) for each point (t, x) ∈ A. A non-resettable hybrid automaton requires guard conditions to specify the area G(e) for each edge e ∈ E, where the corresponding transition can occur. In graph-based field automata, these conditions are defined implicitly by a proper choice of the graph-based field γ. If a graph-based field automaton does not depend on time, the two notions are equivalent as we will see.

If A = R × A x , where A x ⊂ R n , and functions f (s,t, x) and γ(t, x) do not depend on t, then H is called an autonomous graph-based field automaton.

Let us define a bijection assigning an autonomous graphbased field automaton H to every non-resettable hybrid automaton H . Recall definition 1 of H and set m = |Q|. Let s ∈ N m correspond to q s ∈ Q. Let A = R × q∈Q Dom(q). Finally, for every (t, x) ∈ A, define γ(t, x) as follows: (i, j) ∈ γ(t, x), i = j, iff x ∈ G(q i , q j ); and (i, i) ∈ γ(t, x) iff x ∈ Dom(q i ).

The left and the right limits of a function s(t) at a point t are denoted by s(t -0) and s(t + 0). Definition 8: A pair (s, x), where s :

[a, b) → N m and x : [a, b) → R n , is called a classical execution of a graph-based field automaton H if 1) s is a piecewise continuous on every [a, c] ⊂ [a, b); 2) x is a piecewise differentiable on every [a, c] ⊂ [a, b); 3) (s(
(t) = s(t -0) or s(t) = s(t + 0); 8) at the point t = a, if it is discontinuity point of s(t),
there is a path from s(a) to s(a + 0) in γ(a, x(a)). Classical executions of graph-based field automata are introduced to model executions of non-resettable hybrid automata. When discrete state q changes in a non-resettable hybrid automaton, continuous state x doesn't jump. Hence we can consider one continuous function x(t) instead of the set {x i (t)} N i=0 of continuous functions defined on a hybrid time trajectory. Conditions 1 and 2 of definition 8 are chosen especially to model hybrid time trajectories. In hybrid automata, several instant transitions can happen at the same moment. As continuous state x doesn't change in non-resettable hybrid automata during a sequence of instant transitions, we are only interested in the first and the last discrete states of this sequence. That is why conditions 7 and 8 deal with paths in the graph γ(t, x(t)).

Classical executions of autonomous graph-based field automata and non-resettable hybrid automata are equivalent in the following sense. Let H correspond to H by the constructed bijection. We can assign an execution (τ, q, x) = ({I i }, {q i }, {x i (t)}) of H to every execution (s, x) of H. Indeed, consider a set Θ of discontinuity points of s(t).

Obviously, Θ is finite or countable, Θ = {θ k } M k=1 , a ≤ θ k < θ k+1 < b for all k = 1, 2, . . . , M -1, and θ k → b as k → ∞ if M = ∞. To each interval J 0 = [a, θ 1 ], J 1 = [θ 1 , θ 2 ], . . ., J M = [θ M , b) (if M < ∞)
we assign an interval I i k = J k of the hybrid time trajectory τ. Let q i k = s(t k ), where t i is an interior point of J k . Let x i k : I i k → R n be defined as follows: x i k (t) = x(t). To each θ ∈ Θ we assign several (may be 0) intervals

[τ i , τ i+1 ], [τ i+1 , τ i+2 ], . . ., [τ i+l , τ i+l+1 ] of τ such that τ i = τ i+1 = . . . = τ i+l+1
. Let these intervals correspond to vertices of the path from s(θ -0) (or s(a) if θ = a) to s(θ + 0) in γ(θ , x(θ )). Hence we can construct an execution (τ, q, x) of H . Similarly, we can assign an execution (s, x) of H to every execution (τ, q, x) of H such that ∑ N i=0 (τ i+1τ i ) > 0. Thus, autonomous graph-based field automata with classical executions are equivalent to non-resettable hybrid automata. Of course, definition 8 doesn't allow sliding modes as definition 3 doesn't define executions that go beyond Zeno points. In the sequel, we will amend definition 8 in order to allow executions of graph-based field automata being prolonged beyond Zeno points. Let us revisit the example of the chattering system. Consider a graph-based field automaton

H C = (N 2 , R, A, Init, f , γ) corresponding to H C . Here, A = R × R, Init = N 2 × A, f (1,t, x) = -1, f (2,t, x) = 1, γ(t, 0) = γ 0 , γ(t, x) = γ 1 when x > 0,
and γ(t, x) = γ 2 when x < 0, where γ 0 = {(1, 1), (1, 2), (2, 1), (2, 2)}, γ 1 = {(1, 1), (2, 1)}, and γ 2 = {(2, 2), (1, 2)}. In the sliding mode solution x ≡ 0 of (1), ẋ belongs to the convex hull of 1 and -1 by the definition of Filippov [START_REF] Filippov | Differential equations with discontinuous right-hand sides, Mathematics and Its Applications[END_REF], which infers that the discrete state s should also be some "combination" of states 1 and 2. Consider a nondeterministic finite automaton (Q, ∆, Init), where Q = N 2 and ∆ is constructed by γ 0 : ∆(1) = ∆(2) = {1, 2}. Notice that the automaton accepts multivalued executions of the form Q i = {1, 2}, i = 0, 1, . . .. Further on, the idea of using multivalued executions will be exploited in the general definition of graph-based field automata executions.

V. GRAPH-BASED FIELD INITIAL VALUE PROBLEMS

Recall definition 8 and notice that conditions 1, 6, 7, and 8 describe the form of s(t). Suppose that x(t) is already known and fixed, then a graph-based field γ(t) = γ(t, x(t)) is well defined. Given γ(t), conditions 1, 6, 7, and 8 can be considered separately from the other conditions of definition 8. Thus we have an interval [a, b), a graph-based field γ : [a, b) → P(N m × N m ), and some set of initial states Init s ⊂ N m , where s(a) ∈ Init s . We need to determine s(t) on [a, b). That looks like an initial value problem for ordinary differential equations. In this section we will investigate the properties of graph-based field initial value problems.

Notice that the condition "s(t) is a piecewise continuous on every [a, c] ⊂ [a, b)" implies that b is the only accumulation point of the set Θ of discontinuity points of s(t). This restriction on the form of s(t) prevents going beyond Zeno points. Therefore we should consider a wider class of functions s(t). Secondly, the example of the graphbased field automaton H C infers that we should consider multivalued state functions S(t). Thirdly, definition 8 works with paths in the graph (N m , γ), and hence it is convenient to use the transitive closure Γ instead of γ. I.e., (p, q) ∈ Γ iff there exists a path from vertex p to vertex q in γ: (p, s 1 ), (s 1 , s 2 ), . . . , (s j , q) ∈ γ.

We call a number s ∈ N m a partial limit of a multivalued function S : T → P(N m ) at a point t ∈ T iff there exists a sequence {t i }, i = 1, 2, . . ., such that t i → t as i → ∞, t i = t, and s ∈ S(t i ) for for every i = 1, 2, . . .. If t i < t, then s is called a left partial limit. Similarly, if t i > t, then s is called a right partial limit. By P S (t) denote the set of all partial limits of a function S at the point t. Similarly, by P S (t -0) and P S (t + 0) denote the sets of left and right partial limits of a function S at the point t.

Definition 9: Let T ⊂ R be an interval. A function S : T → P(N m ) is called an admissible function for a graph-based field Γ : T → P(N m × N m ) if 1) for any t ∈ T , S(t) is not empty; 2) for any t ∈ T , P S (t) ⊂ S(t);

3) for any interior point t ∈ T and for any s ∈ S(t), s ∈ P S (t) or there exist p ∈ P S (t) and q ∈ P S (t) such that (p, s) ∈ Γ(t) and (s, q) ∈ Γ(t); 4) for any interior point t ∈ T and for any s -∈ P S (t -0), there exists s + ∈ P S (t + 0) such that (s -, s + ) ∈ Γ(t); 5) for any interior point t ∈ T and for any s + ∈ P S (t + 0), there exists s -∈ P S (t -0) such that (s -, s + ) ∈ Γ(t); 6) if t ∈ T is the left endpoint of T , then for any s ∈ S(t), there exists s + ∈ P S (t + 0) such that (s, s + ) ∈ Γ(t); 7) if t ∈ T is the right endpoint of T , then for any s ∈ S(t), there exists s -∈ P S (t -0) such that (s -, s) ∈ Γ(t). Condition 2 of definition 9 means that S(t) is a βcontinuous multivalued function [START_REF] Filippov | Differential equations with discontinuous right-hand sides, Mathematics and Its Applications[END_REF]. Notice that conditions 4 and 5 are analogous to conditions 2 and 3 of definition 6 of multivalued executions of nondeterministic finite automata.

By the initial value problem for a graph-based field on an interval T = [a, b] (or T = [a, b)) we mean looking for an admissible function that satisfies the initial condition S(a) = S 0 .

Let P ⊂ N m and Q ⊂ N m be two disjoint sets such that P ∪ Q = N m . We say that a graph-based field Γ : T → P(N m ×N m ) disallows transitions from the set P to the set Q at the point t ∈ T iff there are no edges (p, q) such that (p, q) ∈ Γ(t), p ∈ P, and q ∈ Q.

Lemma 1: Let a function S : T → P(N m ) be admissible for a graph-based field Γ :

T → P(N m × N m ). Let Γ disallow transitions from P to Q in a neighborhood O of the point t ∈ T . Then: 1) if S(t) ∩ Q = / 0, then S(τ) ∩ Q = / 0 for any τ ≤ t, τ ∈ O; 2) if S(t) ⊂ Q, then S(τ) ⊂ Q for any τ ≤ t, τ ∈ O; 3) if S(t) ∩ P = / 0, then S(τ) ∩ P = / 0 for any τ ≥ t, τ ∈ O; 4) if S(t) ⊂ P, then S(τ) ⊂ P for any τ ≥ t, τ ∈ O.
Let us define an analog of single-valued admissible function for a graph-based field, namely a connected admissible function.

Definition 10: An admissible function S : T → P(N m ) for a graph-based field Γ :

T → P(N m × N m ) is called connected if 1
) for any t ∈ T except the left endpoint of T and for any p -∈ P S (t -0) and q -∈ P S (t -0), (p -, q -) ∈ Γ(t) and (q -, p -) ∈ Γ(t); 2) for any t ∈ T except the right endpoint of T and for any p + ∈ P S (t + 0) and q + ∈ P S (t + 0), (p + , q + ) ∈ Γ(t) and (q + , p + ) ∈ Γ(t). Notice that if there exists a set C ⊂ N m such that for any p ∈ C and q ∈ C, (p, q) ∈ Γ(t) for all t ∈ T , then S(t) = C is a connected admissible function for Γ. Sets like C are called strongly connected components. Suppose there are two sets of vertices P and Q that are disconnected by Γ(t) and there is an admissible function S that has values from both of P and Q at some point t ∈ T . Then S can be decomposed into two admissible function S 1 and S 2 such that S 1 (t) ⊂ P and S 2 (t) ⊂ Q. Connected admissible functions are admissible functions decomposed up to strongly connected components.

For some graph-based fields, there may be no admissible functions at all. Now we propose sufficient conditions for a graph-based field to have an admissible function.

A graph-based field Γ : T → P(N m × N m ) is called closed if for any t ∈ T the following conditions hold:

1) for any sequence {t i }, i = 1, 2, . . ., such that t i → t as i → ∞ and (p, q) ∈ Γ(t i ) for every i = 1, 2, . . ., the inclusion (p, q) ∈ Γ(t) holds, 2) Γ(t) coincides with its transitive closure.

A graph-based field Γ : T → P(N m × N m ) is called nonblocking if for any t ∈ T and for any p ∈ N m , there exists (p, q) ∈ Γ(t).

Consider a non-resettable hybrid automaton H and a continuous function

x : T → R n . Let a graph-based field automaton H = (N m , R n , A, Init, f , γ) correspond to H . By Γ(t, x) denote the transitive closure of γ(t, x). If H is closed, then Γ(t, x(t)) is closed. If H is uniformly non-blocking, then Γ(t, x(t)) is non-blocking.
It turns out that an initial value problem for a closed nonblocking graph-based field is feasible in connected admissible functions. In order to show that, we consider sequences of approximate admissible functions.

Let {Γ i (t)}, i = 1, 2, . . ., be a sequence of graph-based fields, where Γ i : T → P(N m × N m ). Let us construct a graph Γ (t) as follows: (p, q) ∈ Γ (t) iff there exist two sequnces {t k } and {i k }, k = 1, 2, . . ., such that t k → t and i k → ∞ as k → ∞, and (p, q) ∈ Γ i k (t k ) for every k = 1, 2, . . .. By Γ(t) denote the transitive closure of Γ (t). We call Γ(t) a limit graph-based field of {Γ i (t)}.

Lemma 2: A limit graph-based field is a closed graphbased field.

Let {S i (t)}, i = 1, 2, . . ., be a sequence of admissible functions for graph-based fields Γ i (t), where S i : T → P(N m ). Let Γ(t) be the limit graph-based field of {Γ i (t)}. Let us construct a function S (t) as follows: s ∈ S (t) iff there exist two sequences {t k } and {i k }, k = 1, 2, . . ., such that t k → t and i k → ∞ as k → ∞, and s ∈ S i k (t k ) for every k = 1, 2, . . .. Given the function S (t), construct a function S(t): s ∈ S(t) iff s ∈ S (t) or there exist p ∈ S (t) and q ∈ S (t) such that (p, s) ∈ Γ(t) and (s, q) ∈ Γ(t). We call S(t) a limit function of {S i (t)}.

Theorem 1: Let S(t) be the limit function of a sequence {S i (t)}, i = 1, 2, . . ., of admissible functions for graph-based fields Γ i (t). Let Γ(t) be the limit graph-based field of {Γ i (t)}. Then S(t) is admissible function for Γ(t).

Theorem 2: Let S(t) be the limit function of a sequence {S i (t)}, i = 1, 2, . . ., of connected admissible functions for graph-based fields Γ i (t). Let Γ(t) be the limit graph-based field of {Γ i (t)}. Then there exists a connected admissible function S c (t) ⊂ S(t) for Γ(t).

Let δ > 0 be a positive constant and Γ : T → P(N m × N m ) be a graph-based field. By Γ δ (t) denote the graph-based field τ∈[t-δ ,t+δ ],t∈T Γ(τ). By Γ δ (t) denote the transitive closure of Γ δ (t). 1) x(t) is absolutely continuous on T ;

2) for all t ∈ T , (t, x(t)) ∈ A;

3) almost everywhere on T ,

ẋ(t) ∈ co s∈S(t) f (s,t, x(t)); (3)
4) S(t) is a connected admissible function for the graphbased field Γ(t), where Γ(t) is the transitive closure of γ(t, x(t)). By the initial value problem for a graph-based field automaton on an interval T = [a, b] (or T = [a, b)) we mean looking for an execution that satisfies the initial conditions: x(a) = x 0 and s 0 ∈ S(a). We exploit Euler's polygonal lines to prove that the initial value problem for a closed non-blocking graph-based field automaton has a solution.

By ρ(x, y) denote the Euclidean distance between two points x ∈ R n and y ∈ R n . By definition, ρ(X,Y ) = inf x∈X,y∈Y ρ(x, y) for any sets X ⊂ R n and Y ⊂ R n . By M δ we denote a closed δ -neighborhood of a set M ⊂ R n , i.e., the set of all points x ∈ R n such that ρ(x, M) ≤ δ . Similarly, by F(τ δ , ξ δ ) we denote the union of all values of F(t, x) where t ∈ τ δ and x ∈ ξ δ , i.e., t ∈ [τδ , τ + δ ] and ρ(x, ξ ) ≤ δ .

Definition 12: Let δ > 0 be a positive constant. A pair (S, x), where S : T → P(N m ) and x : T → R n , is called a δ -execution of a graph-based field automaton H (or an approximate execution with an accuracy of δ ) if:

1) x(t) is absolutely continuous on T ;

2) for all t ∈ T , (t δ , x(t) δ ) ⊂ A;

3) almost everywhere on T , Theorem 5: Let H = (N m , R n , A, Init, f , γ) be a closed non-blocking graph-based field automaton. For any interior point (t 0 , x 0 ) ∈ A and s 0 ∈ N m , there exists an execution (S, x) of H such that x(t 0 ) = x 0 and s 0 ∈ S(t 0 ).

ẋ(t) ∈   co s∈S(t δ ) f (s,t δ , x(t) δ )   δ ; 4) S(
If A contains a cylinder Z = {(t, x) : t 0 ≤ t ≤ t 0 + a, ρ(x, x 0 ) ≤ b}, then the execution exists at least on the interval [t 0 ,t 0 + d], where Recall that a classical execution (s, x) of H can be assigned to every execution (τ, q, x) of non-resettable hybrid automaton H such that ∑ N i=0 (τ i+1τ i ) > 0. Lemma 5: Let the pair (s, x) be a classical execution of a graph-based field automaton H. Then the pair (S, x), where S(t) = {s(t -0), s(t), s(t + 0)}, is an execution of H. Theorem 6: Let A ⊂ R × R n be a bounded set and f : A → R n be a piecewise continuous function on A [START_REF] Filippov | Differential equations with discontinuous right-hand sides, Mathematics and Its Applications[END_REF]. Consider a differential equation with a discontinuous right-hand side ẋ = f (t, x).

(4)

There exists a graph-based field automaton H with the following properties:

• for any solution x(t) of ( 4), there exists S(t) such that (S, x) is an execution of H; • for any execution (S, x) of H, x(t) is a solution of (4). Recall the example of the graph-based field automaton H C that models the chattering system. Consider an initial problem for H C on the interval [0, +∞) with arbitrary x 0 ∈ R and s 0 ∈ N 2 . For every x 0 and s 0 , there exists an execution (S, x) of H C such that x(0) = x 0 and s 0 ∈ S(0). Moreover, x(t) is defined for all t ≥ 0 and unique. E.g., suppose x 0 > 0 and s 0 = 1. Then (S, x) has the following form: x(t) = x 0t when t ∈ [0, x 0 ], x(t) = 0 when t ∈ [x 0 , +∞), S(t) = {1} when t ∈ [0, x 0 ), and S(t) = {1, 2} when t ∈ [x 0 , +∞). Notice that S(t) is multivalued on [x 0 , +∞) indicating sliding motion.

Consider a graph-based field automaton H T = (N 4 , R 2 , A, Init, f , γ) corresponding to the twisting hybrid automaton H T , where A = R × R 2 and Init = N 4 × A. Graph-based field γ has the following form: (i, j) ∈ γ(t, x, ẋ) iff (x, ẋ) ∈ Dom( j). Similarly, for every initial x 0 , ẋ0 , and s 0 , there exists a unique execution (S, x) of H T on [x 0 , +∞). As was shown previously, the twisting hybrid automaton goes through an infinite sequence of transitions by a genuine Zeno point τ ∞ . After t = τ ∞ , the pair (S, x), where S(t) = {1, 2, 3, 4} and x(t) = 0, is a sliding mode execution of H T .

VII. CONCLUSION

Execution prolongation beyond Zeno points by means of regularization was proposed in [START_REF] Johansson | On the regularization of Zeno hybrid automata[END_REF]. Filippov hybrid automata with additional sliding states applicable for modeling of first order sliding motion were introduced in [START_REF] Johansson | Simulation of Zeno hybrid automata[END_REF], [START_REF] Navarro-López | Hybrid-automaton models for simulating systems with sliding motion: Still a challenge[END_REF]. This paper describes a regularization scheme for general nonresettable hybrid automata capable of higher order sliding mode control modeling.

Fig. 1 .

 1 Fig. 1. Chattering hybrid automaton

Fig. 2 .

 2 Fig. 2. Phase portrait of the twisting hybrid automaton

Lemma 3 :

 3 Let T be an interval[a, b] or [a, b) and Γ : T → P(N m × N m ) be a non-blocking graph-based field. For any δ > 0 and any initial condition s 0 ∈ N m , there exists a connected admissible function S δ (t) for Γ δ (t) such that s 0 ∈ S δ (a).Lemma 4: Let Γ : T → P(N m × N m ) be a closed graphbased field and {δ i }, i = 1, 2, . . ., be a sequence of positive numbers such that δ i → 0 as i → ∞. By Γ * (t) denote the limit graph-based field of {Γ δ i (t)}. Then Γ * = Γ. Theorem 3: Let T be an interval [a, b] or [a, b) and Γ : T → P(N m × N m ) be a closed non-blocking graph-based field. Then for any initial condition s 0 ∈ N m , there exists a connected admissible function S(t) for Γ(t) such that s 0 ∈ S(a). VI. EXECUTION EXISTENCE FOR GRAPH-BASED FIELD AUTOMATA By coV denote the convex hull of a set of vectors V ⊂ R n . The following definition extends definition 8 of classical executions for graph-based field automata. It plays the same role for non-resettable hybrid automata as the Filippov regularization does for differential equations with discontinuous right hand sides. Definition 11: Let T ⊂ R be an interval. A pair (S, x), where S : T → P(N m ) and x : T → R n , is called an execution of a graph-based field automaton H = (N m , R n , A, Init, f , γ) if:

d

  = min a, b m , m = sup N m ,Z | f (s,t, x)|.

  t) is a connected admissible function for the graphbased field Γ δ (t), where Γ δ (t) is the transitive closure of γ(t δ , x(t) δ ). Theorem 4: Let H be a closed graph-based field automaton. Let {(S i , x i )}, i = 1, 2, . . ., be a sequence of δ i -executions of H on an interval [a, b], where δ i → 0 as i → ∞. Let x i (t) uniformly converges to x(t) on [a, b], and (t, x(t)) ∈ A for any t ∈ [a, b]. Let S(t) be the limit function of {S i (t)}. Then there exists a connected admissible function S c (t) ⊂ S(t) such that (S c , x) is an execution of H on [a, b].

Faculty of Applied Mathematics, Informatics and Mechanics, Voronezh State University, Universitetskaya pl. 1, 394006 Voronezh, Russia kryachkovm@gmail.com

Non-A team, Inria Lille-Nord Europe, Parc Scientifique de la Haute Borne, 40, avenue Halley, Bat. A, Park Plaza, 59650 Villeneuve d'Ascq, France andrey.polyakov@inria.fr