Author name cluster

Raphaël M. Jungers

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

9 papers

2 author rows

AAAI Conference 2024 Conference Paper

Stability Analysis of Switched Linear Systems with Neural Lyapunov Functions

Virginie Debauche
Alec Edwards
Raphaël M. Jungers
Alessandro Abate

Neural-based, data-driven analysis and control of dynamical systems have been recently investigated and have shown great promise, e.g. for safety verification or stability analysis. Indeed, not only do neural networks allow for an entirely model-free, data-driven approach, but also for handling arbitrary complex functions via their power of representation (as opposed to, e.g. algebraic optimization techniques that are restricted to polynomial functions). Whilst classical Lyapunov techniques allow to provide a formal and robust guarantee of stability of a switched dynamical system, very little is yet known about correctness guarantees for Neural Lyapunov functions, nor about their performance (amount of data needed for a certain accuracy). We formally introduce Neural Lyapunov functions for the stability analysis of switched linear systems: we benchmark them on this paradigmatic problem, which is notoriously difficult (and in general Turing-undecidable), but which admits existing recently-developed technologies and theoretical results. Inspired by switched systems theory, we provide theoretical guarantees on the representative power of neural networks, leveraging recent results from the ML community. We additionally experimentally display how Neural Lyapunov functions compete with state-of-the-art results and techniques, while admitting a wide range of improvement, both in theory and in practice. This study intends to improve our understanding of the opportunities and current limitations of neural-based data-driven analysis and control of complex dynamical systems.

PDF Details DOI

MFCS Conference 2018 Conference Paper

On Randomized Generation of Slowly Synchronizing Automata

Costanza Catalano
Raphaël M. Jungers

Motivated by the randomized generation of slowly synchronizing automata, we study automata made of permutation letters and a merging letter of rank n-1. We present a constructive randomized procedure to generate synchronizing automata of that kind with (potentially) large alphabet size based on recent results on primitive sets of matrices. We report numerical results showing that our algorithm finds automata with much larger reset threshold than a mere uniform random generation and we present new families of automata with reset threshold of Omega(n^2/4). We finally report theoretical results on randomized generation of primitive sets of matrices: a set of permutation matrices with a 0 entry changed into a 1 is primitive and has exponent of O(n log n) with high probability in case of uniform random distribution and the same holds for a random set of binary matrices where each entry is set, independently, equal to 1 with probability p and equal to 0 with probability 1-p, when np-log n - > infty as n - > infty.

Details

Highlights Conference 2016 Conference Abstract

Primitive sets of nonnegative matrices and synchronizing automata

Balázs Gerencsér
Vladimir V. Gusev
Raphaël M. Jungers

A set of nonnegative matrices M={M_1, M_2, …, M_k} is called PRIMITIVE if there exist indices i_1, i_2, …, i_m such that the product M_{i_1} M_{i_2} … M_{i_m} is positive (i. e. has all its entries >0). The length of the shortest such product is called the EXPONENT of M. The concept of primitive sets of matrices comes up in a number of problems within control theory, non-homogeneous Markov chains etc. In my talk I will speak about the recently discovered connections between synchronizing automata and primitive sets of matrices. An automaton is called SYNCHRONIZING if there exist a word w and a state f such that the action of w brings all states to f. On one hand, the properties of synchronizing automata are relatively well studied due to their applications to industrial automation, coding theory, group theory, etc. On the other hand, there is still a persisting interest of the research community to the topic due to one of the most famous open problems in automata theory. Namely, the CERNY CONJECTURE states that the length of the shortest synchronizing word of an n-state automaton is at most (n-1)^2. In my talk I will explain how the aforementioned connections lead to a relatively large number of results about primitive sets of matrices. Namely, we will see that the maximal exponent among all primitive sets of n by n matrices is roughly equal to 3^(n/3). Furthermore, the problem of deciding whether a given set of matrices is primitive is PSPACE-complete. In my talk the set of matrices with no zero rows and columns, denoted by NZ, will receive a special attention due to its intriguing connections to the Cerny conjecture and the recent generalization of Perron-Frobenius theory for this class. I will characterize the computational complexity of different problems related to the exponent of NZ matrix sets, and present a quadratic bound on the exponents of sets belonging to a special subclass. Namely, we will see that the exponent of a set of matrices having total support is bounded by 2n^2 -5n +5. These results are not published. The preprint is available on http: //arxiv. org/abs/1602. 07556.

Details

STOC Conference 2010 Conference Paper

Sorting under partial information (without the ellipsoid algorithm)

Jean Cardinal
Samuel Fiorini
Gwenaël Joret
Raphaël M. Jungers
J. Ian Munro

