Search

Your search keyword '"Laboratoire d'Informatique Gaspard-Monge (LIGM)"' showing total 1,494 results
Start Over Author "Laboratoire d'Informatique Gaspard-Monge (LIGM)" Publication Year Range Last 10 years
1,494 results on '"Laboratoire d'Informatique Gaspard-Monge (LIGM)"'

1. Random polytopes and the wet part for arbitrary probability distributions

Author

Matthieu Fradelizi, Xavier Goaoc, Alfredo Hubard, Imre Bárány, Günter Rote, Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences (MTA), Laboratoire d'Analyse et de Mathématiques Appliquées (LAMA), Université Paris-Est Marne-la-Vallée (UPEM)-Fédération de Recherche Bézout-Université Paris-Est Créteil Val-de-Marne - Paris 12 (UPEC UP12)-Centre National de la Recherche Scientifique (CNRS), Geometric Algorithms and Models Beyond the Linear and Euclidean realm (GAMBLE ), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Algorithms, Computation, Image and Geometry (LORIA - ALGO), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique Gaspard-Monge (ligm), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), Institut für Informatik [Berlin], Freie Universität Berlin, Rényi Institute of Mathematics, University College London, Université Paris-Est, Université de Lorraine, ANR-17-CE40-0017,ASPAG,Analyse et Simulation Probabilistes des Algorithmes Géométriques(2017), Centre National de la Recherche Scientifique (CNRS)-Université Paris-Est Créteil Val-de-Marne - Paris 12 (UPEC UP12)-Fédération de Recherche Bézout-Université Paris-Est Marne-la-Vallée (UPEM), Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Department of Algorithms, Computation, Image and Geometry (LORIA - ALGO), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria), Goaoc, Xavier, Analyse et Simulation Probabilistes des Algorithmes Géométriques - - ASPAG2017 - ANR-17-CE40-0017 - AAPG2017 - VALID, Imre. Barany was supported by the Hungarian National Research, Development and Innovation Office NKFIH Grants K 111827 andK 116769, and by the Bézout Labex (ANR-10-LABX-58). Xavier Goaoc was supported by Institut Universitaire de France. The authors are grateful for the hospitality during the ASPAG (ANR-17-CE40-0017) workshop on geometry, probability, and algorithms in Arcachon in April 2018., ANR-10-LABX-0058,Bézout,Models and algorithms: from the discrete to the continuous(2010), and Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Inria Nancy - Grand Est

Subjects
Convex hull, [MATH.MATH-PR] Mathematics [math]/Probability [math.PR], Uniform distribution (continuous), Random polytopes, Convex set, Ocean Engineering, Polytope, [MATH] Mathematics [math], 01 natural sciences, Measure (mathematics), Upper and lower bounds, Combinatorics, 010104 statistics & probability, FOS: Mathematics, Mathematics::Metric Geometry, 60D05, [MATH]Mathematics [math], 0101 mathematics, Mathematics, Probability measure, Epsilon-nets, Probability (math.PR), 010102 general mathematics, [MATH.MATH-PR]Mathematics [math]/Probability [math.PR], Floating body, Probability distribution, Mathematics - Probability
Abstract

We examine how the measure and the number of vertices of the convex hull of a random sample of $n$ points from an arbitrary probability measure in $\mathbf{R}^d$ relates to the wet part of that measure. This extends classical results for the uniform distribution from a convex set [B\'ar\'any and Larman 1988]. The lower bound of B\'ar\'any and Larman continues to hold in the general setting, but the upper bound must be relaxed by a factor of $\log n$. We show by an example that this is tight., Comment: 13 pages, 1 figure

Published
2020

2. Properties of combinations of hierarchical watersheds

Author

Deise Santana Maia, Laurent Najman, Jean Cousty, Benjamin Perret, Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Laboratoire des Sciences de l'Image, de l'Informatique et de la Télédétection (LSIIT), Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique Gaspard-Monge (ligm), and Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS)

Subjects
hierarchical watersheds, 02 engineering and technology, Function (mathematics), 01 natural sciences, Infimum and supremum, Artificial Intelligence, [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], 0103 physical sciences, Signal Processing, 0202 electrical engineering, electronic engineering, information engineering, 41A05, 41A10, 65D05, 65D17, 020201 artificial intelligence & image processing, Computer Vision and Pattern Recognition, 010306 general physics, Algorithm, Software, Mathematics
Abstract

International audience; In [12], the authors provide an evaluation of combinations of hierarchical watersheds, showing that some combinations outperform individual hierarchical watersheds. In this article, we aim to achieve a deeper understanding of those combinations. We study which of the four combinations evaluated in [12] always result in flattened (simplified) hierarchical watersheds. Then, we provide a sufficient condition for a combination to always output flattened hierarchical watersheds, and a new combining function that outputs flattened hierarchical watersheds. We conclude that, among the combinations assessed in [12], only a particular case of combinations with infimum always result in flattened hierarchical watersheds.

Published
2019

3. An alternating proximal approach for blind video deconvolution

Author

Feriel Abboud, Jean-Hugues Chenot, Emilie Chouzenoux, Jean-Christophe Pesquet, Louis Laborelli, Laboratoire d'Informatique Gaspard-Monge (ligm), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), WITBE, Organ Modeling through Extraction, Representation and Understanding of Medical Image Content (GALEN), Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Ecole Centrale Paris, Institut National de l'Audiovisuel (INA), Laboratoire d'Informatique Gaspard-Monge (LIGM), WITBE [Puteaux], Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Ecole Centrale Paris-Inria Saclay - Ile de France, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)

Subjects
Blind deconvolution, Computer science, Iterative method, nonconvex optimization, ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION, 02 engineering and technology, Shake, video processing, 0202 electrical engineering, electronic engineering, information engineering, Computer vision, Electrical and Electronic Engineering, Proximal algorithms, business.industry, Regular polygon, 020206 networking & telecommunications, Video processing, Inverse problem, regularization, Kernel (image processing), Signal Processing, 020201 artificial intelligence & image processing, Computer Vision and Pattern Recognition, Deconvolution, Artificial intelligence, business, [SPI.SIGNAL]Engineering Sciences [physics]/Signal and Image processing, Software
Abstract

International audience; Blurring occurs frequently in video sequences captured by consumer devices, as a result of various factors such as lens aberrations, defocus, relative camera-scene motion, and camera shake. When it comes to the contents of archive documents such as old films and television shows, the degradations are even more serious due to several physical phenomena happening during the sensing, transmission, recording, and storing processes. We propose in this paper a versatile formulation of blind video deconvolution problems that seeks to estimate both the sharp unknown video sequence and the underlying blur kernel from an observed video. This inverse problem is severely ill-posed, and an appropriate solution can be obtained by modeling it as a nonconvex minimization problem. We provide a novel iterative algorithm to solve it, grounded on the use of recent advances in convex and nonconvex optimization techniques, and having the ability of including numerous well-known regularization strategies.

Published
2019

4. On the asymptotic behaviour of the eigenvalue distribution of block correlation matrices of high-dimensional time series

Author

Loubaton, Philippe, Mestre, Xavier, Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Centre Tecnològic de Telecomunicacions de Catalunya = Telecommunications Technological Centre of Catalonia (CTTC), ANR-17-CE40-0003,HIDITSA,Analyse de Séries Temporelles de Grandes Dimensions(2017), ANR-10-LABX-0058,Bézout,Models and algorithms: from the discrete to the continuous(2010), Loubaton, Philippe, Analyse de Séries Temporelles de Grandes Dimensions - - HIDITSA2017 - ANR-17-CE40-0003 - AAPG2017 - VALID, Laboratoires d'excellence - Models and algorithms: from the discrete to the continuous - - Bézout2010 - ANR-10-LABX-0058 - LABX - VALID, Laboratoire d'Informatique Gaspard-Monge (ligm), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), and Centre Tecnològic de Telecomunicacions de Catalunya (CTTC)

Subjects
Statistics and Probability, [MATH.MATH-PR] Mathematics [math]/Probability [math.PR], Scalar (mathematics), Block (permutation group theory), [MATH] Mathematics [math], Large random matrices, 01 natural sciences, Correlation, Set (abstract data type), 010104 statistics & probability, Matrix (mathematics), FOS: Mathematics, Discrete Mathematics and Combinatorics, correlated time series, 0101 mathematics, [MATH]Mathematics [math], ComputingMilieux_MISCELLANEOUS, Mathematics, 60B20, Algebra and Number Theory, Series (mathematics), Covariance matrix, 010102 general mathematics, Mathematical analysis, Probability (math.PR), [MATH.MATH-PR]Mathematics [math]/Probability [math.PR], Eigenvalue distribution, Stieltjes transform, Statistics, Probability and Uncertainty, Mathematics - Probability, sample block correlation matrices
Abstract

We consider linear spectral statistics built from the block-normalized correlation matrix of a set of M mutually independent scalar time series. This matrix is composed of M2 blocks. Each block has size L×L and contains the sample cross-correlation measured at L consecutive time lags between each pair of time series. Let N denote the total number of consecutively observed windows that are used to estimate these correlation matrices. We analyze the asymptotic regime where M,L,N→+∞ while ML/N→c⋆, 0

Published
2021

5. A Shooting Formulation of Deep Learning

Author

Vialard, F. -X, Roland Kwitt, Wei, S., Niethammer, M., Laboratoire d'Informatique Gaspard-Monge (LIGM), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), University of Salzburg, Department of Mathematics and Statistics [Melbourne], University of Melbourne, Department of Computer Science [Chapel Hill], University of North Carolina [Chapel Hill] (UNC), University of North Carolina System (UNC)-University of North Carolina System (UNC), Laboratoire d'Informatique Gaspard-Monge (ligm), and Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM)

Subjects
FOS: Computer and information sciences, Computer Science - Machine Learning, Optimization and Control (math.OC), FOS: Mathematics, Computer Science - Neural and Evolutionary Computing, Neural and Evolutionary Computing (cs.NE), [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], [INFO.INFO-NE]Computer Science [cs]/Neural and Evolutionary Computing [cs.NE], Mathematics - Optimization and Control, Machine Learning (cs.LG)
Abstract

Continuous-depth neural networks can be viewed as deep limits of discrete neural networks whose dynamics resemble a discretization of an ordinary differential equation (ODE). Although important steps have been taken to realize the advantages of such continuous formulations, most current techniques are not truly continuous-depth as they assume \textit{identical} layers. Indeed, existing works throw into relief the myriad difficulties presented by an infinite-dimensional parameter space in learning a continuous-depth neural ODE. To this end, we introduce a shooting formulation which shifts the perspective from parameterizing a network layer-by-layer to parameterizing over optimal networks described only by a set of initial conditions. For scalability, we propose a novel particle-ensemble parametrization which fully specifies the optimal weight trajectory of the continuous-depth neural network. Our experiments show that our particle-ensemble shooting formulation can achieve competitive performance, especially on long-range forecasting tasks. Finally, though the current work is inspired by continuous-depth neural networks, the particle-ensemble shooting formulation also applies to discrete-time networks and may lead to a new fertile area of research in deep learning parametrization.

Published
2020

6. Power Spectral Clustering

Author

Sravan Danda, Aditya Challa, B. S. Daya Sagar, Laurent Najman, Systems Science and Informatics Unit, Indian Statistical Institute [Bangalore] (ISI), Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), ANR-15-CE40-0006,CoMeDiC,Métriques convergentes pour le calcul digital(2015), ANR-14-CE27-0001,GRAPHSIP,Traitement de signaux sur graphes(2014), Laboratoire d'Informatique Gaspard-Monge (ligm), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), and ANR-15-CE40-0006,CoMeDiC,Convergent Metrics for Digital Calculus(2015)

Subjects
Statistics and Probability, Fuzzy clustering, Computer science, Correlation clustering, Multi scale combinatorial grouping, 02 engineering and technology, computer.software_genre, MST based clustering, Clustering, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], CURE data clustering algorithm, Gamma convergence, 0202 electrical engineering, electronic engineering, information engineering, Cluster analysis, Multiscale combinatorial grouping !, Image segmentation, business.industry, Spectral Clustering, Applied Mathematics, Constrained clustering, [INFO.INFO-CV]Computer Science [cs]/Computer Vision and Pattern Recognition [cs.CV], Pattern recognition, Condensed Matter Physics, Determining the number of clusters in a data set, Data stream clustering, ComputingMethodologies_PATTERNRECOGNITION, Modeling and Simulation, Canopy clustering algorithm, 020201 artificial intelligence & image processing, Geometry and Topology, Computer Vision and Pattern Recognition, Data mining, Artificial intelligence, business, computer, Γ−convergence
Abstract

