Time filter

Source Type

Margenstern M.,CNRS Theoretical and Applied Informatics
Journal of Cellular Automata | Year: 2017

In this paper, we construct a weakly universal cellular automaton on the tessellation {9, 3} which is not rotation invariant but which is truly planar. ©2017 Old City Publishing, Inc.


Le Thi H.A.,CNRS Theoretical and Applied Informatics | Dinh T.P.,Bp08 Avenue Of Luniversite | Van Ngai H.,University of Quynhon
Journal of Global Optimization | Year: 2012

In the present paper, we are concerned with conditions ensuring the exact penalty for nonconvex programming. Firstly, we consider problems with concave objective and constraints. Secondly, we establish various results on error bounds for systems of DC inequalities and exact penalty, with/without error bounds, in DC programming. They permit to recast several class of difficult nonconvex programs into suitable DC programs to be tackled by the efficient DCA. © Springer Science+Business Media, LLC. 2011.


Hoai An L.T.,CNRS Theoretical and Applied Informatics | Hoai Minh L.,CNRS Theoretical and Applied Informatics | Tao P.D.,Avenue Of Luniversite
Pattern Recognition | Year: 2014

The purpose of this paper is to develop new efficient approaches based on DC (Difference of Convex functions) programming and DCA (DC Algorithm) to perform clustering via minimum sum-of-squares Euclidean distance. We consider the two most widely used models for the so-called Minimum Sum-of-Squares Clustering (MSSC in short) that are a bilevel programming problem and a mixed integer program. Firstly, the mixed integer formulation of MSSC is carefully studied and is reformulated as a continuous optimization problem via a new result on exact penalty technique in DC programming. DCA is then investigated to the resulting problem. Secondly, we introduce a Gaussian kernel version of the bilevel programming formulation of MSSC, named GKMSSC. The GKMSSC problem is formulated as a DC program for which a simple and efficient DCA scheme is developed. A regularization technique is investigated for exploiting the nice effect of DC decomposition and a simple procedure for finding good starting points of DCA is developed. The proposed DCA schemes are original and very inexpensive because they amount to computing, at each iteration, the projection of points onto a simplex and/or onto a ball, and/or onto a box, which are all determined in the explicit form. Numerical results on real word datasets show the efficiency, the scalability of DCA and its great superiority with respect to k-means and kernel k-means, standard methods for clustering. © 2013 Elsevier Ltd. All rights reserved.


Margenstern M.,CNRS Theoretical and Applied Informatics
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Year: 2011

In this paper, we show a construction of a weakly universal cellular automaton in the 3D hyperbolic space with two states. Moreover, based on a new implementation of a railway circuit in the dodecagrid, the construction is a truly 3D-one. This result under the hypothesis of weak universality and in this space cannot be improved. © 2011 Springer-Verlag.


Margenstern M.,CNRS Theoretical and Applied Informatics
Theoretical Computer Science | Year: 2011

In this paper, we construct a new weakly universal cellular automaton on the ternary heptagrid. This significantly improves the previous result, obtained by the same author in the same grid with six states. This time, the number of states is four. This is the best result up to date for cellular automata in the hyperbolic plane, with true planar motions. © 2010 Elsevier B.V. All rights reserved.


Margenstern M.,CNRS Theoretical and Applied Informatics
Proceedings of JAC 2010 - Journees Automates Cellulaires | Year: 2010

In this paper, following the way opened by a previous paper deposited on arXiv, see [7], we give an upper bound to the number of states for a hyperbolic cellular automaton in the pentagrid. Indeed, we prove that there is a hyperbolic cellular automaton which is rotation invariant and whose halting problem is undecidable and which has 9 states.


Grange A.,CNRS Theoretical and Applied Informatics
IHM'10 - 22nd Conference Francophone sur l'Interaction Homme-Machine | Year: 2010

ChewingWord is a cross-platform on-screen keyboard for people with motor impairments and/or speech disorders, their care assistants, dyslexics and beginning readers. We focus on its interface, which aims to minimize the cognitive overload inherent to dynamic virtual keyboards, while preserving their main benefits: speed, power and fluidity.


Margenstern M.,CNRS Theoretical and Applied Informatics
Journal of Cellular Automata | Year: 2016

In this paper, we construct a weakly universal cellular automaton with two states only on the tiling {11, 3}. The cellular automaton is rotation invariant and it is a true planar one. © 2016 Old City Publishing, Inc.


Margenstern M.,CNRS Theoretical and Applied Informatics
Fundamenta Informaticae | Year: 2015

In this paper, our results on algorithmic analysis of tiling in hyperbolic spaces are discussed. We overview results and developments obtained by the approach, focusing on the construction of universal cellular automata in hyperbolic spaces with a minimal number of cell states.


Le Thi H.A.,CNRS Theoretical and Applied Informatics | Nguyen M.C.,CNRS Theoretical and Applied Informatics
Data Mining and Knowledge Discovery | Year: 2014

We offer an efficient approach based on difference of convex functions (DC) optimization for self-organizing maps (SOM). We consider SOM as an optimization problem with a nonsmooth, nonconvex energy function and investigated DC programming and DC algorithm (DCA), an innovative approach in nonconvex optimization framework to effectively solve this problem. Furthermore an appropriate training version of this algorithm is proposed. The numerical results on many real-world datasets show the efficiency of the proposed DCA based algorithms on both quality of solutions and topographic maps. © 2014 The Author(s).

Loading CNRS Theoretical and Applied Informatics collaborators
Loading CNRS Theoretical and Applied Informatics collaborators