We revisit the well-known problem of sorting under partial information: sort a finite set given the outcomes of comparisons between some pairs of elements. The input is a partially ordered set $P$, and solving the problem amounts to discovering an unknown linear extension of P, using pairwise comparisons. The information-theoretic lower bound on the number of comparisons needed in the worst case is log e(P), the binary logarithm of the number of linear extensions of $P$. In a breakthrough paper, Jeff Kahn and Jeong Han Kim (STOC 1992) showed that there exists a polynomial-time algorithm for the problem achieving this bound up to a constant factor. Their algorithm invokes the ellipsoid algorithm at each iteration for determining the next comparison, making it impractical. We develop efficient algorithms for sorting under partial information. Like Kahn and Kim, our approach relies on graph entropy. However, our algorithms differ in essential ways from theirs. Rather than resorting to convex programming for computing the entropy, we approximate the entropy, or make sure it is computed only once in a restricted class of graphs, permitting the use of a simpler algorithm. Specifically, we present: an O(n 2 ) algorithm performing O(log n ⋅ log e(P)) comparisons; an O(n 2.5 ) algorithm performing at most (1+ε) log e(P) + O ε(n) comparisons; an O(n 2.5 ) algorithm performing O(log e(P)) comparisons. All our algorithms are simple to implement.

Details

TCS Journal 2010 Journal Article

The continuous Skolem-Pisot problem

Paul C. Bell
Jean-Charles Delvenne
Raphaël M. Jungers
Vincent D. Blondel

We study decidability and complexity questions related to a continuous analogue of the Skolem-Pisot problem concerning the zeros and nonnegativity of a linear recurrent sequence. In particular, we show that the continuous version of the nonnegativity problem is NP-hard in general and we show that the presence of a zero is decidable for several subcases, including instances of depth two or less, although the decidability in general is left open. The problems may also be stated as reachability problems related to real zeros of exponential polynomials or solutions to initial value problems of linear differential equations, which are interesting problems in their own right.

Details DOI

STOC Conference 2009 Conference Paper

An efficient algorithm for partial order production

Jean Cardinal
Samuel Fiorini
Gwenaël Joret
Raphaël M. Jungers
J. Ian Munro

We consider the problem of partial order production: arrange the elements of an unknown totally ordered set T into a target partially ordered set S, by comparing a minimum number of pairs in T. Special cases of this problem include sorting by comparisons, selection, multiple selection, and heap construction.

Details

TCS Journal 2009 Journal Article

On the number of α -power-free binary words for 2 < α ≤ 7 / 3

Vincent D. Blondel
Julien Cassaigne
Raphaël M. Jungers

We study the number u α ( n ) of α -power-free binary words of length n, and the asymptotics of this number when n tends to infinity, for a fixed rational number α in ( 2, 7 / 3 ]. For any such α, we prove a structure result that allows us to describe constructively the sequence u α ( n ) as a 2 -regular sequence. This provides an algorithm that computes the number u α ( n ) in logarithmic time, for fixed α. Then, generalizing recent results on 2 + -free words, we describe the asymptotic behaviour of u α ( n ) in terms of joint spectral quantities of a pair of matrices that one can efficiently construct, given a rational number α. For α = 7 / 3, we compute the automaton and give sharp estimates for the asymptotic behaviour of u α ( n ).

Details DOI

TCS Journal 2009 Journal Article

Overlap-free words and spectra of matrices

Raphaël M. Jungers
Vladimir Y. Protasov
Vincent D. Blondel

Overlap-free words are words over the binary alphabet A = { a, b } that do not contain factors of the form x v x v x, where x ∈ A and v ∈ A ∗. We analyze the asymptotic growth of the number u n of overlap-free words of length n as n → ∞. We obtain explicit formulas for the minimal and maximal rates of growth of u n in terms of spectral characteristics (the joint spectral subradius and the joint spectral radius) of certain sets of matrices of dimension 20 × 20. Using these descriptions we provide new estimates of the rates of growth that are within 0. 4 % and 0. 03 % of their exact values. The best previously known bounds were within 11 % and 3 %, respectively. We then prove that the value of u n actually has the same rate of growth for “almost all” natural numbers n. This average growth is distinct from the maximal and minimal rates and can also be expressed in terms of a spectral quantity (the Lyapunov exponent). We use this expression to estimate it. In order to obtain our estimates, we introduce new algorithms to compute the spectral characteristics of sets of matrices. These algorithms can be used in other contexts and are of independent interest.

Details DOI

TCS Journal 2009 Journal Article

Testing avoidability on sets of partial words is hard

F. Blanchet-Sadri
Raphaël M. Jungers
Justin Palumbo

We prove that the problem of deciding whether a finite set of partial words is unavoidable is NP-hard for any alphabet of size larger than or equal to two, which is in contrast with the well-known feasability results for unavoidability of a set of full words. We raise some related questions on avoidability of sets of partial words.

Details DOI