International audience; The problem of clustering has been an important problem since the early 20th century and several possible solutions were proposed. With the rise of computing machines clustering has become an important part of many data mining tasks, focussed on fast implementations. An important task related to clustering is image segmentation. In the set of solutions to the clustering problem, the method of spectral clustering has obtained wide interest due to its ability to detect non-convex clusters in the data. In this article, we propose a fast alternative to the spectral clustering, obtained by taking the Γ−limit. We explore the links between the new method and MST based clustering. We then show that the proposed method is as good as the spectral clustering with the help of experiments on several datasets. We also show that the new method is scalable to large data unlike the classical spectral clustering methods.

Published
2020

7. On The Dimension Group of Unimodular S-Adic Subshifts

Author

Berthe, Valerie, Bernales, P Cecchi, Durand, Fabien, Leroy, J, Perrin, Dominique, Petite, Samuel, Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Amiénois de Mathématique Fondamentale et Appliquée - UMR CNRS 7352 (LAMFA), Université de Picardie Jules Verne (UPJV)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Laboratoire Amiénois de Mathématique Fondamentale et Appliquée (LAMFA), Laboratoire d'Informatique Gaspard-Monge (ligm), and Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS)

Subjects
Mathematics::Dynamical Systems, [MATH.MATH-DS]Mathematics [math]/Dynamical Systems [math.DS], FOS: Mathematics, Dynamical Systems (math.DS), Mathematics - Dynamical Systems, Computer Science::Formal Languages and Automata Theory
Abstract

Dimension groups are complete invariants of strong orbit equivalence for minimal Cantor systems. This paper studies a natural family of minimal Cantor systems having a finitely generated dimension group, namely the primitive unimodular proper S-adic subshifts. They are generated by iterating sequences of substitutions. Proper substitutions are such that the images of letters start with a same letter, and similarly end with a same letter. This family includes various classes of subshifts such as Brun subshifts or dendric subshifts, that in turn include Arnoux-Rauzy subshifts and natural coding of interval exchange transformations. We compute their dimension group and investigate the relation between the triviality of the infinitesimal subgroup and rational independence of letter measures. We also introduce the notion of balanced functions and provide a topological characterization of bal-ancedness for primitive unimodular proper S-adic subshifts.

Published
2020

8. Optimisation des couts de virtualisation, puissance de traitement et la charge du réseau des centres de données définis par logiciel pour la 5G

Author

Salhab, Nazih, Rahim, Rana, Langar, Rami, Laboratoire d'Informatique Gaspard-Monge (LIGM), École des Ponts ParisTech (ENPC)-Centre National de la Recherche Scientifique (CNRS)-Université Gustave Eiffel, Université Libanaise, Laboratoire d'Informatique Gaspard-Monge (ligm), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), Phare, Laboratoire d'Informatique de Paris 6 (LIP6), and Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)

Subjects
[INFO.INFO-AR]Computer Science [cs]/Hardware Architecture [cs.AR], [INFO.INFO-MC]Computer Science [cs]/Mobile Computing, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2020

9. Extraction and annotation of 'location names'

Author

Markarit Vartampetian, Claude Martineau, Tita Kyriacopoulou, Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Laboratoire d'Informatique Gaspard-Monge (ligm), and Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS)

Subjects
Unitex, Recall, Process (engineering), business.industry, Computer science, Interoperability, location names, [SCCO.LING]Cognitive science/Linguistics, Variety (linguistics), computer.software_genre, Task (project management), locative complement, Information extraction, Annotation, annotation, Content analysis, [INFO]Computer Science [cs], Artificial intelligence, information extraction, business, computer, Natural language processing
Abstract

International audience; Introduced as part of the Message Understanding Conferences dedicated to information extraction, Named Entity extraction is a well-studied task in Natural Language Processing. The recognition and the categorisation of person names, location names, organisation names, etc., is regardedas a fundamental process for a wide variety of natural language processing applications dealing with content analysis and many research works are devoted to it, achieving very good results. One of our objectives is the identication and automatic (or semi-automatic) annotation of location names in order to apply the most appropriate information extraction methods. Then the main objective concerns the combination and interoperability between symbolic and statistical NLP (Natural Language Processing) methods (symbolic rules, machine learning, and data mining). Our work consisted of recognising named entities and in particular locations with Unitex, annotating them with Brat, and correcting them manually. The recall and accuracy rates are very encouraging but the question remains: What is a location name?

Published
2020

10. Cutting an alignment with Ockham's razor

Author

Jones, Mark, Gambette, Philippe, van Iersel, Leo, Janssen, Remie, Kelk, Steven, Pardi, Fabio, Scornavacca, Celine, Delft University of Technology (TU Delft), Laboratoire d'Informatique Gaspard-Monge (LIGM), École des Ponts ParisTech (ENPC)-Centre National de la Recherche Scientifique (CNRS)-Université Gustave Eiffel, Department of data science and Knowledge Engineering [Maastricht], Maastricht University [Maastricht], Méthodes et Algorithmes pour la Bioinformatique (MAB), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Institut des Sciences de l'Evolution de Montpellier (UMR ISEM), École pratique des hautes études (EPHE), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Université de Montpellier (UM)-Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Centre National de la Recherche Scientifique (CNRS)-Institut de recherche pour le développement [IRD] : UR226, Laboratoire d'Informatique Gaspard-Monge (ligm), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-École pratique des hautes études (EPHE)-Université de Montpellier (UM)-Institut de recherche pour le développement [IRD] : UR226-Centre National de la Recherche Scientifique (CNRS), Pardi, Fabio, Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-École Pratique des Hautes Études (EPHE), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Université de Montpellier (UM)-Institut de recherche pour le développement [IRD] : UR226-Centre National de la Recherche Scientifique (CNRS)

Subjects
FOS: Computer and information sciences, [SDV.BIBS] Life Sciences [q-bio]/Quantitative Methods [q-bio.QM], Populations and Evolution (q-bio.PE), fixed parameter tractability Mathematics Subject Classification 68Q25 92D15 92D20, [SDV.BID.SPT]Life Sciences [q-bio]/Biodiversity/Systematics, Phylogenetics and taxonomy, [SDV.BIBS]Life Sciences [q-bio]/Quantitative Methods [q-bio.QM], FOS: Biological sciences, Computer Science - Data Structures and Algorithms, [SDV.BID.SPT] Life Sciences [q-bio]/Biodiversity/Systematics, Phylogenetics and taxonomy, Recombination breakpoints, Fixed parameter tractability, Data Structures and Algorithms (cs.DS), Homoplasy, Block partitioning, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], Quantitative Biology - Populations and Evolution, Experiments, Parsimony, Exact algorithms, [INFO.INFO-BI] Computer Science [cs]/Bioinformatics [q-bio.QM]
Abstract

Preprints and early-stage research may not have been peer reviewed yet.; In this article, we investigate different parsimony-based approaches towards finding re-combination breakpoints in a multiple sequence alignment. This recombination detection task is crucial in order to avoid errors in evolutionary analyses caused by mixing together portions of sequences which had a different evolution history. Following an overview of the field of recombination detection, we formulate four computational problems for this task with different objective functions. The four problems aim to minimize (1) the total homoplasy of all blocks (2) the maximum homoplasy per block (3) the total homoplasy ratio of all blocks and (4) the maximum homoplasy ratio per block. We describe algorithms for each of these problems, which are fixed-parameter tractable (FPT) when the characters are binary. We have implemented and tested the algorithms on simulated data, showing that minimizing the total homoplasy gives, in most cases, the most accurate results. Our implementation and experimental data have been made publicly available. Finally, we also consider the problem of combining blocks into non-contiguous blocks consisting of at most p contiguous parts. Fixing the homoplasy h of each block to 0, we show that this problem is NP-hard when p ≥ 3, but polynomial-time solvable for p = 2. Furthermore, the problem is FPT with parameter h for binary characters when p = 2. A number of interesting problems remain open.

Published
2019

11. Machine Learning Based Resource Orchestration for 5G Network Slices

Author

Salhab, Nazih, Rahim, Rana, Langar, Rami, Boutaba, Raouf, Laboratoire d'Informatique Gaspard-Monge (ligm), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), Université Libanaise, Phare, Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS), Cheriton School of Computer Science [Waterloo] (CS), University of Waterloo [Waterloo], Laboratoire d'Informatique Gaspard-Monge (LIGM), and École des Ponts ParisTech (ENPC)-Centre National de la Recherche Scientifique (CNRS)-Université Gustave Eiffel

Subjects
[INFO.INFO-MC]Computer Science [cs]/Mobile Computing, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], [INFO.INFO-IA]Computer Science [cs]/Computer Aided Engineering, ComputingMilieux_MISCELLANEOUS, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Abstract

International audience

Published
2019

12. Rigidity and Substitutive Dendric Words

Author

Fabien Durand, Dominique Perrin, Francesco Dolce, Julien Leroy, Valérie Berthé, Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Laboratoire de combinatoire et d'informatique mathématique [Montréal] (LaCIM), Université du Québec à Montréal = University of Québec in Montréal (UQAM)-Centre de Recherches Mathématiques [Montréal] (CRM), Université de Montréal (UdeM)-Université de Montréal (UdeM), Laboratoire Amiénois de Mathématique Fondamentale et Appliquée - UMR CNRS 7352 (LAMFA), Université de Picardie Jules Verne (UPJV)-Centre National de la Recherche Scientifique (CNRS), Université de Liège, Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Université du Québec à Montréal (UQAM), Laboratoire d'Informatique Gaspard-Monge (ligm), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), Laboratoire Amiénois de Mathématique Fondamentale et Appliquée (LAMFA), Centre de Recherches Mathématiques [Montréal] (CRM), and Université de Montréal (UdeM)-Université de Montréal (UdeM)-Université du Québec à Montréal = University of Québec in Montréal (UQAM)

Subjects
Left and right, [MATH.MATH-DS]Mathematics [math]/Dynamical Systems [math.DS], 010102 general mathematics, Substitution (logic), Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing), Rigidity (psychology), 0102 computer and information sciences, Extension (predicate logic), S-adic word, 01 natural sciences, Combinatorics, 010201 computation theory & mathematics, Rigidity, Computer Science (miscellaneous), Bipartite graph, Topological eigenvalue, Dendric word, 0101 mathematics, Substitution, Computer Science::Formal Languages and Automata Theory, Mathematics
Abstract

International audience; Received (Day Month Year) Accepted (Day Month Year) Communicated by (xxxxxxxxxx) Dendric words are infinite words that are defined in terms of extension graphs. These are bipartite graphs that describe the left and right extensions of factors. Dendric words are such that all their extension graphs are trees. They are also called tree words. This class of words includes classical families of words such as Sturmian words, codings of interval exchanges, or else, Arnoux-Rauzy words. We investigate here the properties of substitutive dendric words and prove some rigidity properties, that is, algebraic properties on the set of substitutions that fix a dendric word. We also prove that aperiodic minimal dendric subshifts (generated by dendric words) cannot have rational topological eigenvalues, and thus, cannot be generated by constant length substitutions.

Published
2018

13. Laplacian matrices and spanning trees of tree graphs

Author

Guillaume Chapuy, Philippe Biane, Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Projet Émergences Ville de Paris 'Combinatoire à Paris', ANR-12-JS02-0001,CARTAPLUS,Combinatoire des cartes et applications(2012), Laboratoire d'Informatique Gaspard-Monge (ligm), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), and Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)

Subjects
Strongly connected component, Spanning tree, Probability (math.PR), 010102 general mathematics, 0102 computer and information sciences, General Medicine, Directed graph, 16. Peace & justice, 01 natural sciences, Combinatorics, Operator (computer programming), Factorization, 010201 computation theory & mathematics, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Bijection, Mathematics - Combinatorics, Graph (abstract data type), Combinatorics (math.CO), [MATH]Mathematics [math], 0101 mathematics, Laplace operator, Mathematics - Probability, Mathematics
Abstract

If $G$ is a strongly connected finite directed graph, the set $\mathcal{T}G$ of rooted directed spanning trees of $G$ is naturally equipped with a structure of directed graph: there is a directed edge from any spanning tree to any other obtained by adding an outgoing edge at its root vertex and deleting the outgoing edge of the endpoint. Any Schr\"odinger operator on $G$, for example the Laplacian, can be lifted canonically to $\mathcal{T}G$. We show that the determinant of such a lifted Schr\"odinger operator admits a remarkable factorization into a product of determinants of the restrictions of Schr\"odinger operators on subgraphs of $G$ and we give a combinatorial description of the multiplicities using an exploration procedure of the graph. A similar factorization can be obtained from earlier ideas of C. Athaniasadis, but this leads to a different expression of the multiplicities, as signed sums on which the nonnegativity is not appearent. We also provide a description of the block structure associated with this factorization. As a simple illustration we reprove a formula of Bernardi enumerating spanning forests of the hypercube, that is closely related to the graph of spanning trees of a bouquet. Several combinatorial questions are left open, such as giving a bijective interpretation of the results., Comment: Version 4: Minor corrections; we went back to the previous title following the suggestion of a referee

Published
2017

14. Counting branches in trees using games

Author

Olivier Serre, Arnaud Carayol, Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), and Laboratoire d'Informatique Gaspard-Monge (ligm)

Subjects
0102 computer and information sciences, 02 engineering and technology, Mathematical proof, 01 natural sciences, Theoretical Computer Science, Combinatorics, Set (abstract data type), Two-Player Games, Cardinality, Two-player game, Simple (abstract algebra), 0202 electrical engineering, electronic engineering, information engineering, Mathematics, Discrete mathematics, Finite-state machine, Binary tree, Cardinality Constraints, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], 16. Peace & justice, Computer Science Applications, Automaton, Automata on Infinite Trees, Computational Theory and Mathematics, 010201 computation theory & mathematics, 020201 artificial intelligence & image processing, Topologically Large Sets, Information Systems
Abstract

International audience; We study finite automata running over infinite binary trees. A run of such an automaton is usually said to be accepting if all its branches are accepting. In this article, we relax the notion of accepting run by allowing a certain quantity of rejecting branches. More precisely we study the following criteria for a run to be accepting: (i) it contains at most finitely (\resp countably) many rejecting branches;(ii) it contains infinitely (\resp uncountably) many accepting branches;(iii) the set of accepting branches is topologically “big”.In all situations we provide a simple acceptance game that later permits to prove that the languages accepted by automata with cardinality constraints are always omega-regular.In the case (ii) where one counts accepting branches it leads to new proofs (without appealing to logic) of a result of Beauquier and Niwinski.

Published
2017

15. Convexity Preserving Contraction of Digital Sets

Author

Yukiko Kenmochi, Pascal Romon, Lama Tarsissi, David Coeurjolly, Laboratoire de Mathématiques (LAMA), Université Savoie Mont Blanc (USMB [Université de Savoie] [Université de Chambéry])-Centre National de la Recherche Scientifique (CNRS), Origami (Origami), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA), Laboratoire d'Informatique Gaspard-Monge (ligm), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Analyse et de Mathématiques Appliquées (LAMA), Université Paris-Est Marne-la-Vallée (UPEM)-Fédération de Recherche Bézout-Université Paris-Est Créteil Val-de-Marne - Paris 12 (UPEC UP12)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Université Savoie Mont Blanc (USMB [Université de Savoie] [Université de Chambéry]), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Centre National de la Recherche Scientifique (CNRS)-Université Paris-Est Créteil Val-de-Marne - Paris 12 (UPEC UP12)-Fédération de Recherche Bézout-Université Paris-Est Marne-la-Vallée (UPEM), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), and Geometry Processing and Constrained Optimization (M2DisCo)

Subjects
050101 languages & linguistics, Computer science, business.industry, 05 social sciences, Vertex angle, Regular polygon, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Convexity, Lyndon words, Combinatorics on words, Digital image processing, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, 0501 psychology and cognitive sciences, Artificial intelligence, business, Algorithm
Abstract

International audience; Convexity is one of the useful geometric properties of digital sets in digital image processing. There are various applications which require deforming digital convex sets while preserving their convexity. In this article, we consider the contraction of such digital sets by removing digital points one by one. For this aim, we use some tools of combina-torics on words to detect a set of removable points and to define such convexity-preserving contraction of a digital set as an operation of rewriting its boundary word. In order to chose one of removable points for each contraction step, we present three geometrical strategies, which are related to vertex angle and area changes. We also show experimental results of applying the methods to repair some non-convex digital sets, which are obtained by rotations of convex digital sets.

Published
2019

16. Optimal bounds for computing α-gapped repeats

Author

Maxime Crochemore, Roman Kolpakov, Gregory Kucherov, Services généraux (SGLY), Institut national de recherche en sciences et technologies pour l'environnement et l'agriculture (IRSTEA), Lomonosov Moscow State University (MSU), Dorodnicyn Computing Centre of RAS (CCRAS), Russian Academy of Sciences [Moscow] (RAS), Laboratoire d'Informatique Gaspard-Monge (ligm), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique Gaspard-Monge (LIGM), Department of Computer Science [London], King‘s College London, Faculty of Mechanics and Mathematics, Moscow State University, and Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM)

Subjects
Computational Theory and Mathematics, 010201 computation theory & mathematics, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, ComputingMilieux_MISCELLANEOUS, Computer Science Applications, Information Systems, Theoretical Computer Science
Abstract

International audience; Following (Kolpakov et al., 2013; Gawrychowski and Manea, 2015), we continue the study of α-gapped repeats in strings, defined as factors uvu with |uv| ≤ α|u|. Our main result is the O(αn) bound on the number of maximal α-gapped repeats in a string of length n, previously proved to be O(α 2 n) in (Kolpakov et al., 2013). For a closely related notion of maximal δ-subrepetition (maximal factors of exponent between 1+δ and 2), our result implies the O(n/δ) bound on their number, which improves the bound of (Kolpakov et al., 2010) by a log n factor. We also prove an algorithmic time bound O(αn + S) (S size of the output) for computing all maximal α-gapped repeats. Our solution, inspired by (Gawrychowski and Manea, 2015), is different from the recently published proof by (Tanimura et al., 2015) of the same bound. Together with our bound on S, this implies an O(αn)-time algorithm for computing all maximal α-gapped repeats.

Published
2019

17. Characterization of graph-based hierarchical watersheds: theory and algorithms

Author

Deise Santana Maia, Jean Cousty, Benjamin Perret, Laurent Najman, Laboratoire d'Informatique Gaspard-Monge (ligm), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), Laboratoire des Sciences de l'Image, de l'Informatique et de la Télédétection (LSIIT), Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique Gaspard-Monge (LIGM), and École des Ponts ParisTech (ENPC)-Centre National de la Recherche Scientifique (CNRS)-Université Gustave Eiffel

Subjects
Statistics and Probability, Theoretical computer science, Watershed, Computer science, Efficient algorithm, Applied Mathematics, Graph based, ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION, 02 engineering and technology, Characterization (mathematics), Computer Science::Computational Geometry, Condensed Matter Physics, Physics::Geophysics, Physics::Popular Physics, Operator (computer programming), Modeling and Simulation, Computer Science::Computer Vision and Pattern Recognition, [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Segmentation, Geometry and Topology, Computer Vision and Pattern Recognition, Cluster analysis
Abstract

We propose a characterization of hierarchical watersheds built in the framework of edge-weighted graphs. Based on the notion of binary partition hierarchy by altitude ordering, we provide sufficient and necessary conditions for a hierarchy to be a hierarchical watershed. Those conditions are further used to design an efficient algorithm to recognize hierarchical watersheds. Furthermore, as an immediate application of our theoretical results, we present experiments with the combinations of hierarchical watersheds studied in [15]. Namely, we test if combinations of hierarchical watersheds are hierarchical watersheds themselves.

Published
2019

18. On Long Words Avoiding Zimin Patterns

Author

Stefan Göller, Arnaud Carayol, Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Fachbereich Mathematik und Informatik [Bremen], Universität Bremen, Laboratoire d'Informatique Gaspard-Monge ( LIGM ), Université Paris-Est Marne-la-Vallée ( UPEM ) -École des Ponts ParisTech ( ENPC ) -ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique ( CNRS ), Laboratoire Spécification et Vérification [Cachan] ( LSV ), École normale supérieure - Cachan ( ENS Cachan ) -Centre National de la Recherche Scientifique ( CNRS ), Laboratoire Spécification et Vérification [Cachan] (LSV), École normale supérieure - Cachan (ENS Cachan)-Centre National de la Recherche Scientifique (CNRS), and Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS)

Subjects
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Formal Languages and Automata Theory (cs.FL), Computer Science - Formal Languages and Automata Theory, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Upper and lower bounds, Theoretical Computer Science, Combinatorics, Morphism, Infix, [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], 0202 electrical engineering, electronic engineering, information engineering, 0101 mathematics, Abelian group, ComputingMilieux_MISCELLANEOUS, Mathematics, 000 Computer science, knowledge, general works, Image (category theory), 010102 general mathematics, 16. Peace & justice, Tower (mathematics), Computational Theory and Mathematics, [ INFO.INFO-FL ] Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], Computer Science, Theory of computation, 020201 artificial intelligence & image processing, Word (group theory), Computer Science::Formal Languages and Automata Theory, Computer Science - Discrete Mathematics
Abstract

International audience; A pattern is encountered in a word if some infix of the word is the image of the pattern under some non-erasing morphism. A pattern p is unavoidable if, over every finite alphabet, every sufficiently long word encounters p. A theorem by Zimin and independently by Bean, Ehrenfeucht and McNulty states that a pattern over n distinct variables is unavoidable if, and only if, p itself is encountered in the n-th Zimin pattern. Given an alphabet size k, we study the minimal length f (n, k) such that every word of length f (n, k) encounters the n-th Zimin pattern. It is known that f is upper-bounded by a tower of exponentials. Our main result states that f (n, k) is lower-bounded by a tower of n − 3 exponentials, even for k = 2. To the best of our knowledge, this improves upon a previously best-known doubly-exponential lower bound. As a further result, we prove a doubly-exponential upper bound for encountering Zimin patterns in the abelian sense. A pattern is a finite word over some set of pattern variables. A pattern matches a word if the word can be obtained by substituting each variable appearing in the pattern by a non-empty word. The pattern xx matches the word nana when x is replaced by the word na. A word encounters a pattern if the pattern matches some infix of the word. For example, the word banana encounters the pattern xx (as the word nana is one of its infixes). The pattern xyx is encountered in precisely those words that contain two non-consecutive occurrences of the same letter, as e.g., the word abca. A pattern is unavoidable if over every finite alphabet every sufficiently long word encounters the pattern. Equivalently, by Kőnig's Lemma, a pattern is unavoidable if over every finite alphabet all infinite words encounter the pattern. If it is not the case, the pattern is said to be avoidable. The pattern xyx is easily seen to be unavoidable since every sufficiently long word over a non-empty finite alphabet must contain two non-consecutive occurrences of the same letter. On the other hand, the pattern xx is avoidable as Thue [19] gave an infinite word over a ternary alphabet that does not encounter the pattern xx. A precise characterization of unavoidable patterns was found by Zimin [20] and independently by Bean, Ehrenfeucht and McNulty [6], see also [13] for a more recent proof. This * Supported by Labex Digicosme, Univ. Paris-Saclay, project VERICONISS.

Published
2019

19. Cayley graphs of basic algebraic structures

Author

Caucal, Didier, Laboratoire d'Informatique Gaspard-Monge (ligm), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique Gaspard-Monge (LIGM), Modèles et implémentation des calculs syntaxiques (MICAS), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), and caucal, didier

Subjects
monoid, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Mathematics::Category Theory, semigroup, [INFO]Computer Science [cs], group, [INFO] Computer Science [cs], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Cayley graph
Abstract

Discrete Mathematics & Theoretical Computer Science ; vol. 21 no. 1, ICGT 2018 ; 1365-8050, International audience, We present simple graph-theoretic characterizations for the Cayley graphs of monoids, right-cancellative monoids, left-cancellative monoids, and groups.

Published
2019

20. Replication dynamics of individual loci in single living cells reveal changes in the degree of replication stochasticity through S phase

Author

Bénédicte Duriez, Eslande Hercul, Jean-François Bercher, Sabarinadh Chilaka, Marie-Noëlle Prioleau, Institut Jacques Monod (IJM (UMR_7592)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), and Laboratoire d'Informatique Gaspard-Monge (ligm)

Subjects
DNA Replication Timing, Locus (genetics), Genome Integrity, Repair and Replication, Biology, Origin of replication, Genome, Cell Line, S Phase, 03 medical and health sciences, 0302 clinical medicine, Image Processing, Computer-Assisted, Genetics, Homologous chromosome, Animals, [INFO]Computer Science [cs], Allele, Alleles, ComputingMilieux_MISCELLANEOUS, Fluorescent Dyes, 030304 developmental biology, Stochastic Processes, 0303 health sciences, Replication timing, [SDV.GEN]Life Sciences [q-bio]/Genetics, Lamin Type B, Luminescent Proteins, Electroporation, Microscopy, Fluorescence, Evolutionary biology, Nuclear lamina, Chickens, 030217 neurology & neurosurgery
Abstract

Eukaryotic genomes are replicated under the control of a highly sophisticated program during the restricted time period corresponding to S phase. The most widely used replication timing assays, which are performed on populations of millions of cells, suggest that most of the genome is synchronously replicated on homologous chromosomes. We investigated the stochastic nature of this temporal program, by comparing the precise replication times of allelic loci within single vertebrate cells progressing through S phase at six loci replicated from very early to very late. We show that replication timing is strictly controlled for the three loci replicated in the first half of S phase. Out of the three loci replicated in the second part of S phase, two present a significantly more stochastic pattern. Surprisingly, we find that the locus replicated at the very end of S phase, presents stochasticity similar to those replicated in early S phase. We suggest that the richness of loci in efficient origins of replication, which decreases from early- to late-replicating regions, and the strength of interaction with the nuclear lamina may underlie the variation of timing control during S phase.

Published
2019

21. Asymptotic combinatorics of Artin–Tits monoids and of some other monoids

Author

Vincent Jugé, Jean Mairesse, Sébastien Gouëzel, Samy Abbes, Université Paris Diderot - Paris 7 (UPD7), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Laboratoire de Mathématiques Jean Leray (LMJL), Université de Nantes - Faculté des Sciences et des Techniques, Université de Nantes (UN)-Université de Nantes (UN)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique Gaspard-Monge (ligm), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), Université Paris-Est Marne-la-Vallée (UPEM), Algorithmes, Programmes et Résolution (APR), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Université de Nantes - UFR des Sciences et des Techniques (UN UFR ST), Université de Nantes (UN)-Université de Nantes (UN), Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), and Université de Nantes - UFR des Sciences et des Techniques (UN UFR ST)

Subjects
Uniform distribution (continuous), braid monoids, central limit theorem, Group Theory (math.GR), Möbius polynomial, 01 natural sciences, [MATH.MATH-GR]Mathematics [math]/Group Theory [math.GR], Möbius transform, Combinatorics, Mathematics::Group Theory, normal form, Law of large numbers, Mathematics::Category Theory, 0103 physical sciences, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Braid, Artin-Tits monoids of spherical type, 0101 mathematics, Axiom, Central limit theorem, Mathematics, uniform distribution, Algebra and Number Theory, boundary at infinity, 010102 general mathematics, law of large numbers, dual braid monoids, Dual (category theory), [MATH.MATH-PR]Mathematics [math]/Probability [math.PR], asymptotics, 010307 mathematical physics, Artin-Tits monoids, Mathematics - Group Theory, Artin-Tits monoids of type FC
Abstract

We introduce methods to study the combinatorics of the normal form of large random elements in Artin-Tits monoids. These methods also apply in an axiomatic framework that encompasses other monoids such as dual braid monoids., 53 pages, 2 figures, 38 bibliographic references

Published
2019

22. NFV Orchestration Platform for 5G over On-the-fly Provisioned Infrastructure

Author

Salhab, Nazih, Rahim, Rana, Langar, Rami, Laboratoire d'Informatique Gaspard-Monge (LIGM), École des Ponts ParisTech (ENPC)-Centre National de la Recherche Scientifique (CNRS)-Université Gustave Eiffel, Université Libanaise, Laboratoire d'Informatique Gaspard-Monge (ligm), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), Phare, Laboratoire d'Informatique de Paris 6 (LIP6), and Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)

Subjects
[INFO.INFO-MC]Computer Science [cs]/Mobile Computing, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], [INFO.INFO-SY]Computer Science [cs]/Systems and Control [cs.SY], [INFO]Computer Science [cs], [INFO.INFO-IA]Computer Science [cs]/Computer Aided Engineering, ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2019

23. Positive solutions for large random linear systems

Author

Jamal Najim, Pierre Bizeul, Ecole Normale Supérieure Paris-Saclay (ENS Paris Saclay), Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Laboratoire d'Informatique Gaspard-Monge (ligm), and Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS)

Subjects
Physics, Complement (group theory), Applied Mathematics, General Mathematics, Probability (math.PR), 010102 general mathematics, Dimension (graph theory), Linear system, Physics::Classical Physics, 01 natural sciences, [MATH.MATH-PR]Mathematics [math]/Probability [math.PR], Combinatorics, 010104 statistics & probability, Matrix (mathematics), Critical scaling, System of differential equations, Physics::Space Physics, FOS: Mathematics, [SDE.BE]Environmental Sciences/Biodiversity and Ecology, 0101 mathematics, Eigenvalues and eigenvectors, Mathematics - Probability
Abstract

Consider a large linear system where $A_n$ is a $n\times n$ matrix with independent real standard Gaussian entries, $\boldsymbol{1}_n$ is a $n\times 1$ vector of ones and with unknown the $n\times 1$ vector $\boldsymbol{x}_n$ satisfying $$ \boldsymbol{x}_n = \boldsymbol{1}_n +\frac 1{\alpha_n\sqrt{n}} A_n \boldsymbol{x}_n\, . $$ We investigate the (componentwise) positivity of the solution $\boldsymbol{x}_n$ depending on the scaling factor $\alpha_n$ as the dimension $n$ goes to $\infty$. We prove that there is a sharp phase transition at the threshold $\alpha^*_n =\sqrt{2\log n}$: below the threshold ($\alpha_n\ll \sqrt{2\log n}$), $\boldsymbol{x}_n$ has negative components with probability tending to 1 while above ($\alpha_n\gg \sqrt{2\log n}$), all the vector's components are eventually positive with probability tending to 1. At the critical scaling $\alpha^*_n$, we provide a heuristics to evaluate the probability that $\boldsymbol{x}_n$ is positive. Such linear systems arise as solutions at equilibrium of large Lotka-Volterra systems of differential equations, widely used to describe large biological communities with interactions such as foodwebs for instance. In the domaine of positivity of the solution $\boldsymbol{x}_n$, that is when $\alpha_n\gg \sqrt{2\log n}$, we establish that the Lotka-Volterra system of differential equations whose solution at equilibrium is precisely $\x_n$ is stable in the sense that its jacobian $$ {\mathcal J}(\boldsymbol{x}_n) = \mathrm{diag}(\boldsymbol{x}_n)\left(-I_n + \frac {A_n}{\alpha_n\sqrt{n}}\right) $$ has all its eigenvalues with negative real part with probability tending to one. Our results shed a new light and complement the understanding of feasibility and stability issues for large biological communities with interaction.

Published
2019

24. A Generic Interval Branch and Bound Algorithm for Parameter Estimation

Author

Martin de La Gorce, Bertrand Neveu, Pascal Monasse, Gilles Trombettoni, École des Ponts ParisTech (ENPC), Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), imagine [Marne-la-Vallée], Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM)-Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM)-Centre Scientifique et Technique du Bâtiment (CSTB), Agents, Apprentissage, Contraintes (COCONUT), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Centre Scientifique et Technique du Bâtiment (CSTB)-École des Ponts ParisTech (ENPC)-Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM)-Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-Université Paris-Est Marne-la-Vallée (UPEM), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS)-Centre Scientifique et Technique du Bâtiment (CSTB), and Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Mathematical optimization, 021103 operations research, Control and Optimization, Branch and bound, Estimation theory, Applied Mathematics, 0211 other engineering and technologies, 02 engineering and technology, Interval (mathematics), [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Management Science and Operations Research, RANSAC, Computer Science Applications, Randomized algorithm, [INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing, Essential matrix, Parametric model, Business, Management and Accounting (miscellaneous), Global optimization, Mathematics
Abstract

International audience; In engineering sciences, parameter estimation is a challenging problem consisting in computing the parameters of a parametric model that fit observed data. The system is defined by unknown parameters and sometimes internal constraints. The observed data provide constraints on the parameters. This problem is particularly difficult when some observation constraints correspond to outliers and/or the constraints are non convex. The ransac randomized algorithm can efficiently handle it, but is non deterministic and must be specialized for every problem. This paper presents the first generic interval branch and bound algorithm that produces a model maximizing the number of observation constraints satisfied within a given tolerance. This tool is inspired by the IbexOpt branch and bound algorithm for constrained global optimization (NLP) and is endowed with an improved version of a relaxed intersection operator applied to observations. Experiments have been carried out on two different computer vision problems. They highlight a significant speedup w.r.t. Jaulin et al.’s interval method in 2D and 3D shape recognition problems (having three parameters). We have also obtained promising results on a stereo vision problem where the essential matrix (five parameters) is estimated exactly at a good accuracy in hours for models having a thousand points, a typical size for such problems.

Published
2019

25. UAV-assisted supporting services connectivity in urban VANETs

Author

Abderrezak Rachedi, Pascal Lorenz, Noureddine Chaib, Abderrahmane Lakas, Omar Sami Oubbati, Université Amar Telidji - Laghouat (ALGERIA), United Arab Emirates University (UAEU), Laboratoire d'Informatique Gaspard-Monge (ligm), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), Université Amar Telidji - Laghouat, Modélisation, Intelligence, Processus et Système (MIPS), Ecole Nationale Supérieure d'Ingénieur Sud Alsace-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-IUT de Colmar-IUT de Mulhouse, Laboratoire d'Informatique Gaspard-Monge (LIGM), and École des Ponts ParisTech (ENPC)-Centre National de la Recherche Scientifique (CNRS)-Université Gustave Eiffel

Subjects
Routing protocol, Connectivity, Vehicular ad hoc network, Flooding process, Computer Networks and Communications, Computer science, Network packet, Wireless ad hoc network, Distributed computing, Aerospace Engineering, 020302 automobile design & engineering, 02 engineering and technology, UAVs, Flooding (computer networking), [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], Routing protocols, 0203 mechanical engineering, Automotive Engineering, VANETs, Electrical and Electronic Engineering, Intelligent transportation system, Simulation, ComputingMilieux_MISCELLANEOUS
Abstract

International audience; To keep the services and applications of Intelligent Transportation System (ITS) stable and active, Vehicular Ad hoc Networks (VANETs) are considered as an essential building block to maintain and manage its features. A wide deployment of VANETs is possible only after addressing numerous research challenges. One of the most complicated issues consists in designing a routing strategy, taking into consideration several serious constraints, and especially in a network such as VANET. The severity of these issues would be increased significantly when a VANET is deployed over an urban area, where we distinguish the high mobility of nodes and existing obstructions (e.g., buildings, bridges, tunnels, etc.). In this paper, an efficient routing solution based on a flooding technique is conceived to make the data delivery more reliable and to guarantee robust paths. Vehicles can cooperate in ad hoc fashion with existing Unmanned Aerial Vehicles (UAVs). This kind of collaboration provides reliable routing paths and ensures alternative solutions in the case of path failures. Furthermore, a prediction technique is used to expect the expiration time of each discovered path. To limit the overhead over the network, all control packets are characterized by their static size making the originality of this work. Based on the simulation outputs, we discuss the performances of the proposed approach as compared with other dedicated previous schemes in terms of several metrics. The obtained results demonstrate that the hybrid communication between vehicles and UAVs based on the proposed flooding technique is perfectly suited to improve the data delivery process.

Published
2019

26. Decentralized Reasoning on a Network of Aligned Ontologies with Link Keys

Author

Thinh Dong, Jérémy Lhez, Chan Le Duc, Myriam Lamolle, Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Laboratoire d'Informatique Avancée de Saint-Denis (LIASD), Université Paris 8 Vincennes-Saint-Denis (UP8), Laboratoire d'Informatique Médicale et Ingénierie des Connaissances en e-Santé (LIMICS), Institut National de la Santé et de la Recherche Médicale (INSERM)-Sorbonne Université (SU)-Université Sorbonne Paris Nord, Laboratoire d'Informatique Gaspard-Monge (ligm), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), The university of Danang, and Le Duc, Chan

Subjects
[INFO.INFO-AI] Computer Science [cs]/Artificial Intelligence [cs.AI], Theoretical computer science, Process (engineering), Computer science, 010401 analytical chemistry, [SCCO.COMP]Cognitive science/Computer science, 020207 software engineering, 02 engineering and technology, Ontology (information science), Semantics, 01 natural sciences, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], 0104 chemical sciences, [SCCO.COMP] Cognitive science/Computer science, 0202 electrical engineering, electronic engineering, information engineering, Link (knot theory), ComputingMilieux_MISCELLANEOUS
Abstract

International audience; Link keys are recently introduced to formalize data interlinking between data sources. They are considered as a new kind of correspondences included in ontology alignments. We propose a procedure for reasoning in a decentralized manner on a network of ontologies with alignments containing link keys. In this paper, the ontologies involved in such a network are expressed in the logic ALC while the alignments can contain concept, individual and link key correspondences equipped with a loose semantics. The decentralized aspect of our procedure is based on a process of knowledge propagation through the network via correspondences. This process allows to reduce polynomially global reasoning to local reasoning.

Published
2019

27. Stretching algorithm for global scheduling of real-time DAG tasks

Author

Manar Qamhieh, Laurent George, Serge Midonnet, Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Laboratoire d'Informatique Gaspard-Monge ( LIGM ), Université Paris-Est Marne-la-Vallée ( UPEM ) -École des Ponts ParisTech ( ENPC ) -ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique ( CNRS ), and Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS)

Subjects
Earliest deadline first scheduling, Control and Optimization, Computer Networks and Communications, Computer science, Multiprocessing, Monotonic function, 02 engineering and technology, 01 natural sciences, Multiprocessor scheduling, Scheduling (computing), 0103 physical sciences, 0202 electrical engineering, electronic engineering, information engineering, Golden ratio, [ INFO.INFO-ES ] Computer Science [cs]/Embedded Systems, Electrical and Electronic Engineering, Computer Science::Operating Systems, Real-time operating system, ComputingMilieux_MISCELLANEOUS, 010302 applied physics, Directed acyclic graph, 020202 computer hardware & architecture, Computer Science Applications, Control and Systems Engineering, Modeling and Simulation, [INFO.INFO-ES]Computer Science [cs]/Embedded Systems, Algorithm
Abstract

Parallelism is becoming more important nowadays due to the increasing use of multiprocessor systems. A Directed Acyclic Graph (DAG) is a general model of parallel tasks with inter-subtask parallelism. It consists of a collection of dependent subtasks under precedence constraints. In this paper, we study the problem of scheduling n periodic parallel real-time DAG tasks on m homogeneous multiprocessor systems. The dependencies between subtasks make scheduling process more challenging. We propose a stretching algorithm to be applied on each DAG task prior to scheduling process. Thus, DAGs are transformed into a set of independent sequential threads with intermediate offsets and deadlines. The threads obtained due to the transformation are of two types, (i) fully-stretched master threads with utilization equal to 1 and (ii) independent constrained-deadline threads. We propose a scheduling method over RTOS to ensure the execution of fully-stretched master threads on dedicated processors while the remaining processors $$\overline{m} \le m$$ , are used to schedule the independent constrained-deadline threads using any multiprocessor scheduling algorithm. In this work, we analyze the stretching algorithm while considering two global preemptive scheduling algorithms from different priority assignment families; the Global Earliest Deadline First (GEDF) from the fixed job priority family, and the Global Deadline Monotonic (GDM) from the fixed task priority family. We prove that GEDF scheduling of stretched threads has a resource augmentation bound equal to $$\frac{3+\sqrt{5}}{2}$$ for all task sets with $$n < \varphi \times \overline{m}$$ , where n is the number of tasks in the set and $$\varphi $$ is the golden ratio (the value of the golden ratio is $$\frac{1+\sqrt{5}}{2}$$ ). While GDM has a resource augmentation bound equal to $$2+\sqrt{3}$$ for all task sets with $$n < \frac{1+\sqrt{3}}{2} \times \overline{m}$$ .

Published
2019

28. Une analyse des exercices d’algorithmique et de programmation du brevet 2017

Author

Sylvie Alayrangues, Emmanuel Beffara, Sébastien Daniel, Christophe Declercq, Anne Héam, Jean-Vincent Loddo, Philippe Marquet, Jean-Christophe Masseron, Antoine Meyer, Malika More, Florence Nény, Vincent Pantaloni, Gaëtan Perrin, Cécile Prouteau, Georges Saliba, Sylviane Schwer, Fabien Tarissan, Chloé Ubera, Jean-Marc Vincent, Emmanuel Volte, Université de Poitiers, Synthèse et analyse d'images (XLIM-ASALI), XLIM (XLIM), Université de Limoges (UNILIM)-Centre National de la Recherche Scientifique (CNRS)-Université de Limoges (UNILIM)-Centre National de la Recherche Scientifique (CNRS), Institut de recherche sur l'enseignement des mathématiques d'Aix-Marseille (IREM), Aix Marseille Université (AMU), Institut de Mathématiques de Marseille (I2M), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), Institut de Recherche sur l’Enseignement des Mathématiques [Lorraine] (IREM), École supérieure du professorat et de l'éducation - Académie de Nantes (ESPE Nantes), Université de Nantes (UN), Laboratoire d'Informatique et de Mathématiques (LIM), Université de La Réunion (UR), IREM de Franche-Comté, IREM Paris-Nord, Université Paris 13 (UP13), Université de Lille, IREM de Paris, Université Paris Diderot - Paris 7 (UPD7), Laboratoire d'Informatique Gaspard-Monge (LIGM), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), Université de Clermont-Ferrand, IRES Orléans, Université d'Orléans (UO), IREM Aquitaine, Université de Bordeaux (UB), Laboratoire d'Informatique de Paris-Nord (LIPN), Université Paris 13 (UP13)-Institut Galilée-Université Sorbonne Paris Cité (USPC)-Centre National de la Recherche Scientifique (CNRS), Institut des Sciences sociales du Politique (ISP), École normale supérieure - Cachan (ENS Cachan)-Université Paris Nanterre (UPN)-Centre National de la Recherche Scientifique (CNRS), Institut de Recherche sur l’Enseignement des Mathématiques [Grenoble] (IREM), Performance analysis and optimization of LARge Infrastructures and Systems (POLARIS ), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Grenoble (LIG ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Analyse, Géométrie et Modélisation (AGM - UMR 8088), Centre National de la Recherche Scientifique (CNRS)-CY Cergy Paris Université (CY), Marquet, Philippe, Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Université Sorbonne Paris Cité (USPC)-Institut Galilée-Université Paris 13 (UP13)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Cachan (ENS Cachan)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Nanterre (UPN), CY Cergy Paris Université (CY)-Centre National de la Recherche Scientifique (CNRS), IREM de Clermont-Ferrand, Laboratoire d'Informatique Gaspard-Monge (ligm), Performance analysis and optimization of LARge Infrastructures and Systems (POLARIS), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Grenoble (LIG), Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP)-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP)-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA), Université de Cergy Pontoise (UCP), Université Paris-Seine-Université Paris-Seine-Centre National de la Recherche Scientifique (CNRS), and Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU)

Subjects
[INFO]Computer Science [cs], [SHS] Humanities and Social Sciences, [INFO] Computer Science [cs], [SHS]Humanities and Social Sciences
Abstract

National audience; Nous proposons une analyse critique de l’ensemble des exercices de l’épreuve de mathématiques 2017 du brevet ayant trait au thème « Algorithmique et programmation » du programme de cycle 4. Certains de ces exercices ne mettent en jeu que de manière très superficielle des compétences spécifiquement informatiques, mais portent plutôt sur des compétences mathématiques « traditionnelles », liées par exemple à l’algèbre ou la géométrie. Notre analyse met en regard ces différentes compétences, et propose des adaptations de certains énoncés afin d’en permettre une exploitation plus riche.

Published
2019

29. On the hardness of approximating Linearization of Scaffolds sharing Repeated Contigs

Author

Annie Chateau, Tom Davot, Rodolphe Giroudeau, Mathias Weller, Méthodes Algorithmes pour l'Ordonnancement et les Réseaux (MAORE), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Méthodes et Algorithmes pour la Bioinformatique (MAB), Institut de Biologie Computationnelle (IBC), Université de Montpellier (UM)-Institut National de la Recherche Agronomique (INRA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), Institut National de la Recherche Agronomique (INRA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique Gaspard-Monge (ligm), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), and Methods, Algorithms for Operations REsearch (MAORE)

Subjects
0301 basic medicine, Contig, Computer science, 0102 computer and information sciences, 01 natural sciences, Combinatorics, 03 medical and health sciences, 030104 developmental biology, Planar, 010201 computation theory & mathematics, Linearization, Bipartite graph, Graph (abstract data type), [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], Genome scaffolding, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract

International audience; Solutions to genome scaffolding problems can be represented as paths and cycles in a "solution graph". However, when working with repetitions, such solution graph may contain branchings and they may not be uniquely convertible into sequences. Having introduced, in a previous work, various ways of extracting the unique parts of such solutions, we extend previously known NP-hardness results to the case that the solution graph is planar, bipartite, and subcubic, and show the APX-completeness in this case. We also provide some practical tests.

Published
2018

30. New Results About the Linearization of Scaffolds Sharing Repeated Contigs

Author

Rodolphe Giroudeau, Mathias Weller, Annie Chateau, Tom Davot, Dorine Tabary, Méthodes Algorithmes pour l'Ordonnancement et les Réseaux (MAORE), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Institut de Biologie Computationnelle (IBC), Université de Montpellier (UM)-Institut National de la Recherche Agronomique (INRA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Méthodes et Algorithmes pour la Bioinformatique (MAB), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), Institut National de la Recherche Agronomique (INRA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique Gaspard-Monge (ligm), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), and Methods, Algorithms for Operations REsearch (MAORE)

Subjects
0301 basic medicine, Contig, Computer science, 0102 computer and information sciences, 01 natural sciences, Graph, Combinatorics, 03 medical and health sciences, 030104 developmental biology, Planar, 010201 computation theory & mathematics, Linearization, Bipartite graph, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], Genome scaffolding
Abstract

International audience; Solutions to genome scaffolding problems can be represented as paths and cycles in a "solution graph". However, when working with repetitions, such solution graphs may contain branchings and, thus, they may not be uniquely convertible into sequences. Having introduced various ways of extracting the unique parts of such solutions, we extend previously known NP-hardness results to the case that the solution graph is planar, bipartite, and subcubic, and show that there is no PTAS in this case.

Published
2018

31. On the Worst-Case Complexity of TimSort

Author

Auger , Nicolas, Jugé , Vincent, Nicaud , Cyril, Pivoteau , Carine, Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Laboratoire d'Informatique Gaspard-Monge ( LIGM ), Université Paris-Est Marne-la-Vallée ( UPEM ) -École des Ponts ParisTech ( ENPC ) -ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique ( CNRS ), and Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS)

Subjects
FOS: Computer and information sciences, Sorting algorithms, 000 Computer science, knowledge, general works, [ INFO ] Computer Science [cs], ACM: F.: Theory of Computation/F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY/F.2.2: Nonnumerical Algorithms and Problems/F.2.2.6: Sorting and searching, ACM: F.: Theory of Computation/F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Merge sorting algorithms, ACM : F.: Theory of Computation/F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY, ACM : F.: Theory of Computation/F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY/F.2.2: Nonnumerical Algorithms and Problems/F.2.2.6: Sorting and searching, Computer Science, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), [INFO]Computer Science [cs], TimSort, Analysis of al-gorithms, [ INFO.INFO-DS ] Computer Science [cs]/Data Structures and Algorithms [cs.DS]
Abstract

TimSort is an intriguing sorting algorithm designed in 2002 for Python, whose worst-case complexity was announced, but not proved until our recent preprint. In fact, there are two slightly different versions of TimSort that are currently implemented in Python and in Java respectively. We propose a pedagogical and insightful proof that the Python version runs in $\mathcal{O}(n\log n)$. The approach we use in the analysis also applies to the Java version, although not without very involved technical details. As a byproduct of our study, we uncover a bug in the Java implementation that can cause the sorting method to fail during the execution. We also give a proof that Python's TimSort running time is in $\mathcal{O}(n + n\log \rho)$, where $\rho$ is the number of runs (i.e. maximal monotonic sequences), which is quite a natural parameter here and part of the explanation for the good behavior of TimSort on partially sorted inputs.

Published
2018

32. Pure Strategies in Imperfect Information Stochastic Games

Author

Olivier Serre, Christof Löding, Arnaud Carayol, Laboratoire d'Informatique Gaspard-Monge (ligm), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), Rheinisch-Westfälische Technische Hochschule Aachen (RWTH), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique Gaspard-Monge (LIGM), École des Ponts ParisTech (ENPC)-Centre National de la Recherche Scientifique (CNRS)-Université Gustave Eiffel (UNIV GUSTAVE EIFFEL), and École des Ponts ParisTech (ENPC)-Centre National de la Recherche Scientifique (CNRS)-Université Gustave Eiffel

Subjects
FOS: Computer and information sciences, Algebra and Number Theory, Theoretical computer science, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], Computer science, Formal Languages and Automata Theory (cs.FL), Perfect information, ComputingMilieux_PERSONALCOMPUTING, Computer Science - Formal Languages and Automata Theory, 0102 computer and information sciences, 01 natural sciences, Theoretical Computer Science, Undecidable problem, Decidability, Two-player imperfect information stochastic games, Computational Theory and Mathematics, 010201 computation theory & mathematics, Reachability, Computer Science - Computer Science and Game Theory, pure strategies, decidability/undecidability, ComputingMilieux_MISCELLANEOUS, Information Systems, Computer Science and Game Theory (cs.GT)
Abstract

International audience; We consider imperfect information stochastic games where we require the players to use pure (i.e. non randomised) strategies. We consider reachability, safety, Büchi and co-Büchi objectives, and investigate the existence of almost-sure/positively winning strategies for the first player when the second player is perfectly informed or more informed than the first player. We obtain decidability results for positive reachability and almost-sure Büchi with optimal algorithms to decide existence of a pure winning strategy and to compute one if it exists. We complete the picture by showing that positive safety is undecidable when restricting to pure strategies even if the second player is perfectly informed.

Published
2018

33. Dynamic Network Slicing for 5G IoT and eMBB services: A New Design with Prototype and Implementation Results

Author

Rami Langar, Nadjib Aitsaadi, Ilhem Fajjari, Salvatore Costanzo, Phare, LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Orange Labs [Issy les Moulineaux], France Télécom, Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Laboratoire d'Informatique de Paris 6 ( LIP6 ), Université Pierre et Marie Curie - Paris 6 ( UPMC ) -Centre National de la Recherche Scientifique ( CNRS ) -Université Pierre et Marie Curie - Paris 6 ( UPMC ) -Centre National de la Recherche Scientifique ( CNRS ), Laboratoire d'Informatique Gaspard-Monge ( LIGM ), Université Paris-Est Marne-la-Vallée ( UPEM ) -École des Ponts ParisTech ( ENPC ) -ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique ( CNRS ), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), and Rami, Langar

Subjects
Mobile radio, Dynamic network analysis, [ INFO ] Computer Science [cs], Computer science, [ INFO.INFO-NI ] Computer Science [cs]/Networking and Internet Architecture [cs.NI], Transport network, Cloud computing, 02 engineering and technology, [INFO] Computer Science [cs], [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], 0202 electrical engineering, electronic engineering, information engineering, Wireless, Resource management, [INFO]Computer Science [cs], ComputingMilieux_MISCELLANEOUS, Radio access network, Access network, [INFO.INFO-NI] Computer Science [cs]/Networking and Internet Architecture [cs.NI], business.industry, Quality of service, Mobile broadband, 020206 networking & telecommunications, Cellular network, 020201 artificial intelligence & image processing, business, Computer network
Abstract

Recent progress in sensor and communications have opened the road for the ever-growing development of Internet of Things (IoT) services, where a massive number of devices require access to the transport network, using widely deployed fixed or wireless access technologies and/or mobile Radio Access Network (RAN). Supporting IoT in the RAN is challenging, as IoT services may generate a multitude of short and bursty sessions, thus impacting the performances of mobile users sharing the same RAN. To this end, network slicing is envisioned as a promising design approach to enable optimal support for heterogeneous service segments sharing the same RAN, i.e., the key requirement of the upcoming fifth generation (5G) mobile network. In this paper, we propose a network slicing solution for enabling efficient coexistence of enhanced mobile broadband (eMBB) and IoT services, sharing the same RAN. Our solution aims at efficiently sharing the bandwidth resources among different slice segments, while considering their requirements. We validate the proposed solution in a 5G prototype based on the Cloud Radio Access Network (C-RAN) architecture, which makes use of the Open Air Interface (OAI) platform and the FlexRAN SDN controller. The main goal of our work is to validate the feasibility of the prototype of supporting the creation and configuration of network slices on-demand, taking into account diverse requirements that are elaborated by a northbound SDN-based slicing application. By means of emulations, we show that the prototype is capable to dynamically manage the slicing process in real-time, providing isolation among eMBB and IoT services.

Published
2018

34. Cypher

Author

Tobias Lindaaker, Andrés Taylor, Paolo Guagliardo, Petra Selmer, Victor Marsault, Leonid Libkin, Alastair Green, Nadime Francis, Stefan Plantikow, Mats Rydberg, Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Neo4j, Laboratory for the Foundations of Computer Science [Edinburgh] (LFCS), University of Edinburgh, Laboratoire d'Informatique Gaspard-Monge ( LIGM ), Université Paris-Est Marne-la-Vallée ( UPEM ) -École des Ponts ParisTech ( ENPC ) -ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique ( CNRS ), Laboratory for the Foundations of Computer Science [Edinburgh] ( LFCS ), and Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS)

Subjects
[ INFO ] Computer Science [cs], [INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB], Graph database, Computer science, Programming language, 02 engineering and technology, Query language, computer.software_genre, Graph, [ INFO.INFO-DB ] Computer Science [cs]/Databases [cs.DB], Named graph, 020204 information systems, Formal specification, 0202 electrical engineering, electronic engineering, information engineering, [INFO]Computer Science [cs], 020201 artificial intelligence & image processing, computer
Abstract

International audience; The Cypher property graph query language is an evolving language, originally designed and implemented as part of the Neo4j graph database, and it is currently used by several commercial database products and researchers. We describe Cypher 9, which is the first version of the language governed by the openCypher Implementers Group. We first introduce the language by example, and describe its uses in industry. We then provide a formal semantic definition of the core read-query features of Cypher, including its variant of the property graph data model, and its " ASCII Art " graph pattern matching mechanism for expressing subgraphs of interest to an application. We compare the features of Cypher to other property graph query languages, and describe extensions, at an advanced stage of development, which will form part of Cypher 10, turning the language into a compositional language which supports graph projections and multiple named graphs.

Published
2018

35. DECO-MWE: Building a Linguistic Resource of Korean Multiword Expressions for Feature-Based Sentiment Analysis

Author

Jaeho Han, Changhoe Hwang, Seongyong Choi, Gwanghoon Yoo, Eric Laporte, Jeesun Nam, Digital Language & Knowledge Contents Research Association ( DICORA ), Hankuk University of Foreign Studies ( HUFS ), Hankuk University of Foreign Studies, Laboratoire d'Informatique Gaspard-Monge ( LIGM ), Université Paris-Est Marne-la-Vallée ( UPEM ) -École des Ponts ParisTech ( ENPC ) -ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique ( CNRS ), Kiyoaki Shirai, Digital Language & Knowledge Contents Research Association (DICORA), Hankuk University of Foreign Studies (HUFS), Laboratoire d'Informatique Gaspard-Monge (LIGM), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), and Laporte, Eric

Subjects
[INFO.INFO-TT]Computer Science [cs]/Document and Text Processing, Sentiment analysis, [ INFO.INFO-TT ] Computer Science [cs]/Document and Text Processing, Feature-Based Sentiment Analysis, [INFO.INFO-CL] Computer Science [cs]/Computation and Language [cs.CL], Multiword Expression, DECO-MWE, [INFO.INFO-TT] Computer Science [cs]/Document and Text Processing, [ INFO.INFO-CL ] Computer Science [cs]/Computation and Language [cs.CL], [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL], Local Grammar Graph
Abstract

International audience; This paper aims to construct a linguistic resource of Korean Multiword Expressions for Feature-Based Sentiment Analysis (FBSA): DECO-MWE. Dealing with multiword expressions (MWEs) has been a critical issue in FBSA since many constructs reveal lexical idiosyncrasy. To construct linguistic resources of sentiment MWEs efficiently, we utilize the Local Grammar Graph (LGG) methodology: DECO-MWE is formalized as a Finite-State Transducer that represents lexical-syntactic restrictions on MWEs. In this study, we built a corpus of cosmetics review texts, which show particularly frequent occurrences of MWEs. Based on an empirical examination of the corpus, four types of MWEs have been distinguished. The DECO-MWE thus covers the following four categories: Standard Polarity MWEs (SMWEs), Domain-Dependent Polarity MWEs (DMWEs), Compound Named Entity MWEs (EMWEs) and Compound Feature MWEs (FMWEs). The retrieval performance of the DECO-MWE shows 0.806 f-measure in the test corpus. This study brings a twofold outcome: first, a sizeable general-purpose polarity MWE lexicon, which may be broadly used in FBSA; second, a finite-state methodology adopted in this study to treat domain-dependent MWEs such as idiosyncratic polarity expressions, named entity expressions or feature expressions, and which may be reused in describing linguistic properties of other corpus domains.

Published
2018

36. Towards Variational Generation of Small Graphs

Author

Simonovsky, Martin, Komodakis, Nikos, École des Ponts ParisTech (ENPC), Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), imagine [Marne-la-Vallée], Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM)-Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Martin, Simonovsky, École des Ponts ParisTech ( ENPC ), Laboratoire d'Informatique Gaspard-Monge ( LIGM ), and Université Paris-Est Marne-la-Vallée ( UPEM ) -École des Ponts ParisTech ( ENPC ) -ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique ( CNRS )

Subjects
[INFO.INFO-CV] Computer Science [cs]/Computer Vision and Pattern Recognition [cs.CV], [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], [INFO.INFO-NE] Computer Science [cs]/Neural and Evolutionary Computing [cs.NE], [INFO.INFO-CV]Computer Science [cs]/Computer Vision and Pattern Recognition [cs.CV], [INFO.INFO-LG] Computer Science [cs]/Machine Learning [cs.LG], [ INFO.INFO-NE ] Computer Science [cs]/Neural and Evolutionary Computing [cs.NE], [INFO.INFO-NE]Computer Science [cs]/Neural and Evolutionary Computing [cs.NE], [ INFO.INFO-CV ] Computer Science [cs]/Computer Vision and Pattern Recognition [cs.CV], [ INFO.INFO-LG ] Computer Science [cs]/Machine Learning [cs.LG]
Abstract

International audience; In this paper we propose a generative model for graphs formulated as a variational autoencoder. We sidestep hurdles associated with linearization of graphs by having the decoder output a probabilistic fully-connected graph of a predefined maximum size directly at once. We evaluate on the challenging task of molecule generation.

Published
2018

37. A Nonconvex Variational Approach for Robust Graphical Lasso

Author

Alessandro Benfenati, Emilie Chouzenoux, Jean-Christophe Pesquet, Laboratoire d'Informatique Gaspard-Monge ( LIGM ), Université Paris-Est Marne-la-Vallée ( UPEM ) -École des Ponts ParisTech ( ENPC ) -ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique ( CNRS ), ESIEE Paris, Organ Modeling through Extraction, Representation and Understanding of Medical Image Content ( GALEN-POST ), Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria ), ANR-14-CE27-0001,GRAPHSIP,Traitement de signaux sur graphes ( 2014 ), Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Organ Modeling through Extraction, Representation and Understanding of Medical Image Content (GALEN-POST), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), ANR-14-CE27-0001,GRAPHSIP,Traitement de signaux sur graphes(2014), Chouzenoux, Emilie, Appel à projets générique - Traitement de signaux sur graphes - - GRAPHSIP2014 - ANR-14-CE27-0001 - Appel à projets générique - VALID, and Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS)

Subjects
Mathematical optimization, Graphical LASSO, Computer science, Model selection, Convex decomposition, Non–convex Optimization, 020206 networking & telecommunications, 02 engineering and technology, [ SPI.SIGNAL ] Engineering Sciences [physics]/Signal and Image processing, 01 natural sciences, Regularization (mathematics), Proximal Methods, Matrix similarity, 010104 statistics & probability, Estimation of covariance matrices, Majorization–minimization, 0202 electrical engineering, electronic engineering, information engineering, Symmetric matrix, Graph (abstract data type), 0101 mathematics, [SPI.SIGNAL]Engineering Sciences [physics]/Signal and Image processing, Covariance Estimation, Eigenvalues and eigenvectors, [SPI.SIGNAL] Engineering Sciences [physics]/Signal and Image processing
Abstract

International audience; In recent years, there has been a growing interest in problems in graph estimation and model selection, which all share very similar matrix variational formulations, the most popular one being probably GLASSO. Unfortunately, the standard GLASSO formulation does not take into account noise corrupting the data: this shortcoming leads us to propose a novel cost function, where the regularization function is decoupled in two terms, one acting only on the eigenvalues of the matrix and the other on the matrix elements. Incorporating noise information into the model has the side–effect to make the cost function non–convex. To overcome this difficulty, we adopt a majorization–minimization approach, where at each iteration a convex approximation of the original cost function is minimized via the Douglas–Rachford procedure. The achieved results are very promising w.r.t. classical approaches.

Published
2018

38. PIPA: A New Proximal Interior Point Algorithm for Large Scale Convex Optimization

Author

Corbineau, Marie-Caroline, Chouzenoux, Emilie, Pesquet, Jean-Christophe, Organ Modeling through Extraction, Representation and Understanding of Medical Image Content (GALEN-POST), Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Organ Modeling through Extraction, Representation and Understanding of Medical Image Content ( GALEN-POST ), Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria ), Laboratoire d'Informatique Gaspard-Monge ( LIGM ), Université Paris-Est Marne-la-Vallée ( UPEM ) -École des Ponts ParisTech ( ENPC ) -ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique ( CNRS ), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), and Chouzenoux, Emilie

Subjects
Hyperspectral unimixing, [ SPI.SIGNAL ] Engineering Sciences [physics]/Signal and Image processing, Large-scale problems, Interior point methods, Proximal algorithms, [SPI.SIGNAL]Engineering Sciences [physics]/Signal and Image processing, [SPI.SIGNAL] Engineering Sciences [physics]/Signal and Image processing, Convex optimization
Abstract

International audience; Interior point methods have been known for decades to be useful for the resolution of small to medium size constrained optimization problems. These approaches have the benefit of ensuring feasibility of the iterates through a logarithmic barrier. We propose to incorporate a proximal forward-backward step in the resolution of the barrier subproblem to account for non-necessarily differentiable terms arising in the objective function. The combination of this scheme with a novel line-search strategy gives rise to the so-called Proximal Interior Point Algorithm (PIPA) suitable for the minimization of the sum of a smooth convex function and a non-smooth convex one under general convex constraints. The convergence of PIPA is secured under mild assumptions. As demonstrated by numerical experiments carried out on a large-scale hyperspectral image unmixing application, the proposed method outperforms the state-of-the-art.

Published
2018

39. Uniform generation of infinite concurrent runs: the case of trace monoids

Author

Abbes, Samy, Jugé, Vincent, Preuves, Programmes et Systèmes (PPS), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7), Laboratoire d'Informatique Gaspard-Monge (ligm), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), and Jugé, Vincent

Subjects
[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO)
Abstract

We introduce an algorithm for the uniform generation of infinite runs in concurrent systems under a partial order probabilistic semantics. We work with trace monoids as concurrency models. The algorithm outputs on-the-fly approximations of a theoretical infinite run, the latter being distributed according to the exact uniform probability measure. The average size of the approximation grows linearly with the time of execution of the algorithm. The execution of the algorithm only involves distributed computations, provided that some - costly - precomputations have been done., 19 pages, 2 figures

Published
2018

40. Scouter: A Stream Processing Web Analyzer to Contextualize Singularities

Author

Belabbess, Badre, Bairat, Musab, Lhez, Jérémy, Khattabi, Zakaria, Zheng, Yufan, Curé, Olivier, Laboratoire d'Informatique Gaspard-Monge ( LIGM ), Université Paris-Est Marne-la-Vallée ( UPEM ) -École des Ponts ParisTech ( ENPC ) -ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique ( CNRS ), Atos [Bezons], ATOS Origin, Curé, Olivier, Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), and Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS)

Subjects
[INFO.INFO-AI] Computer Science [cs]/Artificial Intelligence [cs.AI], [INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB], [ INFO.INFO-DB ] Computer Science [cs]/Databases [cs.DB], [INFO.INFO-DB] Computer Science [cs]/Databases [cs.DB], [ INFO.INFO-AI ] Computer Science [cs]/Artificial Intelligence [cs.AI], ComputingMilieux_MISCELLANEOUS, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Abstract

International audience

Published
2018

41. Unbounded Largest Eigenvalue of Large Sample Covariance Matrices: Asymptotics, Fluctuations and Applications

Author

Jamal Najim, Florence Merlevède, Peng Tian, Laboratoire d'Analyse et de Mathématiques Appliquées (LAMA), Centre National de la Recherche Scientifique (CNRS)-Université Paris-Est Créteil Val-de-Marne - Paris 12 (UPEC UP12)-Fédération de Recherche Bézout-Université Paris-Est Marne-la-Vallée (UPEM), Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Université Paris-Est Marne-la-Vallée (UPEM)-Fédération de Recherche Bézout-Université Paris-Est Créteil Val-de-Marne - Paris 12 (UPEC UP12)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique Gaspard-Monge (ligm), and Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS)

Subjects
Numerical Analysis, Algebra and Number Theory, Multivariate random variable, 010102 general mathematics, Nuclear Theory, Probability (math.PR), 010103 numerical & computational mathematics, Positive-definite matrix, Lambda, 01 natural sciences, Hermitian matrix, Combinatorics, [MATH.MATH-PR]Mathematics [math]/Probability [math.PR], Autocovariance, Matrix (mathematics), Mathematics::Group Theory, FOS: Mathematics, Discrete Mathematics and Combinatorics, Spectral gap, Geometry and Topology, 0101 mathematics, Nuclear Experiment, Mathematics - Probability, Eigenvalues and eigenvectors, Mathematics
Abstract

International audience; Given a large sample covariance matrix$S_N=\frac 1n\Gamma_N^{1/2}Z_N Z_N^*\Gamma_N^{1/2}\, ,$where $Z_N$ is a $N\times n$ matrix with i.i.d. centered entries, and $\Gamma_N$ is a $N\times N$ deterministic Hermitian positive semidefinite matrix, we study the location and fluctuations of $\lambda_{\max}(S_N)$, the largest eigenvalue of $S_N$ as $N,n\to\infty$ and $Nn^{-1} \to r\in(0,\infty)$ in the case where the empirical distribution $\mu^{\Gamma_N}$ of eigenvalues of $\Gamma_N$ is tight (in $N$) and $\lambda_{\max}(\Gamma_N)$ goes to $+\infty$. These conditions are in particular met when $\mu^{\Gamma_N}$ weakly converges to a probability measure with unbounded support on $\mathbb{R}^+$. We prove that asymptotically $\lambda_{\max}(S_N)\sim \lambda_{\max}(\Gamma_N)$. Moreover when the $\Gamma_N$'s are block-diagonal, and the following {\em spectral gap condition} is assumed:$$\limsup_{N\to\infty} \frac{\lambda_2(\Gamma_N)}{\lambda_{\max}(\Gamma_N)}

Published
2018
Full Text
View/download PDF

42. On Cayley graphs of algebraic structures

Author

Caucal, Didier, Laboratoire d'Informatique Gaspard-Monge ( LIGM ), Université Paris-Est Marne-la-Vallée ( UPEM ) -École des Ponts ParisTech ( ENPC ) -ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique ( CNRS ), Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), and Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS)

Subjects
monoid, FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Mathematics::General Mathematics, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], [ INFO.INFO-DM ] Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], quasigroup, Cayley graph, Mathematics::Group Theory, FOS: Mathematics, Mathematics - Combinatorics, group, [ INFO.INFO-LO ] Computer Science [cs]/Logic in Computer Science [cs.LO], Combinatorics (math.CO), F.1.1, Computer Science - Discrete Mathematics, Computer Science::Cryptography and Security
Abstract

presented at ICGT 2018; International audience; We present simple graph-theoretic characterizations of Cayley graphs for left-cancellative monoids, groups, left-quasigroups and quasigroups. We show that these characterizations are effective for the end-regular graphs of finite degree.

Published
2018
Full Text
View/download PDF

43. Noncrossing partitions, Bruhat order and the cluster complex

Author

Philippe Biane, Matthieu Josuat-Vergès, Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique Gaspard-Monge (ligm), and Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS)

Subjects
cluster complex, Bruhat order, Noncrossing partitions, 01 natural sciences, [MATH.MATH-GR]Mathematics [math]/Group Theory [math.GR], Combinatorics, 0103 physical sciences, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Cluster (physics), FOS: Mathematics, Order (group theory), Mathematics - Combinatorics, 0101 mathematics, Mathematics::Representation Theory, ComputingMilieux_MISCELLANEOUS, Mathematics, Algebra and Number Theory, Mathematics::Combinatorics, Noncrossing partition, 010102 general mathematics, Coxeter group, 16. Peace & justice, 010307 mathematical physics, Geometry and Topology, Combinatorics (math.CO), Bijection, injection and surjection
Abstract

International audience; We introduce two order relations on finite Coxeter groups which refine the absolute and the Bruhat order, and establish some of their main properties. In particular we study the restriction of these orders to noncrossing partitions and show that the intervals for these orders can be enumerated in terms of the cluster complex. The properties of our orders permit to revisit several results in Coxeter combinatorics, such as the Chapoton triangles and how they are related, the enumera-tion of reflections with full support, the bijections between clusters and noncrossing partitions.

Published
2018
Full Text
View/download PDF

44. Rayleigh-Schrödinger series and Birkhoff decomposition

Author

David Sauzin, Jean-Christophe Novelli, Thierry Paul, Jean-Yves Thibon, Laboratoire d'Informatique Gaspard-Monge (LIGM), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), Centre de Mathématiques Laurent Schwartz (CMLS), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), Institut de Mécanique Céleste et de Calcul des Ephémérides (IMCCE), Institut national des sciences de l'Univers (INSU - CNRS)-Observatoire de Paris, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Université de Lille-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), Laboratoire d'Informatique Gaspard-Monge ( LIGM ), Université Paris-Est Marne-la-Vallée ( UPEM ) -École des Ponts ParisTech ( ENPC ) -ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique ( CNRS ), Centre de Mathématiques Laurent Schwartz ( CMLS ), École polytechnique ( X ) -Centre National de la Recherche Scientifique ( CNRS ), Institut de Mécanique Céleste et de Calcul des Ephémérides ( IMCCE ), and Université Pierre et Marie Curie - Paris 6 ( UPMC ) -Institut national des sciences de l'Univers ( INSU - CNRS ) -Observatoire de Paris-Université de Lille-Centre National de la Recherche Scientifique ( CNRS )

Subjects
Laurent series, [MATH.MATH-DS]Mathematics [math]/Dynamical Systems [math.DS], Perturbation (astronomy), Perturbation theory, 01 natural sciences, Quantum mechanics, Renormalization, symbols.namesake, Mathematics - Analysis of PDEs, [PHYS.QPHY]Physics [physics]/Quantum Physics [quant-ph], [MATH.MATH-MP]Mathematics [math]/Mathematical Physics [math-ph], Lie algebra, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], 0101 mathematics, Quantum field theory, Quantum, [MATH.MATH-MG]Mathematics [math]/Metric Geometry [math.MG], Mathematical Physics, Eigenvalues and eigenvectors, Birkhoff decomposition, Mathematics, Mathematical physics, 010102 general mathematics, Statistical and Nonlinear Physics, Mathematics::Spectral Theory, 16. Peace & justice, 010101 applied mathematics, Mould theory, symbols, [ PHYS.MPHY ] Physics [physics]/Mathematical Physics [math-ph], Schrödinger's cat
Abstract

International audience; We derive new expressions for the Rayleigh-Schr\"odinger seriesdescribing the perturbation of eigenvalues of quantumHamiltonians. The method, somehow close to the so-called dimensionalrenormalization in quantum field theory, involves the Birkhoffdecomposition of some Laurent series built up out of explicit fullynon-resonant terms present in the usual expression of theRayleigh-Schr\"odinger series. Our results provide new combinational formulae and a new way \ff{of deriving} perturbation series in Quantum Mechanics. More generally we prove that such a decomposition provides solutions of general normal form problems in Lie algebras.

Published
2018

45. Characterization of bijective digitized rotations on the hexagonal grid

Author

Kacper Pluta, David Cœurjolly, Pascal Romon, Yukiko Kenmochi, Tristan Roussillon, Victor Ostromoukhov, Laboratoire d'Informatique Gaspard-Monge (LIGM), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Analyse et de Mathématiques Appliquées (LAMA), Université Paris-Est Marne-la-Vallée (UPEM)-Fédération de Recherche Bézout-Université Paris-Est Créteil Val-de-Marne - Paris 12 (UPEC UP12)-Centre National de la Recherche Scientifique (CNRS), Geometry Processing and Constrained Optimization (M2DisCo), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), Rendu Réaliste pour la Réalité Augmentée Mobile (R3AM), ANR-15-CE40-0006,CoMeDiC,Métriques convergentes pour le calcul digital(2015), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Centre National de la Recherche Scientifique (CNRS)-Université Paris-Est Créteil Val-de-Marne - Paris 12 (UPEC UP12)-Fédération de Recherche Bézout-Université Paris-Est Marne-la-Vallée (UPEM), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), Laboratoire d'Informatique Gaspard-Monge (ligm), Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA), and ANR-15-CE40-0006,CoMeDiC,Convergent Metrics for Digital Calculus(2015)

Subjects
Statistics and Probability, Square tiling, digitized rotations, digital geometry, digital topology, hexagonal grid, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, bijective transformations, Combinatorics, symbols.namesake, 0202 electrical engineering, electronic engineering, information engineering, Arithmetic function, Digital geometry, 0101 mathematics, Digital topology, Mathematics, Hexagonal tiling, honeycomb geometry, Applied Mathematics, 010102 general mathematics, Condensed Matter Physics, Modeling and Simulation, Eisenstein integer, Bijection, symbols, 020201 artificial intelligence & image processing, Geometry and Topology, Computer Vision and Pattern Recognition, Rotation (mathematics)
Abstract

Submitted to Journal of Mathematical Imaging and Vision.; International audience; Digitized rotations on discrete spaces are usually defined as the composition of a Euclidean rotation and a rounding operator; they are in general not bijective. Nevertheless, it is well known that digitized rotations defined on the square grid are bijective for some specific angles. This infinite family of angles has been characterized by Nouvel and Rémila and more recently by Roussillon and Cœurjolly. In this article, we characterize bijective digitized rotations on the hexagonal grid using arithmetical properties of the Eisenstein integers.

Published
2018

46. 3D Sketching using Multi-View Deep Volumetric Prediction

Author

Adrien Bousseau, Mathieu Aubry, Phillip Isola, Johanna Delanoy, Alexei A. Efros, GRAPHics and DEsign with hEterogeneous COntent ( GRAPHDECO ), Inria Sophia Antipolis - Méditerranée ( CRISAM ), Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria ), Laboratoire d'Informatique Gaspard-Monge ( LIGM ), Université Paris-Est Marne-la-Vallée ( UPEM ) -École des Ponts ParisTech ( ENPC ) -ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique ( CNRS ), UC Berkeley, European Project : ERC-2016-STG 714221,D3, GRAPHics and DEsign with hEterogeneous COntent (GRAPHDECO), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), OpenAI, Lawrence Berkeley National Laboratory [Berkeley] (LBNL), European Project: 714221,H2020 Pilier ERC,ERC-2016-STG-714221,D3(2017), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), and ANR-17-CE23-0008,EnHerit,Exploitation des bases d'images patrimoniales(2017)

Subjects
FOS: Computer and information sciences, Computer science, media_common.quotation_subject, Computer Vision and Pattern Recognition (cs.CV), Computer Science - Computer Vision and Pattern Recognition, ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION, ACM : I.: Computing Methodologies/I.3: COMPUTER GRAPHICS/I.3.5: Computational Geometry and Object Modeling, 02 engineering and technology, computer.software_genre, [ INFO.INFO-CV ] Computer Science [cs]/Computer Vision and Pattern Recognition [cs.CV], Convolutional neural network, CCS CONCEPTS • Computing methodologies → Shape modeling, Rendering (computer graphics), Computer Science - Graphics, Voxel, 0202 electrical engineering, electronic engineering, information engineering, Computer vision, 3D reconstruction, media_common, ComputingMethodologies_COMPUTERGRAPHICS, business.industry, I.3.5, ACM: I.: Computing Methodologies/I.3: COMPUTER GRAPHICS/I.3.5: Computational Geometry and Object Modeling, deep learning, [INFO.INFO-CV]Computer Science [cs]/Computer Vision and Pattern Recognition [cs.CV], 020207 software engineering, Ambiguity, computer.file_format, [ INFO.INFO-GR ] Computer Science [cs]/Graphics [cs.GR], Grid, Computer Graphics and Computer-Aided Design, Sketch, Graphics (cs.GR), [INFO.INFO-GR]Computer Science [cs]/Graphics [cs.GR], Computer Science Applications, ccs:I.: Computing Methodologies/I.3: COMPUTER GRAPHICS/I.3.5: Computational Geometry and Object Modeling, line drawing, Bitmap, 020201 artificial intelligence & image processing, Artificial intelligence, sketch-based modeling, business, computer
Abstract

Sketch-based modeling strives to bring the ease and immediacy of drawing to the 3D world. However, while drawings are easy for humans to create, they are very challenging for computers to interpret due to their sparsity and ambiguity. We propose a data-driven approach that tackles this challenge by learning to reconstruct 3D shapes from one or more drawings. At the core of our approach is a deep convolutional neural network (CNN) that predicts occupancy of a voxel grid from a line drawing. This CNN provides us with an initial 3D reconstruction as soon as the user completes a single drawing of the desired shape. We complement this single-view network with an updater CNN that refines an existing prediction given a new drawing of the shape created from a novel viewpoint. A key advantage of our approach is that we can apply the updater iteratively to fuse information from an arbitrary number of viewpoints, without requiring explicit stroke correspondences between the drawings. We train both CNNs by rendering synthetic contour drawings from hand-modeled shape collections as well as from procedurally-generated abstract shapes. Finally, we integrate our CNNs in a minimal modeling interface that allows users to seamlessly draw an object, rotate it to see its 3D reconstruction, and refine it by re-drawing from another vantage point using the 3D reconstruction as guidance. The main strengths of our approach are its robustness to freehand bitmap drawings, its ability to adapt to different object categories, and the continuum it offers between single-view and multi-view sketch-based modeling., Comment: See our accompanying video on https://youtu.be/DGIYzmlm2pQ, networks and databases available at https://ns.inria.fr/d3/3DSketching/. To appear in PACMCGIT

Published
2018

47. A survey on difference hierarchies of regular languages

Author

Carton, Olivier, Perrin, Dominique, Pin, Jean-Eric, Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Laboratoire d'Informatique Gaspard-Monge (ligm), and Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS)

Subjects
FOS: Computer and information sciences, Nonlinear Sciences::Exactly Solvable and Integrable Systems, [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], 010201 computation theory & mathematics, Formal Languages and Automata Theory (cs.FL), 010102 general mathematics, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Computer Science - Formal Languages and Automata Theory, 68Q70, 68Q45, 20M35, 0102 computer and information sciences, 0101 mathematics, 01 natural sciences
Abstract

Difference hierarchies were originally introduced by Hausdorff and they play an important role in descriptive set theory. In this survey paper, we study difference hierarchies of regular languages. The first sections describe standard techniques on difference hierarchies, mostly due to Hausdorff. We illustrate these techniques by giving decidability results on the difference hierarchies based on shuffle ideals, strongly cyclic regular languages and the polynomial closure of group languages., Logical Methods in Computer Science ; Volume 14, Issue 1 ; 1860-5974

Published
2018
Full Text
View/download PDF

48. Détection de Singularités en temps-réel par combinaison d'apprentissage automatique et web sémantique basés sur Spark

Author

Belabbess, Badre, Bairat, Musab, Lhez, Jérémy, Curé, Olivier, Laboratoire d'Informatique Gaspard-Monge ( LIGM ), Université Paris-Est Marne-la-Vallée ( UPEM ) -École des Ponts ParisTech ( ENPC ) -ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique ( CNRS ), Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), and Curé, Olivier

Subjects
[INFO.INFO-AI] Computer Science [cs]/Artificial Intelligence [cs.AI], [INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB], [ INFO.INFO-DB ] Computer Science [cs]/Databases [cs.DB], [ INFO.INFO-DC ] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], [INFO.INFO-DB] Computer Science [cs]/Databases [cs.DB], [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], [ INFO.INFO-AI ] Computer Science [cs]/Artificial Intelligence [cs.AI], ComputingMilieux_MISCELLANEOUS, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Abstract

International audience

Published
2018

49. Contextualisation de Singularités en Temps-Réel par Extraction de Connaissances du Web des Données

Author

Belabbess , Badre, Lhez , Jérémy, Bairat , Musab, Curé , Olivier, Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Laboratoire d'Informatique Gaspard-Monge ( LIGM ), Université Paris-Est Marne-la-Vallée ( UPEM ) -École des Ponts ParisTech ( ENPC ) -ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique ( CNRS ), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), and Curé, Olivier

Subjects
[INFO.INFO-AI] Computer Science [cs]/Artificial Intelligence [cs.AI], [ INFO.INFO-DB ] Computer Science [cs]/Databases [cs.DB], [INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB], [INFO.INFO-DB] Computer Science [cs]/Databases [cs.DB], [ INFO.INFO-AI ] Computer Science [cs]/Artificial Intelligence [cs.AI], ComputingMilieux_MISCELLANEOUS, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Abstract

International audience

Published
2018

50. A Heuristic Approach for Joint Batch-Routing and Channel Assignment in Hybrid-DCNs

Author

Nadjib Aitsaadi, Ilhem Fajjari, Boutheina Dab, Laboratoire Images, Signaux et Systèmes Intelligents (LISSI), Université Paris-Est Créteil Val-de-Marne - Paris 12 (UPEC UP12), Phare, Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Orange Labs [Chatillon], Orange Labs, Laboratoire d'Informatique Gaspard-Monge (ligm), and Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS)

Subjects
Routing protocol, Channel allocation schemes, business.industry, Heuristic (computer science), Computer science, 020206 networking & telecommunications, 02 engineering and technology, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], 0202 electrical engineering, electronic engineering, information engineering, Wireless, Routing (electronic design automation), business, Dijkstra's algorithm, ComputingMilieux_MISCELLANEOUS, Communication channel, Computer network
Abstract

International audience; To support the drastically increasing data demands, Internet giants are urged to rethink their data center design. Unfortunately, the conventional wired data centers struggle to resist to the huge volume of traffic. In this regard, we investigate a radically new methodology by augmenting the wired Data Center Network (DCN) with wireless communication (60 GHz technology). Heretofore, only few researches have dealt with the optimization of multi-hop communications in such Hybrid DCN (HDCN) infrastructures. In this paper, we address the joint routing and channel allocation issue for batched flow requests within HDCN. We propose a novel strategy named Joint Batch Routing and Channel Assignment Heuristic for HDCN (JBH-HDCN). To do so, we first formulate the problem based on an advanced Multi-Commodity Flow model with interference constraints. Then, we propose i) a heuristic-based solution to find the best sequence to process the batched flow requests, and ii) an advanced Dijkstra algorithm to jointly route and assign channels. We assess the performances of our solution JBH- HDCN under real conditions, within Cisco's MSDC infrastructure, using both: i) Altoona Facebook's DCN workload and ii) uniform traces. To do so, a full protocol stack is implemented within QualNet simulator and extensive simulations are conducted. Obtained results show that our scheme outperforms the related strategies.

Published
2017

Catalog

Books, media, physical & digital resources
See catalog results