Author: "Laboratoire d'informatique Fondamentale de Marseille (LIF)" - Searchworks@Jio Institute Digital Library Search Results

Your search keyword '"Laboratoire d'informatique Fondamentale de Marseille (LIF)"' showing total 633 results

Start Over Author "Laboratoire d'informatique Fondamentale de Marseille (LIF)"

633 results on '"Laboratoire d'informatique Fondamentale de Marseille (LIF)"'

1. Vers une représentation des systèmes dynamiques booléens en logique des hypothèses

Author: Siegel, Pierre, Doncescu, Andrei, Risch, Vincent, Sené, Sylvain, Laboratoire des Sciences de l'Information et des Systèmes (LSIS), Centre National de la Recherche Scientifique (CNRS)-Arts et Métiers Paristech ENSAM Aix-en-Provence-Université de Toulon (UTLN)-Aix Marseille Université (AMU), Laboratoire d'informatique Fondamentale de Marseille (LIF), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), Équipe DIagnostic, Supervision et COnduite (LAAS-DISCO), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Arts et Métiers Paristech ENSAM Aix-en-Provence-Centre National de la Recherche Scientifique (CNRS), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Laboratoire d'informatique Fondamentale de Marseille ( LIF ), Aix Marseille Université ( AMU ) -Ecole Centrale de Marseille ( ECM ) -Centre National de la Recherche Scientifique ( CNRS ), Équipe DIagnostic, Supervision et COnduite ( LAAS-DISCO ), Laboratoire d'analyse et d'architecture des systèmes [Toulouse] ( LAAS ), Institut National Polytechnique [Toulouse] ( INP ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Université Paul Sabatier - Toulouse 3 ( UPS ) -Centre National de la Recherche Scientifique ( CNRS ) -Institut National Polytechnique [Toulouse] ( INP ) -Institut National des Sciences Appliquées - Toulouse ( INSA Toulouse ), Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Université Paul Sabatier - Toulouse 3 ( UPS ) -Centre National de la Recherche Scientifique ( CNRS ), Laboratoire des Sciences de l'Information et des Systèmes ( LSIS ), Aix Marseille Université ( AMU ) -Université de Toulon ( UTLN ) -Arts et Métiers Paristech ENSAM Aix-en-Provence-Centre National de la Recherche Scientifique ( CNRS ), Aix Marseille Université (AMU)-Ecole Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'analyse et d'architecture des systèmes [Toulouse] (LAAS), Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UPS), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), and Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UPS)
Subjects: ASP, système dynamique Booléen, logique de défauts, itéractions géne-proteine, [ INFO.INFO-AI ] Computer Science [cs]/Artificial Intelligence [cs.AI], ComputingMilieux_MISCELLANEOUS, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Abstract: National audience; Un système dynamique Booléen (SDB) représente l'évolution au cours du temps des interactions dans un ré-seau fini d'entités. La représentation des réseaux de ré-gulation de gènes, c'est à dire des interactions entre les gènes/protéines d'une cellule, en est un exemple. Dans ce domaine des théorèmes fondateurs ont porté sur les cycles d'interactions et l'étude des cycles, circuits et point fixes est fondamentale. Des travaux ont été fait sur la représentation de certains réseaux biologiques en utilisant des formalismes non-monotones, en particulier la logique de défauts ou les ASP. Mais une représentation des SDB par la plupart des formalismes non-monotones n'est pas satisfaisante, car elle ne permet pas de représenter les cycles stables et instables. Ici on représente les cycles en utilisant la logique des hypothèses qui généralise la logique des défauts. Pour cette logique on a toujours des extensions mais certaines d'entre elles, les extensions fantômes, vont jouer un rôle particulier pour la représentation et la gestion des cycles. L'article donne une représentation des SDB en logique des hypothèses. Le but est de permettre de discriminer les états stables, les cycles stables et instables.
Published: 2017

2. On the construction of the asymmetric Chudnovsky multiplication algorithm in finite fields without derivated evaluation

Author: Bonnecaze , Alexis, Ballet , Stéphane, Baudru , Nicolas, Tukumuli , Mila, Institut de Mathématiques de Marseille (I2M), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), Laboratoire d'informatique Fondamentale de Marseille (LIF), Modélisation et Vérification (MOVE), Laboratoire d'Informatique et Systèmes (LIS), Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU), Institut de Mathématiques de Marseille ( I2M ), Centre National de la Recherche Scientifique ( CNRS ) -Ecole Centrale de Marseille ( ECM ) -Aix Marseille Université ( AMU ), Laboratoire d'informatique Fondamentale de Marseille ( LIF ), Aix Marseille Université ( AMU ) -Ecole Centrale de Marseille ( ECM ) -Centre National de la Recherche Scientifique ( CNRS ), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), and Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)
Subjects: [ MATH ] Mathematics [math], [MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG], [MATH]Mathematics [math], [ MATH.MATH-AG ] Mathematics [math]/Algebraic Geometry [math.AG]
Abstract: International audience; Presented by the Editorial Board The Chudnovsky algorithm for the multiplication in extensions of finite fields provides a bilinear complexity uniformly linear with respect to the degree of the extension. Recently, Randriambololona has generalized the method, allowing asymmetry in the interpolation procedure and leading to new upper bounds on the bilinear complexity. In this note, we describe the construction of this asymmetric method without derived evaluation. To do this, we translate this generalization into the language of algebraic function fields and we give a strategy of construction and implementation.; L'algorithme de multiplication dans les corps finis de Chudnovsky a une complexité bilinéaire uniformément linéaire en le degré de l'extension. Randriambololona a récemment généralisé cette méthode en introduisant l'asymétrie dans la procédure d'interpolation et en obtenant ainsi de nouvelles bornes sur la complexité bilinéaire. Dans cette note, nous décrivons la construction de cette méthode asymétrique sans évaluation dérivée. Pour ce faire, nous traduisons cette généralisation dans le langage des corps de fonctions algébriques, et nous donnons une stratégie de construction et d'implantation.
Published: 2017
Full Text: View/download PDF

3. Actes de l'atelier « Diversité Linguistique et TAL » (DiLiTAL 2017)

Author: Fadoua Atta-Allah, Fatima Agnaou, Khalid Ansar, Aicha Bouhjar, Siham Boulaknadel, Malika Chakiri, Hammou Fadili, Jamal Frain, Jovan Kostov, Alice Millour, Satenik Mkhitaryan, Michael Zock, Institut Royal de la Culture Amazighe, Laboratoire des Sciences du Numérique de Nantes (LS2N), Université de Nantes - Faculté des Sciences et des Techniques, Université de Nantes (UN)-Université de Nantes (UN)-École Centrale de Nantes (ECN)-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Université Paris Descartes - Paris 5 (UPD5), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), Pluralité des langues et des Identités : Didactique, Acquisition, Médiations (PLIDAM EA 4514), Institut National des Langues et Civilisations Orientales (Inalco), Sens, Texte, Informatique, Histoire (STIH), Université Paris-Sorbonne (UP4), Équipe de Recherche en Textes, Informatique, Multilinguisme (ERTIM), Laboratoire d'informatique Fondamentale de Marseille (LIF), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-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)-École Centrale de Nantes (ECN)-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)-HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM), Laboratoire d'Informatique de Nantes Atlantique ( LINA ), Mines Nantes ( Mines Nantes ) -Université de Nantes ( UN ) -Centre National de la Recherche Scientifique ( CNRS ), Université Paris Descartes - Paris 5 ( UPD5 ), Centre d'étude et de recherche en informatique et communications ( CEDRIC ), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise ( ENSIIE ) -Conservatoire National des Arts et Métiers [CNAM] ( CNAM ), Pluralité des langues et des Identités : Didactique, Acquisition, Médiations ( PLIDAM EA 4514 ), Institut National des Langues et Civilisations Orientales ( Inalco ), Sens, Texte, Informatique, Histoire ( STIH ), Université Paris-Sorbonne ( UP4 ), Équipe de Recherche en Textes, Informatique, Multilinguisme ( ERTIM ), Laboratoire d'informatique Fondamentale de Marseille ( LIF ), Aix Marseille Université ( AMU ) -Ecole Centrale de Marseille ( ECM ) -Centre National de la Recherche Scientifique ( CNRS ), IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Nantes - UFR des Sciences et des Techniques (UN UFR ST), Université de Nantes (UN)-Université de Nantes (UN)-École Centrale de Nantes (ECN)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Nantes (ECN)-Université de Nantes - UFR des Sciences et des Techniques (UN UFR ST), Université de Nantes (UN)-Université de Nantes (UN)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), and HESAM Université (HESAM)-HESAM Université (HESAM)
Subjects: TAL, [ SHS.LANGUE ] Humanities and Social Sciences/Linguistics, linguistics, langues peu dotées, [SHS.LANGUE]Humanities and Social Sciences/Linguistics, NLP, less resourced languages, linguistique, diversity, diversité
Abstract: National audience; The goal of the DiLiTAL workshop is to raise awareness among the scientific community of the issues and difficulties encountered in the processing of under-resourced languages (ULL). We also want to point out the necessity of creating generic tools in order to process a large number of languages by identifying their particularities. This workshop’s aim is to pool the different methods and techniques used to boost the construction of resources, as well as the transfer of knowledge and experience in the processing of under-resourced languages.; L’atelier DiLiTAL se donne pour objectif de sensibiliser la communauté́scientifique non seulement aux enjeux et aux difficultés rencontrées dans le traitement des langues peu dotées (LPD), mais aussi àl’intérêt de créer des outils génériques permettant de traiter un très grand nombre de langues,tout en identifiant les besoins spécifiques en fonction de leurs particularités. Cet atelier vise à mettre en commun les différentes méthodes et techniques utilisées pour dynamiser la construction et la mutualisation des ressources, ainsi que le transfert des savoirs et des savoir-faire.
Published: 2017

4. A Causality Based Feature Selection Approach for Multivariate Time Series Forecasting

Author: Hmamouche, Youssef, Casali, Alain, Lakhal, Lotfi, Laboratoire d'informatique Fondamentale de Marseille ( LIF ), Aix Marseille Université ( AMU ) -Ecole Centrale de Marseille ( ECM ) -Centre National de la Recherche Scientifique ( CNRS ), Laboratoire d'informatique Fondamentale de Marseille (LIF), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), Data Mining at scale (DANA), Laboratoire d'Informatique et Systèmes (LIS), Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), and Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Multivariate Time Series Forecasting, [INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB], [ INFO.INFO-DB ] Computer Science [cs]/Databases [cs.DB], [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Granger Causality, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], –Multivariate Time Series Forecasting, Feature selection, Forecasting using Feature Selection, [ INFO.INFO-DS ] Computer Science [cs]/Data Structures and Algorithms [cs.DS], [ STAT.ML ] Statistics [stat]/Machine Learning [stat.ML]
Abstract: International audience; —The field of time series forecasting has progressed significantly in recent decades, specially in regards to the need of forecasting economic data. That said, some issues still arise. In particular when we are working with a set of time series that have a large number of variables. Hence, a selection step is usually needed in order to reduce the number of variables that will contribute to forecast each target time series. In this paper, we propose a feature selection and / or dimension reduction algorithm for forecasting multivariate time series, based on (i) the notion of the Granger causality, and (ii) on a selection step based on a clustering strategy. Finally, we carry out experiments on different real data sets, by comparing our proposal and some of the most used feature selection methods. Experiments show that we improved the forecasting accuracy compared with the evaluated methods.
Published: 2017

5. Packing and Covering with Balls on Busemann Surfaces

Author: Guyslain Naves, Bertrand Estellon, Victor Chepoi, Laboratoire d'Informatique et Systèmes (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), Algorithmique, Combinatoire et Recherche Opérationnelle (ACRO), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), Estellon, Bertrand, Laboratoire d'informatique Fondamentale de Marseille (LIF), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), Laboratoire d'informatique Fondamentale de Marseille ( LIF ), Aix Marseille Université ( AMU ) -Ecole Centrale de Marseille ( ECM ) -Centre National de la Recherche Scientifique ( CNRS ), Math Department - McGill University, McGill University, Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), Department of Mathematics and Statistics [Montréal], and McGill University = Université McGill [Montréal, Canada]
Subjects: FOS: Computer and information sciences, Geodesic, Discrete Mathematics (cs.DM), [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, Disjoint sets, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Curvature, [ MATH.MATH-CO ] Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], 01 natural sciences, Theoretical Computer Science, Combinatorics, Mathematics - Metric Geometry, Euclidean geometry, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], 0202 electrical engineering, electronic engineering, information engineering, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics::Metric Geometry, Simple polygon, [MATH.MATH-MG]Mathematics [math]/Metric Geometry [math.MG], [ INFO.INFO-DS ] Computer Science [cs]/Data Structures and Algorithms [cs.DS], ComputingMilieux_MISCELLANEOUS, Mathematics, Regular polygon, Metric Geometry (math.MG), [ INFO.INFO-DM ] Computer Science [cs]/Discrete Mathematics [cs.DM], Surface (topology), 52A35, 68R05, Metric space, Computational Theory and Mathematics, [INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG], 010201 computation theory & mathematics, [ INFO.INFO-CG ] Computer Science [cs]/Computational Geometry [cs.CG], 020201 artificial intelligence & image processing, [ MATH.MATH-MG ] Mathematics [math]/Metric Geometry [math.MG], Geometry and Topology, Computer Science - Discrete Mathematics
Abstract: In this note we prove that for any compact subset $S$ of a Busemann surface $({\mathcal S},d)$ (in particular, for any simple polygon with geodesic metric) and any positive number $\delta$, the minimum number of closed balls of radius $\delta$ with centers at $\mathcal S$ and covering the set $S$ is at most 19 times the maximum number of disjoint closed balls of radius $\delta$ centered at points of $S$: $\nu(S) \le \rho(S) \le 19\nu(S)$, where $\rho(S)$ and $\nu(S)$ are the covering and the packing numbers of $S$ by ${\delta}$-balls., Comment: 27 pages
Published: 2017
Full Text: View/download PDF

6. Apprentissage d'agents conversationnels pour la gestion de relations clients

Author: Benoit Favre, Frédéric Béchet, Géraldine Damnati, Delphine Charlet, Laboratoire d'informatique Fondamentale de Marseille (LIF), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), France Télécom Recherche et Développement [Lannion] (FTR&D), France Télécom, Orange Labs [Lannion], ANR-15-CE23-0003,DATCHA,Extraction de connaissances à partir de vastes corpus de conversations 'chat' client-opérateurs(2015), Laboratoire d'informatique Fondamentale de Marseille ( LIF ), Aix Marseille Université ( AMU ) -Ecole Centrale de Marseille ( ECM ) -Centre National de la Recherche Scientifique ( CNRS ), France Télécom Recherche et Développement [Lannion] ( FTR&D ), Favre, Benoit, Extraction de connaissances à partir de vastes corpus de conversations 'chat' client-opérateurs - - DATCHA2015 - ANR-15-CE23-0003 - AAPG2015 - VALID, Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), Traitement Automatique du Langage Ecrit et Parlé (TALEP), Laboratoire d'Informatique et Systèmes (LIS), and Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)
Subjects: [ INFO.INFO-TT ] Computer Science [cs]/Document and Text Processing, [ INFO.INFO-TS ] Computer Science [cs]/Signal and Image Processing, [INFO.INFO-TS] Computer Science [cs]/Signal and Image Processing, GRU, [INFO.INFO-TT] Computer Science [cs]/Document and Text Processing, ACM : I.: Computing Methodologies/I.2: ARTIFICIAL INTELLIGENCE/I.2.7: Natural Language Processing, [INFO.INFO-LG] Computer Science [cs]/Machine Learning [cs.LG], seq2seq, [ INFO.INFO-LG ] Computer Science [cs]/Machine Learning [cs.LG], [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL], ACM: I.: Computing Methodologies/I.2: ARTIFICIAL INTELLIGENCE/I.2.7: Natural Language Processing, [INFO.INFO-TT]Computer Science [cs]/Document and Text Processing, Chatbots, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], [INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing, [INFO.INFO-CL] Computer Science [cs]/Computation and Language [cs.CL], [ INFO.INFO-CL ] Computer Science [cs]/Computation and Language [cs.CL], LSTM
Abstract: This work demonstrates the feasability of training chatbots on customer relation conversation traces.Systems based on language models, information retrieval and machine translation are compared., Ce travail démontre la faisabilité d'entraîner des chatbots sur des traces de conversations dans le domaine de la relation client. Des systèmes à base de modèles de langage, de recherche d'information et de traduction sont comparés pour la tâche. ABSTRACT Training chatbots for customer relation management This work demonstrates the feasability of training chatbots on customer relation conversation traces. Systems based on language models, information retrieval and machine translation are compared.
Published: 2017

7. Permutohedra and Associahedra

Author: N. Caspard, F. Wehrung, L. Santocanale, Laboratoire d'Algorithmique Complexité et Logique (LACL), Université Paris-Est Créteil Val-de-Marne - Paris 12 (UPEC UP12)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'informatique Fondamentale de Marseille (LIF), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), Laboratoire de Mathématiques Nicolas Oresme (LMNO), Centre National de la Recherche Scientifique (CNRS)-Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Normandie Université (NU), Laboratoire d'Algorithmique Complexité et Logique ( LACL ), Université Paris-Est Créteil Val-de-Marne - Paris 12 ( UPEC UP12 ) -Centre National de la Recherche Scientifique ( CNRS ), Laboratoire d'informatique Fondamentale de Marseille ( LIF ), Aix Marseille Université ( AMU ) -Ecole Centrale de Marseille ( ECM ) -Centre National de la Recherche Scientifique ( CNRS ), Laboratoire de Mathématiques Nicolas Oresme ( LMNO ), Université de Caen Normandie ( UNICAEN ), Normandie Université ( NU ) -Normandie Université ( NU ) -Centre National de la Recherche Scientifique ( CNRS ), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), Université de Caen Normandie (UNICAEN), and Normandie Université (NU)-Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Cayley graph, [ MATH.MATH-GR ] Mathematics [math]/Group Theory [math.GR], 010102 general mathematics, Coxeter group, Lattice homomorphism, ACM : G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.1: Combinatorics/G.2.1.3: Permutations and combinations, [ INFO.INFO-DM ] Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [ MATH.MATH-CO ] Mathematics [math]/Combinatorics [math.CO], 01 natural sciences, [MATH.MATH-GR]Mathematics [math]/Group Theory [math.GR], Combinatorics, ACM: G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.1: Combinatorics/G.2.1.3: Permutations and combinations, 0103 physical sciences, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], 010307 mathematical physics, 0101 mathematics, Greeks, ComputingMilieux_MISCELLANEOUS, Transposition cipher, Mathematics
Abstract: Historically, notions or problems related to permutations occur — at least — as early as the Antiquity. For example, among the ancient Greeks, Spartans developed the art of encrypting messages via transposition ciphers as part of their military efforts (cf. Kelly [275]).
Published: 2016
Full Text: View/download PDF

8. Exact location of the phase transition for random (1, 2)-QSAT

Author: Creignou, Nadia, Daudé, Hervé, Uwe, Egly, Rossignol, Raphael, Creignou, Nadia, BLANC - Géométrie des mesures convexes et discrètes - - GeMeCoD2011 - ANR-11-BS01-0007 - BLANC - VALID, Laboratoire d'informatique Fondamentale de Marseille ( LIF ), Aix Marseille Université ( AMU ) -Ecole Centrale de Marseille ( ECM ) -Centre National de la Recherche Scientifique ( CNRS ), Institut de Mathématiques de Marseille ( I2M ), Institut für Informationssysteme [Wien], Technische Universität Wien ( TU Wien ), Institut Fourier ( IF ), Centre National de la Recherche Scientifique ( CNRS ) -Université Grenoble Alpes ( UGA ), ANR-11-BS01-0007,GeMeCoD,Géométrie des mesures convexes et discrètes ( 2011 ), Laboratoire d'informatique Fondamentale de Marseille (LIF), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), Institut de Mathématiques de Marseille (I2M), Technische Universität Wien (TU Wien), Institut Fourier (IF), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA), ANR-11-BS01-0007,GeMeCoD,Géométrie des mesures convexes et discrètes(2011), Vienna University of Technology (TU Wien), Institut Fourier (IF ), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), and Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU)
Subjects: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], [ INFO.INFO-DM ] Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], ComputingMilieux_MISCELLANEOUS
Abstract: International audience
Published: 2015

9. Présentation d’un thésaurus des mots d’affects : théorie, méthode et applications

Author: Le Pesant, Denis, Sabatier, Paul, Silberztein, Max, Stéfanini, Marie-hélène, Modèles, Dynamiques, Corpus (MoDyCo), Université Paris Nanterre (UPN)-Centre National de la Recherche Scientifique (CNRS), Université Paris Nanterre (UPN), Laboratoire d'informatique Fondamentale de Marseille (LIF), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), Aix Marseille Université (AMU), Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC), Edition, Littératures, Langages, Informatique, Arts, Didactique, Discours - UFC (UR 4661) (ELLIADD), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC), Peter Bluementhal, Iva Novakova, Dirk Siepmann, Modèles, Dynamiques, Corpus ( MoDyCo ), Université Paris Nanterre ( UPN ) -Centre National de la Recherche Scientifique ( CNRS ), Université Paris Nanterre ( UPN ), Laboratoire d'informatique Fondamentale de Marseille ( LIF ), Aix Marseille Université ( AMU ) -Ecole Centrale de Marseille ( ECM ) -Centre National de la Recherche Scientifique ( CNRS ), Aix Marseille Université ( AMU ), Université de Franche-Comté ( UFC ), Edition, Littératures, Langages, Informatique, Arts, Didactique, Discours - UFC ( ELLIADD ), Université Bourgogne Franche-Comté ( UBFC ) -Université de Franche-Comté ( UFC ), MoDyCo, Laboratoire, Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), and Edition, Littératures, Langages, Informatique, Arts, Didactique, Discours - UFC (EA 4661) (ELLIADD)
Subjects: [ SHS.LANGUE ] Humanities and Social Sciences/Linguistics, [SHS.LANGUE]Humanities and Social Sciences/Linguistics, [SHS.LANGUE] Humanities and Social Sciences/Linguistics, ComputingMilieux_MISCELLANEOUS
Abstract: International audience
Published: 2014

10. Dictionary-Ontology Cross-Enrichment Using TLFi and WOLF to enrich one another

Author: Eckard, Emmanuel, Barque, Lucie, Nasr, Alexis, Sagot, Benoît, Laboratoire d'informatique Fondamentale de Marseille (LIF), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), Lexiques, Dictionnaires, Informatique (LDI), Université Paris 13 (UP13)-Université de Cergy Pontoise (UCP), Université Paris-Seine-Université Paris-Seine-Université Sorbonne Paris Cité (USPC)-Centre National de la Recherche Scientifique (CNRS), Analyse Linguistique Profonde à Grande Echelle, Large-scale deep linguistic processing (ALPAGE), Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Paris Diderot - Paris 7 (UPD7), Michael Zock and Reinhard Rapp, ANR-09-CORD-0008,EDyLex,Enrichissement Dynamique de ressources Lexicales(2009), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), Université Sorbonne Paris Cité (USPC)-Université de Cergy Pontoise (UCP), Université Paris-Seine-Université Paris-Seine-Université Paris 13 (UP13)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'informatique Fondamentale de Marseille ( LIF ), Aix Marseille Université ( AMU ) -Ecole Centrale de Marseille ( ECM ) -Centre National de la Recherche Scientifique ( CNRS ), Lexiques, Dictionnaires, Informatique ( LDI ), Université Paris 13 ( UP13 ) -Université de Cergy Pontoise ( UCP ), Université Paris-Seine-Université Paris-Seine-Université Sorbonne Paris Cité ( USPC ) -Centre National de la Recherche Scientifique ( CNRS ), Large-scale deep linguistic processing ( ALPAGE ), Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -Université Paris Diderot - Paris 7 ( UPD7 ), ANR-09-CORD-0008,EDyLex,Enrichissement Dynamique de Lexiques ( 2009 ), Sagot, Benoît, and Enrichissement Dynamique de ressources Lexicales - - EDyLex2009 - ANR-09-CORD-0008 - CORD - VALID
Subjects: [INFO.INFO-CL] Computer Science [cs]/Computation and Language [cs.CL], [ SHS.LANGUE ] Humanities and Social Sciences/Linguistics, [ INFO.INFO-CL ] Computer Science [cs]/Computation and Language [cs.CL], [SHS.LANGUE]Humanities and Social Sciences/Linguistics, [SHS.LANGUE] Humanities and Social Sciences/Linguistics, [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL]
Abstract: International audience; It has been known since Ide and Veronis that it is impossible to automatically extract an ontology structure from a dictionary, because that information is simply not present. We at- tempt to extract structure elements from a dictionary using clues taken from a formal ontology, and use these elements to match dictionary definitions to ontology synsets; this allows us to enrich the ontology with dictionary definitions, assign ontological structure to the dictionary, and disambiguate elements of definitions and synsets.
Published: 2012

11. Associating parallel automata network dynamics and strictly one-way cellular automata

Author: Perrotin, Pacôme, Laboratoire d'informatique Fondamentale de Marseille (LIF), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), PERROTIN, Pacôme, and Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS)
Subjects: [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Nonlinear Sciences::Cellular Automata and Lattice Gases, Computer Science::Formal Languages and Automata Theory
Abstract: International audience; Automata networks are often conceived as a finite generalization of cellular automata. In this paper, we prove that the limit dynamics of any finite automata network under the parallel update schedule correspond exactly to the fixed points of so-called strictly one-way cellular automata. This correspondence is proven to be exact, as any strictly one-way cellular automata can be transformed into a corresponding automata network, where the attractors of the latter correspond exactly to the fixed points of the former. This transformation is easy to operate by using output functions which have been developed in the author's previous works.
Published: 2021

12. How to learn about space by building and exploring a microworld

Author: Zock, Michael, Briffault, Xavier, Laboratoire d'informatique Fondamentale de Marseille (LIF), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), Centre de Recherche Psychotropes, Santé Mentale, Société (CESAMES), Université Paris Descartes - Paris 5 (UPD5)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'informatique Fondamentale de Marseille ( LIF ), Aix Marseille Université ( AMU ) -Ecole Centrale de Marseille ( ECM ) -Centre National de la Recherche Scientifique ( CNRS ), Centre de Recherche Psychotropes, Santé Mentale, Société ( CESAMES ), Université Paris Descartes - Paris 5 ( UPD5 ) -Institut National de la Santé et de la Recherche Médicale ( INSERM ) -Centre National de la Recherche Scientifique ( CNRS ), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), and Zock, Michael
Subjects: [INFO.INFO-CL] Computer Science [cs]/Computation and Language [cs.CL], [ INFO.INFO-CL ] Computer Science [cs]/Computation and Language [cs.CL], ComputingMilieux_MISCELLANEOUS, [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL]
Abstract: International audience; no abstract
Published: 1995

13. Copyful Streaming String Transducers

Author: Emmanuel Filiot, Pierre-Alain Reynier, Département d'Informatique [Bruxelles] (ULB), Faculté des Sciences [Bruxelles] (ULB), Université libre de Bruxelles (ULB)-Université libre de Bruxelles (ULB), Modélisation et Vérification (MOVE), Laboratoire d'Informatique et Systèmes (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), ANR-16-CE40-0007,DELTA,DÉfis pour la Logique, les Transducteurs et les Automates(2016), Laboratoire d'informatique Fondamentale de Marseille (LIF), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU)-Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), and Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)
Subjects: TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES, Computer science, 0102 computer and information sciences, 01 natural sciences, Theoretical Computer Science, Set (abstract data type), [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], 0101 mathematics, Equivalence (formal languages), Physics::Atmospheric and Oceanic Physics, PSPACE, Variable (mathematics), Discrete mathematics, Algebra and Number Theory, Finite-state machine, 010102 general mathematics, String (computer science), [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], Decidability, Automaton, TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, Computational Theory and Mathematics, 010201 computation theory & mathematics, Computer Science::Programming Languages, Computer Science::Formal Languages and Automata Theory, Information Systems
Abstract: International audience; Copyless streaming string transducers (copyless SST) have been introduced by R. Alur and P. ˇ Cern´yCern´y in 2010 as a one-way determin-istic automata model to define transductions of finite strings. Copyless SST extend deterministic finite state automata with a set of variables in which to store intermediate output strings, and those variables can be combined and updated all along the run, in a linear manner, i.e., no variable content can be copied on transitions. It is known that copyless SST capture exactly the class of MSO-definable string-to-string trans-ductions, and are as expressive as deterministic two-way transducers. They enjoy good algorithmic properties. Most notably, they have decid-able equivalence problem (in PSpace). On the other hand, HDT0L systems have been introduced for a while, the most prominent result being the decidability of the equivalence problem. In this paper, we propose a semantics of HDT0L systems in terms of transductions, and use it to study the class of deterministic copyful SST. Our contributions are as follows: (i) HDT0L systems and total deterministic copyful SST have the same expressive power, (ii) the equivalence problem for deterministic copyful SST and the equivalence problem for HDT0L systems are inter-reducible, in linear time. As a consequence, equivalence of deterministic SST is decid-able, (iii) the functionality of non-deterministic copyful SST is decidable, (iv) determining whether a deterministic copyful SST can be transformed into an equivalent deterministic copyless SST is decidable in polynomial time.
Published: 2021
Full Text: View/download PDF

14. Simulation between natural computation models and automata networks modularity

Author: Perrotin, Pacôme, PERROTIN, Pacôme, Laboratoire d'informatique Fondamentale de Marseille (LIF), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), Aix-Marseile Université, Sylvain Sené, Kévin Perrot, and Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Réseaux d'automates, natural computation, [INFO]Computer Science [cs], Automata network, calcul naturel, [INFO] Computer Science [cs], simulation, ACM: F.: Theory of Computation/F.1: COMPUTATION BY ABSTRACT DEVICES/F.1.1: Models of Computation/F.1.1.0: Automata (e.g., finite, push-down, resource-bounded), ACM: F.: Theory of Computation/F.1: COMPUTATION BY ABSTRACT DEVICES/F.1.1: Models of Computation/F.1.1.3: Relations between models
Abstract: We explore different generalisations about natural computation models. The most theoretical is the notion of simulation between models, for which we describe a series of proposed definitions, by discussing the interests and the flaws of each of them. We take advantage of the most promising definitions to broaden the discussion on the possible consequences of simulation in complexity theory, such as the construction of new complexity classes by proposing the substitution of polynomial reduction by simulation.Our more applied approach consists in the generalisation of automata networks by means of modules that have inputs. This formalism makes it possible to approach the questions of the dynamics of interaction networks from a new angle : we explore its usefulness as a modular tool capable of flexibly simulating many similar objects, as well as the expressiveness of acyclic modules. These allow the characterisation of the dynamics of automata networks in the form of output functions. This expressiveness allows us to describe a process for optimising automata networks that reduces certain networks in size while retaining equivalent attractors., Nous explorons différentes généralisations concernant les modèles de calcul naturel. La plus théorique est la notion de simulation entre modèles, pour laquelle nous décrivons une série de propositions de définition, en discutant des intérêts et des failles de chacune d’elles. Nous profitons des définitions les plus prometteuses pour élargir le propos sur les possibles conséquences de la simulation en théorie de la complexité, comme la construction de nouvelles classes de complexité en proposant la substitution de la réduction polynomiale par la simulation. Notre approche plus appliquée consiste en la généralisation des réseaux d’automates sous formes de modules, qui possèdent des entrées. Ce formalisme permet d’approcher les questions de la dynamique des réseaux d’interactions sous un nouvelangle : nous explorons son utilité en tant qu’outil modulaire propre à simuler de façon flexible de nombreux objets similaires, ainsi que l’expressivité des modules acycliques. Ceux-ci permettent la caractérisation de la dynamique des réseaux d’automates sous la forme de fonctions de sortie. Cette expressivité nous autorise la description d’unprocessus d’optimisation de réseaux d’automates, qui réduit certains réseaux en taille tout en conservant des attracteurs équivalents.
Published: 2021

15. Weakly Modular Graphs and Nonpositive Curvature

Author: Jérémie Chalopin, Hirai Hiroshi, Chepoi Victor, Damian Osajda, Laboratoire d'informatique Fondamentale de Marseille (LIF), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), Universität Wien, Mathematical Institute [Wroclaw], University of Wrocław [Poland] (UWr), Polska Akademia Nauk = Polish Academy of Sciences (PAN), Algorithmique Distribuée (DALGO), Laboratoire d'Informatique et Systèmes (LIS), Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU), Algorithmique, Combinatoire et Recherche Opérationnelle (ACRO), Department of Mathematical Informatics (University of Tokyo), The University of Tokyo (UTokyo), Institut of Mathematics - Polish Academy of Sciences (PAN), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), Uniwersytet Wroclawski, and Chepoi, Victor
Subjects: Applied Mathematics, General Mathematics, 010102 general mathematics, Metric Geometry (math.MG), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], Mathematics - Metric Geometry, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, MR 05C12 (05C75 05E45 20F67 51K05), Mathematics - Combinatorics, Combinatorics (math.CO), 05C12, 51K05, 20F67, 90C27, 0101 mathematics, [MATH.MATH-MG]Mathematics [math]/Metric Geometry [math.MG], ComputingMilieux_MISCELLANEOUS
Abstract: This article investigates structural, geometrical, and topological characterizations and properties of weakly modular graphs and of cell complexes derived from them. The unifying themes of our investigation are various `nonpositive curvature' and `local-to-global' properties and characterizations of weakly modular graphs and their subclasses. Weakly modular graphs have been introduced as a far-reaching common generalization of median graphs (and more generally, of modular and orientable modular graphs), Helly graphs, bridged graphs, and dual polar graphs occurring under different disguises in several seemingly-unrelated fields of mathematics: Metric graph theory, Geometric group theory, Incidence geometries and buildings, Theoretical computer science and combinatorial optimization. We give a local-to-global characterization of weakly modular graphs and their subclasses in terms of simple connectedness of associated triangle-square complexes and specific local combinatorial conditions. In particular, we revisit characterizations of dual polar graphs by Cameron and by Brouwer-Cohen. We also show that (disk-)Helly graphs are precisely the clique-Helly graphs with simply connected clique complexes. With $l_1$-embeddable weakly modular and sweakly modular graphs we associate high-dimensional cell complexes, having several strong topological and geometrical properties (contractibility and the CAT(0) property). Their cells have a specific structure: they are basis polyhedra of even $\triangle$-matroids in the first case and orthoscheme complexes of gated dual polar subgraphs in the second case. We resolve some open problems concerning subclasses of weakly modular graphs: we prove a Brady-McCammond conjecture about CAT(0) metric on the orthoscheme complexes of modular lattices; we answer Chastand's question about prime graphs for pre-median graphs., to appear in Mem. Amer. Math. Soc.
Published: 2020
Full Text: View/download PDF

16. Commutative automata networks

Author: Maximilien Gadouleau, Florian Bridoux, Guillaume Theyssier, Laboratoire d'informatique Fondamentale de Marseille (LIF), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), School of Engineering and Computing Sciences, Durham University, Institut de Mathématiques de Marseille (I2M), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), Hector Zenil, TC 1, and WG 1.5
Subjects: FOS: Computer and information sciences, [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Schedule, Discrete Mathematics (cs.DM), Computer science, [MATH.MATH-DS]Mathematics [math]/Dynamical Systems [math.DS], commutativity, Of the form, Dynamical Systems (math.DS), 0102 computer and information sciences, Computational Complexity (cs.CC), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Boolean networks, FOS: Mathematics, [INFO]Computer Science [cs], Mathematics - Dynamical Systems, 0101 mathematics, Invariant (mathematics), Automata networks, Commutative property, ComputingMilieux_MISCELLANEOUS, Discrete mathematics, Locality, Cellular automaton, Automaton, 010101 applied mathematics, Computer Science - Computational Complexity, 010201 computation theory & mathematics, update schedules, Alphabet, Computer Science - Discrete Mathematics
Abstract: Automata networks are mappings of the form $f: Q^Z \rightarrow Q^Z$, where Q is a finite alphabet and Z is a set of entities; they generalise Cellular Automata and Boolean networks. An update schedule dictates when each entity updates its state according to its local function $f_i: Q^Z \rightarrow Q$. One major question is to study the behaviour of a given automata networks under different update schedules. In this paper, we study automata networks that are invariant under many different update schedules. This gives rise to two definitions, locally commutative and globally commutative networks. We investigate the relation between commutativity and different forms of locality of update functions; one main conclusion is that globally commutative networks have strong dynamical properties, while locally commutative networks are much less constrained. We also give a complete classification of all globally commutative Boolean networks.
Published: 2020
Full Text: View/download PDF

17. Special issue on Structural Information and Communication Complexity

Author: Sébastien Tixeuil, Shantanu Das, Algorithmique Distribuée (DALGO), Laboratoire d'Informatique et Systèmes (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), Networks and Performance Analysis (NPA), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Laboratory of Information, Network and Communication Sciences (LINCS), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut Mines-Télécom [Paris] (IMT)-Sorbonne Université (SU), Laboratoire d'informatique Fondamentale de Marseille (LIF), and Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU)
Subjects: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], General Computer Science, Computer science, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Data science, Theoretical Computer Science, 010201 computation theory & mathematics, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Communication complexity, ComputingMilieux_MISCELLANEOUS
Abstract: International audience
Published: 2020
Full Text: View/download PDF

18. Structural graph-based morphometry: A multiscale searchlight framework based on sulcal pits

Author: Guillaume Auzias, Sylvain Takerkart, Lucile Brun, Olivier Coulon, éQuipe AppRentissage et MultimediA [Marseille] (QARMA), Laboratoire d'informatique Fondamentale de Marseille (LIF), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU)-Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), Institut de Neurosciences de la Timone (INT), Aix Marseille Université (AMU)-Centre National de la Recherche Scientifique (CNRS), Laboratoire des Sciences de l'Information et des Systèmes (LSIS), Centre National de la Recherche Scientifique (CNRS)-Arts et Métiers Paristech ENSAM Aix-en-Provence-Université de Toulon (UTLN)-Aix Marseille Université (AMU), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), and Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Arts et Métiers Paristech ENSAM Aix-en-Provence-Centre National de la Recherche Scientifique (CNRS)
Subjects: Adult, Male, searchlight, Graph kernel, Adolescent, Computer science, brain, Inference, Health Informatics, Similarity measure, Machine learning, computer.software_genre, Sensitivity and Specificity, 050105 experimental psychology, Young Adult, 03 medical and health sciences, 0302 clinical medicine, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], [INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing, [INFO.INFO-IM]Computer Science [cs]/Medical Imaging, Humans, 0501 psychology and cognitive sciences, Radiology, Nuclear Medicine and imaging, graph kernel, sulcal pits, Spatial organization, Cerebral Cortex, Radiological and Ultrasound Technology, business.industry, 05 social sciences, Brain morphometry, Graph based, Reproducibility of Results, Pattern recognition, Magnetic Resonance Imaging, Computer Graphics and Computer-Aided Design, Kernel method, Kernel (image processing), [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], [SDV.NEU]Life Sciences [q-bio]/Neurons and Cognition [q-bio.NC], Female, Computer Vision and Pattern Recognition, Artificial intelligence, business, computer, multi-scale methods, morphometry, Algorithms, 030217 neurology & neurosurgery
Abstract: International audience; Studying the topography of the cortex has proved valuable in order to characterize populations of subjects. In particular, the recent interest towards the deepest parts of the cortical sulci – the so-called sulcal pits – has opened new avenues in that regard. In this paper, we introduce the first fully automatic brain morphometry method based on the study of the spatial organization of sulcal pits – Structural Graph-Based Morphometry (SGBM). Our framework uses attributed graphs to model local patterns of sulcal pits, and further relies on three original contributions. First, a graph kernel is defined to provide a new similarity measure between pit-graphs, with few parameters that can be efficiently estimated from the data. Secondly, we present the first searchlight scheme dedicated to brain morphometry, yielding dense information maps covering the full cortical surface. Finally, a multi-scale inference strategy is designed to jointly analyze the searchlight information maps obtained at different spatial scales. We demonstrate the effectiveness of our framework by studying gender differences and cortical asymmetries: we show that SGBM can both localize informative regions and estimate their preferred spatial scales, while providing results which are consistent with the literature. Thanks to the modular design of our kernel and the vast array of available kernel methods, SGBM can easily be extended to include a more detailed description of the sulcal patterns and solve different statistical problems. Therefore, we suggest that our SGBM framework should be useful for both reaching a better understanding of the normal brain and defining imaging biomarkers in clinical settings.
Published: 2017
Full Text: View/download PDF

19. Transformation from Graphs to Signals and Back

Author: Patrick Flandrin, Céline Robardet, Ronan Hamon, Pierre Borgnat, éQuipe d'AppRentissage de MArseille (QARMA), Laboratoire d'Informatique et Systèmes (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), éQuipe AppRentissage et MultimediA [Marseille] (QARMA), Laboratoire d'informatique Fondamentale de Marseille (LIF), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), Laboratoire de Physique de l'ENS Lyon (Phys-ENS), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), École normale supérieure de Lyon (ENS de Lyon), Data Mining and Machine Learning (DM2L), 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), Robardet, Céline, Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU), École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon, École normale supérieure - Lyon (ENS Lyon), 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), and Université de Lyon-Université Lumière - Lyon 2 (UL2)
Subjects: [INFO.INFO-AI] Computer Science [cs]/Artificial Intelligence [cs.AI], Signal processing, Theoretical computer science, [INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB], Euclidean space, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Duality (optimization), Inverse transform sampling, 020206 networking & telecommunications, Network science, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 02 engineering and technology, [INFO.INFO-LG] Computer Science [cs]/Machine Learning [cs.LG], 01 natural sciences, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], Distance matrix, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], Stochastic block model, 0103 physical sciences, 0202 electrical engineering, electronic engineering, information engineering, [INFO.INFO-DB] Computer Science [cs]/Databases [cs.DB], Sociology, Multidimensional scaling, 010306 general physics, ComputingMilieux_MISCELLANEOUS
Abstract: Network science has been a rapidly evolving field to study systems made of interactions between entities. Studying the structure of such networks reveals indeed the underlying mechanisms of these systems, and has been proven successful in many domains, such as sociology, biology, or geography. Recently, connections between network science and signal processing have emerged, making the use of a wide variety of tools possible to study networks. In this chapter, a focus is made on a methodology introduced to transform a graph into a collection of signals, using a multidimensional scaling technique: by projecting a distance matrix representing relations between vertices of the graph as points in a Euclidean space, it is possible to interpret coordinates of vertices in this space as signals, and take advantage of this dual representation to develop new tools for the study of networks. Deeper considerations of this methodology are proposed, by strengthening the connections between the obtained signals and the common graph structures. A robust inverse transformation method is next described, taking into account possible changes in the signals. Establishing a robust duality between graphs and signals opens up new perspectives, as classical signal processing tools, such as spectral analysis or filtering, are made available for the study of the structure of networks.
Published: 2019
Full Text: View/download PDF

20. Probabilistic epistemic updates on algebras

Author: Conradie, Willem, Frittella, Sabine, Palmigiano, Alessandra, Tzimoulis, Apostolos, Wang, Wen-Fang, van der Hoek, Wiebe, Holliday, Wesley H., Management and Organisation, University of Johannesburg (UJ), Laboratoire d'informatique Fondamentale de Marseille (LIF), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), Applied Logic, Delft University of Technology (TU Delft), van der Hoek W., Holliday W., Wang W., University of the Witwatersrand [Johannesburg] (WITS), Sécurité des Données et des Systèmes (SDS), Laboratoire d'Informatique Fondamentale d'Orléans (LIFO), Université d'Orléans (UO)-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université d'Orléans (UO)-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA), Vrije Universiteit Amsterdam [Amsterdam] (VU), University of Amsterdam [Amsterdam] (UvA), Wang, Wen-Fang, van der Hoek, Wiebe, Holliday, Wesley H., Entrepreneurship & Innovation (ABS, FEB), Faculteit Economie en Bedrijfskunde, University of Johannesburg [South Africa] (UJ), and Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Pointfree semantics, General Computer Science, Duality, Logic, Computer science, Duality (mathematics), 0102 computer and information sciences, 01 natural sciences, Theoretical Computer Science, Development (topology), Computer Science::Logic in Computer Science, FOS: Mathematics, 0101 mathematics, Algebraic number, ComputingMilieux_MISCELLANEOUS, Mathematics, Interpretation (logic), 010102 general mathematics, Probabilistic logic, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], Mathematics - Logic, pointfree semantics, algebraic models, Epistemology, Focus (linguistics), Mathematical theory, Algebra, Math. Subject Class. 03B42 06D20 06D50 06E15, Computational Mathematics, Intuitionistic probabilistic dynamic epistemic logic, Algebraic models, 010201 computation theory & mathematics, Product (mathematics), Intuitionistic modal logic, duality, Logic (math.LO), intuitionistic probabilistic dynamic epistemic logic, intuitionistic modal logic
Abstract: The present paper contributes to the development of the mathematical theory of epistemic updates using the tools of duality theory. Here we focus on Probabilistic Dynamic Epistemic Logic (PDEL). We dually characterize the product update construction of PDEL-models as a certain construction transforming the complex algebras associated with the given model into the complex algebra associated with the updated model. Thanks to this construction, an interpretation of the language of PDEL can be defined on algebraic models based on Heyting algebras. This justifies our proposal for the axiomatization of the intuitionistic counterpart of PDEL, of which prove soundness and completeness with respect to algebraic probabilistic epistemic models., Comment: Final version of the paper
Published: 2019
Full Text: View/download PDF

21. On the complexity of acyclic modules in automata networks

Author: Sylvain Sené, Kévin Perrot, Pacôme Perrotin, Laboratoire d'informatique Fondamentale de Marseille (LIF), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-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: Discrete mathematics, FOS: Computer and information sciences, 050101 languages & linguistics, Computer Science - Logic in Computer Science, Discrete Mathematics (cs.DM), Computer science, Formalism (philosophy), Computation, 05 social sciences, 02 engineering and technology, Extension (predicate logic), Upper and lower bounds, Automaton, Logic in Computer Science (cs.LO), Attractor, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, 0501 psychology and cognitive sciences, [INFO]Computer Science [cs], Limit (mathematics), ComputingMilieux_MISCELLANEOUS, Computer Science - Discrete Mathematics
Abstract: Modules were introduced as an extension of Boolean automata networks. They have inputs which are used in the computation said modules perform, and can be used to wire modules with each other. In the present paper we extend this new formalism and study the specific case of acyclic modules. These modules prove to be well described in their limit behavior by functions called output functions. We provide other results that offer an upper bound on the number of attractors in an acyclic module when wired recursively into an automata network, alongside a diversity of complexity results around the difficulty of deciding the existence of cycles depending on the number of inputs and the size of said cycle., Comment: 21 pages
Published: 2019
Full Text: View/download PDF

22. Apparent insubordination as discourse patterns in French

Author: Deulofeu, Henri-José, Debaisieux, Jeanne-Marie, Martin, Ph., Laboratoire d'informatique Fondamentale de Marseille (LIF), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), Traitement Automatique du Langage Ecrit et Parlé (TALEP), Laboratoire d'Informatique et Systèmes (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU), and deulofeu, henri
Subjects: French, discourse patterns, [SHS.LANGUE]Humanities and Social Sciences/Linguistics, [SHS.LANGUE] Humanities and Social Sciences/Linguistics, syntax, Insubordination
Abstract: International audience; In current syntactic literature, two empirical situations are typically earmarked as cases of "insubordination". Their common trait is that, despite formal features that should technically define them as subordinate clauses (they are preceded by subordinatorsa subordinating conjunction or some other appropriate morpheme), they behave in discourse like "independent sentences". This description takes into account both formally subordinate clauses functioning as independent discourse units (Evans 2007) and peripheral subordinate clauses which display "main clause features" (Debaisieux 2013, Chap 2). Our stance is that, in both cases, the concept of "insubordination" is an artefact of sentence type theory (Struckmeier & Kaiser, 2015). Committed to the pioneering model of Claire Blanche-Benveniste (1990), which posits a fundamental distinction between grammatical syntax on the one hand and discourse syntax on the other, Desbaisieux (2016) has conclusively shown that, in actual fact, neither of the structures identified in the macrosyntactic paradigm as candidates for "insubordination"peripheral clauses with main clauses featuresare in any way governed by the so-called "main clauses" with which they are combined. In this paper we deal with two types of apparent exclamative insubordinates in French introduced respectively by the subordinating conjunctions si and quand. We argue by extending syntactic dependency to discourse that both are regular syntactic patterns.
Published: 2019

23. Eureka! A Simple Solution to the Complex ‘Tip-of-the-Tongue’-Problem

Author: Michael Zock, Laboratoire d'informatique Fondamentale de Marseille (LIF), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), Traitement Automatique du Langage Ecrit et Parlé (TALEP), Laboratoire d'Informatique et Systèmes (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), Bastardas-Boada, A., Massip Bonet, A, Bel-Enguix, G., and Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS)
Subjects: 060201 languages & linguistics, Syntagmatic analysis, Computer science, business.industry, WordNet, 06 humanities and the arts, 02 engineering and technology, [SCCO.LING]Cognitive science/Linguistics, computer.software_genre, Focus (linguistics), Resource (project management), Index (publishing), 0602 languages and literature, [SCCO.PSYC]Cognitive science/Psychology, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Artificial intelligence, [INFO.INFO-HC]Computer Science [cs]/Human-Computer Interaction [cs.HC], Set (psychology), business, computer, Natural language processing, Word (computer architecture), Lemma (morphology)
Abstract: International audience; To search for a word in a dictionary without a proper index is like looking for an address in a city without a decent map. Abstract Dictionaries are repositories of knowledge concerning words. While 1 readers are mostly concerned with meanings, writers are generally more concerned 2 with word forms expressing meanings (lemma). I will focus here on this latter task: 3 building a tool to help authors to find the word they are looking for, word they may 4 know but whose form is eluding them. Put differently, my goal is to build a resource 5 helping authors to overcome the Tip-of-the-Tongue problem (ToT). Obviously, in 6 order to access a word, it must be stored somewhere (brain, resource). Yet this is 7 far from sufficient. Access may depend on many other factors than storage of word 8 forms: organization of the dictionary (index), the user's cognitive state, i.e. available 9 knowledge at the onset of search, the distance between the source-and the target-10 word (direct neighbor or not) , the knowledge of the relationship between the two, 11 etc. I will try to provide evidence for the claim that (word) storage does not guar-12 antee access. To this end I will compare a well-known lexical resource, WordNet 13 (WN), to an equivalent one, but bootstrapped from Wikipedia (WiPe). While both 14 versions contain basically the same set of words, the latter contains many more 15 (syntagmatic) links than WN. This is probably the reason why WiPe outperforms 16 WN. In the last two sections I will explain under what conditions WN is suitable 17 for word access, and what it might take to go beyond the limitations of this famous 18 resource.
Published: 2019
Full Text: View/download PDF

24. Linear Search by a Pair of Distinct-Speed Robots

Author: Tomasz Kociumaka, Jurek Czyzowicz, David Ilcinkas, Leszek Gąsieniec, Ralf Klasing, Dominik Pająk, Evangelos Bampas, School of of Electrical and Computer Engineering [Athens] (School of E.C.E), National Technical University of Athens [Athens] (NTUA), Département d'Informatique et d'Ingénierie (DII), Université du Québec en Outaouais (UQO), Department of Computer Science [Liverpool], University of Liverpool, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), University of Warsaw (UW), Institute of informatics [Wrocław], See paper for details., ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011), ANR-13-JS02-0002,MACARON,Bouger et Calculer: Agents, Robots et Réseaux(2013), ANR-16-CE40-0023,DESCARTES,Abstraction modulaire pour le calcul distribué(2016), ANR-10-IDEX-0003,IDEX BORDEAUX,Initiative d'excellence de l'Université de Bordeaux(2010), Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory, Pajak, Dominik S, Laboratoire d'informatique Fondamentale de Marseille (LIF), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Institute of Informatics [Warsaw], Faculty of Mathematics, Informatics, and Mechanics [Warsaw] (MIMUW), University of Warsaw (UW)-University of Warsaw (UW), and Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU)
Subjects: Engineering, General Computer Science, Computer science, different speeds, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0211 other engineering and technologies, 0102 computer and information sciences, 02 engineering and technology, Bang-bang robot, linear search, 01 natural sciences, Article, Computer Science::Robotics, Position (vector), mobile robots, 0202 electrical engineering, electronic engineering, information engineering, Cartesian coordinate robot, Point (geometry), Computer vision, [INFO]Computer Science [cs], Online algorithm, Simulation, Linear search, 021103 operations research, business.industry, Applied Mathematics, Mobile robot, Computer Science Applications, 010201 computation theory & mathematics, group search, Moment (physics), Line (geometry), Robot, 020201 artificial intelligence & image processing, Artificial intelligence, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], business
Abstract: Two mobile robots are initially placed at the same point on an infinite line. Each robot may move on the line in either direction not exceeding its maximal speed. The robots need to find a stationary target placed at an unknown location on the line. The search is completed when both robots arrive at the target point. The target is discovered at the moment when either robot arrives at its position. The robot knowing the placement of the target may communicate it to the other robot. We look for the algorithm with the shortest possible search time (i.e. the worst-case time at which both robots meet at the target) measured as a function of the target distance from the origin (i.e. the time required to travel directly from the starting point to the target at unit velocity). We consider two standard models of communication between the robots, namely wireless communication and communication by meeting. In the case of communication by meeting, a robot learns about the target while sharing the same location with a robot possessing this knowledge. We propose here an optimal search strategy for two robots including the respective lower bound argument, for the full spectrum of their maximal speeds. This extends the main result of Chrobak et al. (in: Italiano, Margaria-Steffen, Pokorný, Quisquater, Wattenhofer (eds) Current trends in theory and practice of computer science, SOFSEM, 2015) referring to the exact complexity of the problem for the case when the speed of the slower robot is at least one third of the faster one. In the wireless communication model, a message sent by one robot is instantly received by the other robot, regardless of their current positions on the line. For this model, we design a strategy which is optimal whenever the faster robot is at most \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\sqrt{17}+4\approx 8.123$$\end{document}17+4≈8.123 times faster than the slower one. We also prove that otherwise the wireless communication offers no advantage over communication by meeting.
Published: 2019
Full Text: View/download PDF

25. Drawing graphs with vertices and edges in convex position

Author: Ignacio García-Marco, Kolja Knauer, École normale supérieure de Lyon (ENS de Lyon), Modèles de calcul, Complexité, Combinatoire (MC2), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'informatique Fondamentale de Marseille (LIF), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), Algorithmique, Combinatoire et Recherche Opérationnelle (ACRO), Laboratoire d'Informatique et Systèmes (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Lyon (ENS Lyon), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU), and Knauer, Kolja
Subjects: Computational Geometry (cs.CG), FOS: Computer and information sciences, Convex hull, Control and Optimization, Discrete Mathematics (cs.DM), Convex set, Planar point sets, 0102 computer and information sciences, 02 engineering and technology, Subderivative, Convex position, [INFO] Computer Science [cs], Midpoint, 01 natural sciences, Combinatorics, Planar, Minkowski space, Convex polytope, FOS: Mathematics, 0202 electrical engineering, electronic engineering, information engineering, Mathematics - Combinatorics, [INFO]Computer Science [cs], Convex combination, Mathematics, Discrete mathematics, Convex analysis, Regular polygon, Graph, Computer Science Applications, Computational Mathematics, Computational Theory and Mathematics, Steinitz's theorem, 010201 computation theory & mathematics, Computer Science - Computational Geometry, 020201 artificial intelligence & image processing, Combinatorics (math.CO), Geometry and Topology, Minkowski sum, Strong convex dimension, Computer Science - Discrete Mathematics
Abstract: A graph has strong convex dimension $2$, if it admits a straight-line drawing in the plane such that its vertices are in convex position and the midpoints of its edges are also in convex position. Halman, Onn, and Rothblum conjectured that graphs of strong convex dimension $2$ are planar and therefore have at most $3n-6$ edges. We prove that all such graphs have at most $2n-3$ edges while on the other hand we present a class of non-planar graphs of strong convex dimension $2$. We also give lower bounds on the maximum number of edges a graph of strong convex dimension $2$ can have and discuss variants of this graph class. We apply our results to questions about large convexly independent sets in Minkowski sums of planar point sets, that have been of interest in recent years., Comment: 15 pages, 12 figures, improved exposition
Published: 2016
Full Text: View/download PDF

26. The pole behavior of the phase derivative of the short-time Fourier transform

Author: Dominik Bayer, Peter Balazs, Peter Lempel Søndergaard, Florent Jaillet, Laboratoire d'informatique Fondamentale de Marseille (LIF), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), Acoustics Research Institute (ARI), Austrian Academy of Sciences (OeAW), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), and Oticon A/S [Danemark]
Subjects: Phase (waves), 02 engineering and technology, [MATH.MATH-FA]Mathematics [math]/Functional Analysis [math.FA], computer.software_genre, 01 natural sciences, symbols.namesake, [INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing, FOS: Mathematics, 0202 electrical engineering, electronic engineering, information engineering, [MATH]Mathematics [math], 0101 mathematics, Representation (mathematics), Audio signal processing, ComputingMilieux_MISCELLANEOUS, Mathematics, Phase derivative, Applied Mathematics, 010102 general mathematics, Mathematical analysis, Short-time Fourier transform, 020206 networking & telecommunications, Functional Analysis (math.FA), Mathematics - Functional Analysis, Amplitude, Fourier transform, Time-frequency Analysis, Negative peak, symbols, Short-time Fourier transform STFT, [SPI.SIGNAL]Engineering Sciences [physics]/Signal and Image processing, computer
Abstract: The short-time Fourier transform (STFT) is a time-frequency representation widely used in applications, for example in audio signal processing. Recently it has been shown that not only the amplitude, but also the phase of this representation can be successfully exploited for improved analysis and processing. In this paper we describe a rather peculiar pole phenomenon in the phase derivative, a recurring pattern that appears in a characteristic way in the neighborhood around any of the zeros of the STFT, a negative peak followed by a positive one. We describe this phenomenon numerically and provide a complete analytical explanation., Comment: 15 pages, 4 figures; Applied and Computational Harmonic Analysis (in press), available online 22 October 2015
Published: 2016
Full Text: View/download PDF

27. Integrating Selectional Constraints and Subcategorization Frames in a Dependency Parser

Author: Alexis Nasr, Seyed Abolghasem Mirroshandel, Traitement Automatique du Langage Ecrit et Parlé (TALEP), Laboratoire d'Informatique et Systèmes (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), University of Guilan, Laboratoire d'informatique Fondamentale de Marseille (LIF), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), Computer Engineering Department, and Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Linguistics and Language, Computational complexity theory, Computer science, Process (engineering), 02 engineering and technology, computer.software_genre, Language and Linguistics, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], 03 medical and health sciences, 0302 clinical medicine, Artificial Intelligence, Dependency grammar, 0202 electrical engineering, electronic engineering, information engineering, Frame (artificial intelligence), Subcategorization, Parsing, business.industry, 16. Peace & justice, Computer Science Applications, [INFO.INFO-TT]Computer Science [cs]/Document and Text Processing, Constraint (information theory), 030221 ophthalmology & optometry, Independence (mathematical logic), 020201 artificial intelligence & image processing, Artificial intelligence, business, computer, Natural language processing
Abstract: International audience; Statistical parsers are trained on treebanks that are composed of a few thousand sentences. In order to prevent data sparseness and computational complexity, such parsers make strong independence hypotheses on the decisions that are made to build a syntactic tree. These independence hypotheses yield a decomposition of the syntactic structures into small pieces, which in turn prevent the parser from adequately modeling many lexico-syntactic phenomena like selectional constraints and subcategorization frames. Additionally, treebanks are several orders of magnitude too small to observe many lexico-syntactic regularities, such as selectional constraints and subcategorization frames. In this article, we propose a solution to both problems: how to account for patterns that exceed the size of the pieces that are modeled in the parser and how to obtain subcategorization frames and selectional constraints from raw corpora and incorporate them in the parsing process. The method proposed was evaluated on French and on English. The experiments on French showed a decrease of 41.6% of selectional constraint violations and a decrease of 22% of erroneous subcategorization frame assignment. These figures are lower for English: 16.21% in the first case and 8.83% in the second.
Published: 2016
Full Text: View/download PDF

28. Adversarial learning for modeling human motion

Author: Qi Wang, Mickaël Chen, Ludovic Denoyer, Thierry Artières, Laboratoire d'Informatique et Systèmes (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), École Centrale de Marseille (ECM), éQuipe AppRentissage et MultimediA [Marseille] (QARMA), Laboratoire d'informatique Fondamentale de Marseille (LIF), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), éQuipe d'AppRentissage de MArseille (QARMA), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), Machine Learning and Information Access (MLIA), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), and ANR-16-CONV-0002,ILCB,ILCB: Institute of Language Communication and the Brain(2016)
Subjects: Computer science, 02 engineering and technology, Machine learning, computer.software_genre, Motion capture, Field (computer science), [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], Computer graphics, [INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], 0202 electrical engineering, electronic engineering, information engineering, ComputingMilieux_MISCELLANEOUS, Complex data type, business.industry, [INFO.INFO-CV]Computer Science [cs]/Computer Vision and Pattern Recognition [cs.CV], 020207 software engineering, Animation, Computer Graphics and Computer-Aided Design, Variety (cybernetics), [INFO.INFO-TT]Computer Science [cs]/Document and Text Processing, [INFO.INFO-IR]Computer Science [cs]/Information Retrieval [cs.IR], 020201 artificial intelligence & image processing, Computer Vision and Pattern Recognition, Artificial intelligence, business, computer, Software, Generative grammar, Generator (mathematics)
Abstract: We investigate how adversarial learning may be used for various animation tasks related to human motion synthesis. We propose a learning framework that we decline for building various models corresponding to various needs: a random synthesis generator that randomly produces realistic motion capture trajectories; conditional variants that allow controlling the synthesis by providing high-level features that the animation should match; a style transfer model that allows transforming an existing animation in the style of another one. Our work is built on the adversarial learning strategy that has been proposed in the machine learning field very recently (2014) for learning accurate generative models on complex data, and that has been shown to provide impressive results, mainly on image data. We report both objective and subjective evaluation results on motion capture data performed under emotion, the Emilya Dataset. Our results show the potential of our proposals for building models for a variety of motion synthesis tasks.
Published: 2018
Full Text: View/download PDF

29. Towards a Variability Measure for Multiword Expressions

Author: Jean-Yves Antoine, Carlos Ramisch, Caroline Pasquer, Agata Savary, Bases de données et traitement des langues naturelles ( BDTLN ), Laboratoire d'Informatique de l'Université de Tours ( LI ), Université de Tours-Polytech'Tours-Université de Tours-Polytech'Tours, Laboratoire d'informatique Fondamentale de Marseille ( LIF ), Aix Marseille Université ( AMU ) -Ecole Centrale de Marseille ( ECM ) -Centre National de la Recherche Scientifique ( CNRS ), Pasquer, Caroline, Analyse syntaxique et expressions polylexicales pour le fran?ais - - PARSEME-FR2014 - ANR-14-CERA-0001 - Appel à projets générique - VALID, Bases de données et traitement des langues naturelles (BDTLN), Laboratoire d'Informatique Fondamentale et Appliquée de Tours (LIFAT), Université de Tours (UT)-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université de Tours (UT)-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), Traitement Automatique du Langage Ecrit et Parlé (TALEP), Laboratoire d'Informatique et Systèmes (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), ANR-14-CERA-0001,PARSEME-FR,Analyse syntaxique et expressions polylexicales pour le fran?ais(2014), Centre National de la Recherche Scientifique (CNRS)-Université de Tours-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université de Tours-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA), and Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)
Subjects: Computer science, business.industry, Property (programming), Scale (chemistry), Theoretical models, 02 engineering and technology, computer.software_genre, Syntax, Measure (mathematics), [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL], Identification (information), [INFO.INFO-CL] Computer Science [cs]/Computation and Language [cs.CL], 020204 information systems, 0202 electrical engineering, electronic engineering, information engineering, Benchmark (computing), 020201 artificial intelligence & image processing, Relevance (information retrieval), [ INFO.INFO-CL ] Computer Science [cs]/Computation and Language [cs.CL], Artificial intelligence, business, computer, Natural language processing
Abstract: International audience; One of the outstanding properties of multi-word expressions (MWEs), especially verbal ones (VMWEs), important both in theoretical models and applications, is their idiosyncratic variability. Some MWEs are always continuous , while some others admit certain types of insertions. Components of some MWEs are rarely or never modified, while some others admit either specific or unrestricted modification. This unpredictable variability profile of MWEs hinders modeling and processing them as " words-with-spaces " on the one hand, and as regular syntactic structures on the other hand. Since variability of MWEs is a matter of scale rather than a binary property, we propose a 2-dimensional language-independent measure of variability dedicated to verbal MWEs based on syntactic and discontinuity-related clues. We assess its relevance with respect to a linguistic benchmark and its utility for the tasks of VMWE classification and variant identification on a French corpus.
Published: 2018

30. Embeddability into relational lattices is undecidable

Author: Luigi Santocanale, Logique, Interaction, Raisonnement et Inférence, Complexité, Algèbre (LIRICA), Laboratoire d'Informatique et Systèmes (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU), Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU), Laboratoire d'informatique Fondamentale de Marseille (LIF), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), My salary, and Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU)
Subjects: Pure mathematics, Logic, Computer science, High Energy Physics::Lattice, relational lattice, polymodal logic, Distributive lattice, 0102 computer and information sciences, 02 engineering and technology, inner union, Relational algebra, 01 natural sciences, Theoretical Computer Science, generalized ultrametric space, 020204 information systems, Lattice (order), natural join, 0202 electrical engineering, electronic engineering, information engineering, Algebraic number, 0101 mathematics, Mathematics, [MATH.MATH-CT]Mathematics [math]/Category Theory [math.CT], Discrete mathematics, [INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB], 010102 general mathematics, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], Map of lattices, Undecidable problem, [MATH.MATH-LO]Mathematics [math]/Logic [math.LO], Coverability problem, Relational calculus, universal product frame, Computational Theory and Mathematics, 010201 computation theory & mathematics, Codd's theorem, undecidability, Conjunctive query, Software
Abstract: International audience; The natural join and the inner union operations combine relations of a database. Tropashko and Spight realized that these two operations are the meet and join operations in a class of lattices, known by now as the relational lattices. They proposed then lattice theory as an algebraic approach to the theory of databases alternative to the relational algebra. Litak et al. proposed an axiomatization of relational lattices over the signature that extends the pure lattice signature with a constant and argued that the quasiequational theory of relational lattices over this extended signature is undecidable. We prove in this paper that embeddability is undecidable for relational lattices. More precisely, it is undecidable whether a finite subdirectly-irreducible lattice can be embedded into a relational lattice. Our proof is a reduction from the coverability problem of a multimodal frame by a universal product frame and, indirectly, from the representability problem for relation algebras. As corollaries we obtain the following results: the quasiequational theory of relational lattices over the pure lattice signature is undecidable and has no finite base; there is a quasiequation over the pure lattice signature which holds in all the finite relational lattices but fails in an infinite relational lattice.
Published: 2018
Full Text: View/download PDF

31. Computational complexity of the avalanche problem on one dimensional Kadanoff sandpiles

Author: Eric Rémila, Enrico Formenti, Kévin Perrot, Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Modèles Discrets pour les Systèmes Complexes (Laboratoire I3S - MDSC), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), Groupe d'Analyse et de Théorie Economique Lyon - Saint-Etienne (GATE Lyon Saint-Étienne), École normale supérieure de Lyon (ENS de Lyon)-Université Lumière - Lyon 2 (UL2)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Université Jean Monnet - Saint-Étienne (UJM)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'informatique Fondamentale de Marseille (LIF), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), Center for Mathematical Modelling - Centro de Modelamiento Matematico [Santiago] (CMM), Universidad de Chile = University of Chile [Santiago] (UCHILE)-Centre National de la Recherche Scientifique (CNRS), Teijiro Isokawa, Katsunobu Imai, Nobuyuki Matsui, Ferdinand Peper, Hiroshi Umeo, ANR-09-BLAN-0164,EMC,Emergence dans les modèles de calcul(2009), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), Groupe d'analyse et de théorie économique (GATE Lyon Saint-Étienne), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Jean Monnet [Saint-Étienne] (UJM)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-École normale supérieure - Lyon (ENS Lyon), and Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU)
Subjects: FOS: Computer and information sciences, [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Computational complexity theory, Open problem, [MATH.MATH-DS]Mathematics [math]/Dynamical Systems [math.DS], FOS: Physical sciences, 0102 computer and information sciences, Computational Complexity (cs.CC), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, 010305 fluids & plasmas, Sandpile models, Nonlinear Sciences::Adaptation and Self-Organizing Systems, Dimension (vector space), 0103 physical sciences, [INFO]Computer Science [cs], [NLIN.NLIN-CG]Nonlinear Sciences [physics]/Cellular Automata and Lattice Gases [nlin.CG], [NLIN.NLIN-AO]Nonlinear Sciences [physics]/Adaptation and Self-Organizing Systems [nlin.AO], Dimension sensitive problems, Condensed Matter - Statistical Mechanics, Mathematics, Discrete mathematics, Statistical Mechanics (cond-mat.stat-mech), Abelian sandpile model, Discrete dynamical systems, Computational complexity, Computer Science - Computational Complexity, Monotone polygon, 010201 computation theory & mathematics, [NLIN.NLIN-CD]Nonlinear Sciences [physics]/Chaotic Dynamics [nlin.CD], Condensed Matter::Statistical Mechanics
Abstract: In this paper we prove that the general avalanche problem AP is in NC, for the Kadanoff sandpile model in one dimension, answering an open problem of Formenti, Goles and Martin in 2010. Thus adding one more item to the (slowly) growing list of dimension sensitive problems since in higher dimensions the problem is P-complete (for monotone sandpiles).
Published: 2018
Full Text: View/download PDF

32. Le projet ORFÉO : un corpus d’étude pour le français contemporain

Author: Henri-José Deulofeu, Jeanne-Marie Debaisieux, Christophe Benzitoun, Analyse et Traitement Informatique de la Langue Française (ATILF), Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Lattice - Langues, Textes, Traitements informatiques, Cognition - UMR 8094 (Lattice), Université Sorbonne Nouvelle - Paris 3-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Université Sorbonne Paris Cité (USPC)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'informatique Fondamentale de Marseille (LIF), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), Université Sorbonne Nouvelle - Paris 3-Université Sorbonne Paris Cité (USPC)-Centre National de la Recherche Scientifique (CNRS)-Université Paris sciences et lettres (PSL)-Département Littératures et langage (LILA), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL), ANR-12-CORP-0005,ORFEO,Outils et Recherches sur le Français Écrit et Oral(2012), Université Sorbonne Nouvelle - Paris 3-Université Sorbonne Paris Cité (USPC)-Centre National de la Recherche Scientifique (CNRS)-Université Paris sciences et lettres (PSL)-Département Littératures et langage - ENS Paris (LILA), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-École normale supérieure - Paris (ENS-PSL), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), Département Littératures et langage - ENS Paris (LILA), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Sorbonne Paris Cité (USPC)-Université Sorbonne Nouvelle - Paris 3, Lattice - Langues, Textes, Traitements informatiques, Cognition - UMR 8094 (LattIce), and Paris Sciences et Lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Sorbonne Paris Cité (USPC)-École normale supérieure - Paris (ENS Paris)-Université Sorbonne Nouvelle - Paris 3
Subjects: Oral, 060201 languages & linguistics, requêtes, français parlé, dépendances syntaxiques, 06 humanities and the arts, 02 engineering and technology, POS annotation, [SCCO.LING]Cognitive science/Linguistics, Corpus, corpus outillé, spoken and written French, dependency annotation, POS, equipped corpus, 0602 languages and literature, 0202 electrical engineering, electronic engineering, information engineering, annotations, General Earth and Planetary Sciences, 020201 artificial intelligence & image processing, ComputingMilieux_MISCELLANEOUS, General Environmental Science, français écrit
Abstract: L’article présente le projet ORFEO (outils pour l’étude du Français écrit et oral). Ce projet a consisté à rassembler 4M de mots de Français oral et 6M de mots d’écrit à partir de ressources existantes. Les ressources orales ont été unifiées dans un format trs et alignées avec les fichiers sons au phonème. Les corpus sont présentés avec des métadonnées qui permettent de constituer des sous-corpus d’étude. Les données orales ont été segmentées et annotées en POS et relations de dépendance semi automatiquement. La précision des annotations a fait l’objet d’une évaluation. L’ensemble est interrogeable à partir d’une plateforme adaptée du logiciel libre ANNIS. La ressource sera mise à disposition en open source courant 2017. The paper presents the outcomes of the project ORFEO (tools for the study of spoken and written French). The outcomes consist of a 4M words spoken French and 6M written French sampled corpus. Detailed metadata allows the user to build his own study corpus according to his research purposes. Oral resources have been unified under trs. Format aligned with sound files. Spoken data have been segmented and annotated into POS and dependency relations. The precision of these annotations has been evaluated and meets the current standards. Queries are possible through a platform adapted from ANNIS free software. The whole resource will be available during the year 2017.
Published: 2018
Full Text: View/download PDF

33. Set-Constrained Delivery Broadcast: Definition, Abstraction Power, and Computability Limits

Author: Damien Imbs, Matthieu Perrin, Achour Mostefaoui, Michel Raynal, Algorithmique Distribuée (DALGO), Laboratoire d'Informatique et Systèmes (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), Laboratoire des Sciences du Numérique de Nantes (LS2N), Université de Nantes - UFR des Sciences et des Techniques (UN UFR ST), Université de Nantes (UN)-Université de Nantes (UN)-École Centrale de Nantes (ECN)-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), the World Is Distributed Exploring the tension between scale and coordination (WIDE), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), ANR-16-CE40-0023,DESCARTES,Abstraction modulaire pour le calcul distribué(2016), ANR-16-CE25-0005,OBrowser,Applications décentralisées sur navigateurs(2016), Laboratoire d'informatique Fondamentale de Marseille (LIF), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), Gestion de Données Distribuées (GDD), Université de Nantes (UN)-Université de Nantes (UN)-École Centrale de Nantes (ECN)-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Nantes - UFR des Sciences et des Techniques (UN UFR ST), As Scalable As Possible: foundations of large scale dynamic distributed systems (ASAP), SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Université de Bretagne Sud (UBS)-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)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria), Institut Universitaire de France (IUF), Ministère de l'Education nationale, de l’Enseignement supérieur et de la Recherche (M.E.N.E.S.R.), LIF, Université Aix-Marseille, LINA-University of Nantes, IMDEA Software Institute, Institut Universitaire de France, IRISA, Université de Rennes, ANR-14-CE35-0010,DISCMAT,Mathematical Methods in Distributed Computing(2014), Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), 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)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), Gestion de Données Distribuées (LS2N - équipe GDD), IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), and Université de Nantes (UN)-Université de Nantes (UN)-École Centrale de Nantes (ECN)-Centre National de la Recherche Scientifique (CNRS)
Subjects: FOS: Computer and information sciences, Theoretical computer science, Linearizability, Computer science, Lattice agreement, 0102 computer and information sciences, 02 engineering and technology, Conflict-free replicated data type, Design simplicity, 01 natural sciences, Process crash, Abstraction layer, Communication abstraction, 0202 electrical engineering, electronic engineering, information engineering, Distributed task, Asynchronous system, Snapshot object, Computability, 020206 networking & telecommunications, Read/write atomic register, 16. Peace & justice, Message-passing system, Computer Science - Distributed, Parallel, and Cluster Computing, 010201 computation theory & mathematics, Asynchronous communication, Snapshot (computer storage), Distributed, Parallel, and Cluster Computing (cs.DC), Communication pattern, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Abstraction
Abstract: This paper introduces a new communication abstraction, called Set-Constrained Delivery Broadcast (SCD-broadcast), whose aim is to provide its users with an appropriate abstraction level when they have to implement objects or distributed tasks in an asynchronous message-passing system prone to process crash failures. This abstraction allows each process to broadcast messages and deliver a sequence of sets of messages in such a way that, if a process delivers a set of messages including a message m and later delivers a set of messages including a message m ' , no process delivers first a set of messages including m ' and later a set of message including m. After having presented an algorithm implementing SCD-broadcast, the paper investigates its programming power and its computability limits. On the "power" side it presents SCD-broadcast-based algorithms, which are both simple and efficient, building objects (such as snapshot and conflict-free replicated data), and distributed tasks. On the "computability limits" side it shows that SCD-broadcast and read/write registers are computationally equivalent., Comment: arXiv admin note: substantial text overlap with arXiv:1702.08176
Published: 2018
Full Text: View/download PDF

34. Laughter Animation Generation

Author: Yu Ding, Catherine Pelachaud, Thierry Artières, University of Houston, École Centrale de Marseille (ECM), éQuipe AppRentissage et MultimediA [Marseille] (QARMA), Laboratoire d'informatique Fondamentale de Marseille (LIF), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), Institut des Systèmes Intelligents et de Robotique (ISIR), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS), Bertram Müller, Sebastian I. Wolf, Gert-Peter Brueggemann, Zhigang Deng, Andrew McIntosh, Freeman Miller, William Scott Selbie, Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU)-Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), and Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU)
Subjects: Communication, Computer science, business.industry, media_common.quotation_subject, 0206 medical engineering, 05 social sciences, ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION, 020207 software engineering, Animation, 02 engineering and technology, 020601 biomedical engineering, 050105 experimental psychology, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], Laughter, ComputerApplications_MISCELLANEOUS, 0202 electrical engineering, electronic engineering, information engineering, 0501 psychology and cognitive sciences, [INFO.INFO-HC]Computer Science [cs]/Human-Computer Interaction [cs.HC], business, media_common, ComputingMethodologies_COMPUTERGRAPHICS
Abstract: International audience; Laughter is an important communicative signal in human-human communication. It involves the whole body, from lip motion, facial expression, to rhythmic body and shoulder movement. Laughter is an important social signal in human-human interaction and may convey a wide range of meanings (extreme happiness, social bounding, politeness, irony,). To enhance human-machine interactions, efforts have been made to endow embodied conversational agents, ECAs, with laughing capabilities. Recently, motion capture technologies have been applied to record laughter behaviors including facial expressions and body movements. It allows investigating the temporal relationship of laughter behaviors in details. Based on the available data, researchers have made efforts to develop automatic generation models of laughter animations. These models control the multimodal behaviors of ECAs including lip motions, upper facial expressions, head rotations, shoulder shaking, and torso movements. The underlying idea of these works is to propose a statistical framework able to automatically capture the correlation between laughter audio and multimodal behaviors. In the synthesis phase, the captured correlation is rendered into synthesized animations according to laughter audio given in input. This chapter reviews existing works on automatic generation of laughter animation.
Published: 2018
Full Text: View/download PDF

35. Do Hard SAT-Related Reasoning Tasks Become Easier in the Krom Fragment?

Author: Creignou, Nadia, Pichler, Reinhard, Woltran, Stefan, Logique, Interaction, Raisonnement et Inférence, Complexité, Algèbre (LIRICA), Laboratoire d'Informatique et Systèmes (LIS), Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU), Institute of Information Systems, Vienna University of Technology (TU Wien), Creignou, Nadia, Laboratoire d'informatique Fondamentale de Marseille (LIF), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), and Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)
Subjects: FOS: Computer and information sciences, [INFO.INFO-AI] Computer Science [cs]/Artificial Intelligence [cs.AI], [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Computer Science - Logic in Computer Science, Krom Formulas, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], Complexity, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Logic in Computer Science (cs.LO), [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], Belief Revision, [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC], Abduction, Satisfiability, ComputingMilieux_MISCELLANEOUS
Abstract: Many reasoning problems are based on the problem of satisfiability (SAT). While SAT itself becomes easy when restricting the structure of the formulas in a certain way, the situation is more opaque for more involved decision problems. We consider here the CardMinSat problem which asks, given a propositional formula $\phi$ and an atom $x$, whether $x$ is true in some cardinality-minimal model of $\phi$. This problem is easy for the Horn fragment, but, as we will show in this paper, remains $\Theta_2$-complete (and thus $\mathrm{NP}$-hard) for the Krom fragment (which is given by formulas in CNF where clauses have at most two literals). We will make use of this fact to study the complexity of reasoning tasks in belief revision and logic-based abduction and show that, while in some cases the restriction to Krom formulas leads to a decrease of complexity, in others it does not. We thus also consider the CardMinSat problem with respect to additional restrictions to Krom formulas towards a better understanding of the tractability frontier of such problems., Logical Methods in Computer Science ; Volume 14, Issue 4 ; 1860-5974
Published: 2018
Full Text: View/download PDF

36. Analyse automatique FrameNet : une étude sur un corpus français de textes encyclopédiques

Author: Marzinotto, Gabriel, Damnati, Géraldine, Bechet, Frederic, Orange Labs [Lannion], France Télécom, Traitement Automatique du Langage Ecrit et Parlé (TALEP), Laboratoire d'Informatique et Systèmes (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), France Télécom Recherche et Développement [Lannion] (FTR&D), Laboratoire d'informatique Fondamentale de Marseille (LIF), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), and Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)
Subjects: Semantic frame analysis, [INFO.INFO-TT]Computer Science [cs]/Document and Text Processing, FOS: Computer and information sciences, textes encyclopédiques, Computer Science - Computation and Language, Analyse en cadres sémantiques, encyclopedic texts, sequence labeling, Computation and Language (cs.CL), étiquetage de séquence, [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL], [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Abstract: This article presents an automatic frame analysis system evaluated on a corpus of French encyclopedic history texts annotated according to the FrameNet formalism. The chosen approach relies on an integrated sequence labeling model which jointly optimizes frame identification and semantic role segmentation and identification. The purpose of this study is to analyze the task complexity from several dimensions. Hence we provide detailed evaluations from a feature selection point of view and from the data point of view., Comment: in French
Published: 2018
Full Text: View/download PDF

37. Comment explorer un arbre inconnu avec des agents à énergie limitée ?

Author: Bampas, Evangelos, Chalopin, Jérémie, Das, Shantanu, Hackfeld, Jan, Karousatou, Christina, Laboratoire d'informatique Fondamentale de Marseille (LIF), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), Institute of Mathematics, TU Berlin, Technische Universität Berlin (TU), ANR-14-CE36-0002,ANCOR,Algorithm Design for Microrobots with Energy Constraints(2014), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), Algorithmique Distribuée (DALGO), Laboratoire d'Informatique et Systèmes (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), and Technical University of Berlin / Technische Universität Berlin (TU)
Subjects: Computer Science::Multiagent Systems, FOS: Computer and information sciences, Computer Science - Data Structures and Algorithms, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], agents mobiles, Data Structures and Algorithms (cs.DS), énergie limitée, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], exploration, arbre inconnu
Abstract: International audience; We wish to explore an unknown tree with a team of k >= 1 initially collocated mobile agents. Each agent has limited energy and cannot,as a result, traverse more than B edges. The goal is to maximize the number of nodes collectively visited by all agents during the execution.Initially, the agents have no knowledge about the structure of the tree,but they gradually discover the topology as they traverse new edges. We assume that the agents can communicate with each other at arbitrary distances, therefore the knowledge obtained by one agent after traversing an edge is instantaneously transmitted to the other agents.We propose an intuitive algorithm based on depth-first search and westudy its performance compared to the optimal solution that we could obtain if we knew in advance the map of the tree. We prove that this algorithm has a constant competitive ratio. We also provide a lower bound on the competitive ratio of any algorithm.; On souhaite explorer un arbre inconnu avec une équipe de k \geq 1 agents mobiles initialement regroupés sur un sommet. Chaque agent dispose d'une énergie limitée et ne peut pas traverser plus de B arêtes. On souhaite maximiser le nombre de sommets visités par l'équipe d'agents lors de l'exécution. Initialement, les agents n'ont aucune connaissance sur la structure de l'arbre, mais ils en découvrent la topologie au fur et à mesure qu’ils traversent de nouvelles arêtes. Nous supposons que les agents peuvent communiquer entre eux à distance illimitée, donc la connaissance qu'un agent obtient lors de la traversée d'une arête est instantanément transmise aux autres agents. Nous proposons un algorithme très intuitif, basé sur le parcours en profondeur, et nous étudions son efficacité par rapport à la solution optimale qu'on peut obtenir lorsqu'on connaît initialement la carte. Nous prouvons que cet algorithme a un rapport de compétitivité constant. Nous fournissons également une borne inférieure sur le rapport de compétitivité réalisable par un algorithme quelconque.
Published: 2018
Full Text: View/download PDF

38. Cycles, double-cycles d’interactions et modes de mise à jour

Author: Sylvain Sené, Tarek Melliti, Damien Regnault, Mathilde Noual, Informatique, Biologie Intégrative et Systèmes Complexes (IBISC), Université d'Évry-Val-d'Essonne (UEVE), Modèles Discrets pour les Systèmes Complexes (Laboratoire I3S - MDSC), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Laboratoire d'informatique Fondamentale de Marseille (LIF), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), Institut Rhône-Alpin des systèmes complexes (IXXI), École normale supérieure - Lyon (ENS Lyon)-Université Lumière - Lyon 2 (UL2)-Université Joseph Fourier - Grenoble 1 (UJF)-Université Jean Moulin - Lyon 3 (UJML), 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), and Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)
Subjects: parallélisme et asynchronisme, systèmes dynamiques discrets, cycles, [INFO]Computer Science [cs], parallelism and asynchronism, automata networks, Réseaux d'interactions
Abstract: National audience; Our daily life more and more inﬂuenced by social networks, ourselves widely depending on biological regulation networks, and the physical world together with the particle systems that compose it highlight that we are all closely concerned with interaction networks. However, our knowledge of them is far from complete and it seems necessary, or at the very least useful, to better apprehend and comprehend their intrinsic properties, like the relations between their architecture and their dynamics notably and their link with respect to “time”. Considering Boolean automata networks as a model of interaction networks, we present in this article a synthesis of recent results about the role of retroaction cycles and their intersections on their asymptotic dynamical behaviour, by emphasising the impact of the automata updating modes.; Qu'il s'agisse de notre vie quotidienne à travers les réseaux sociaux, de ce qui constitue notre essence avec les réseaux de régulation biologique, ou même du monde physique auquel nous appartenons et des systèmes de particules qui le constituent, nous sommes tous concernés de très près par les réseaux d'interactions. Or, les connaissances acquises à leur sujet ne sont que très partielles et il semble aujourd'hui nécessaire, ou tout du moins utile, de mieux appréhender et comprendre leurs propriétés intrinsèques, et notamment les relations entre leur architecture et leur dynamique ainsi que leur rapport au \og temps \fg{}. En considérant comme modèle général de réseaux d'interactions les réseaux d'automates booléens, nous présentons dans cet article une synthèse de résultats récents sur le rôle de la présence de cycles de rétroaction et de leurs intersections sur leur comportement asymptotique, en mettant notamment en avant l'influence des modes de mise à jour des automates.
Published: 2015
Full Text: View/download PDF

39. Piles de sable décroissantes 1D. Classification expérimentale d'émergences

Author: Eric Rémila, Kévin Perrot, Laboratoire d'informatique Fondamentale de Marseille (LIF), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique et Systèmes (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), Center for Mathematical Modelling - Centro de Modelamiento Matematico [Santiago] (CMM), Universidad de Chile = University of Chile [Santiago] (UCHILE)-Centre National de la Recherche Scientifique (CNRS), Groupe d'Analyse et de Théorie Economique Lyon - Saint-Etienne (GATE Lyon Saint-Étienne), École normale supérieure de Lyon (ENS de Lyon)-Université Lumière - Lyon 2 (UL2)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Université Jean Monnet - Saint-Étienne (UJM)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), Groupe d'analyse et de théorie économique (GATE Lyon Saint-Étienne), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Jean Monnet [Saint-Étienne] (UJM)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université Lumière - Lyon 2 (UL2)-École normale supérieure - Lyon (ENS Lyon)
Subjects: sandpile, fixed points, Philosophy, Piles de sable, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [SHS.ECO]Humanities and Social Sciences/Economics and Finance, 01 natural sciences, [SHS]Humanities and Social Sciences, 010201 computation theory & mathematics, points fixes, 0202 electrical engineering, electronic engineering, information engineering, emergence, 020201 artificial intelligence & image processing, Humanities
Abstract: International audience; The dynamics of decreasing sandpile models in one dimension lets regular patterns appear after a seemingly unordered phase of evolution. In this article, we present simulation results exhibiting emergence phenomena sustained by different mechanisms. The definition of decreasing sandpile models is argued, its main properties are demonstrated, and the observations are discussed around the statement of two conjectures.; La dynamique des modèles de piles de sable décroissantes en une dimension laisse apparaître des motifs réguliers après une phase d'évolution à l'allure désordonnée. Dans cet article, nous présentons les résultats de simulations mettant en avant des phénomènes d'émergence entretenus par différents mécanismes. La définition des modèles est argumentée, ses premières propriétés sont démontrées, et les observations sont discutées autour de la formulation de deux conjectures.
Published: 2015
Full Text: View/download PDF

40. On the expressivity of time-varying graphs

Author: Masafumi Yamashita, Paola Flocchini, Nicola Santoro, Arnaud Casteigts, Emmanuel Godard, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), School of Information Technology and Engineering [Ottawa] (SITE), University of Ottawa [Ottawa], Laboratoire d'informatique Fondamentale de Marseille (LIF), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), School of Computer Science [Ottawa], Carleton University, Theoretical Computer Science Group (TCSG), Kyushu University, Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), and Kyushu University [Fukuoka]
Subjects: Discrete mathematics, Vehicular ad hoc network, General Computer Science, Unit of time, 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Theoretical Computer Science, Rendering (computer graphics), Automaton, Turing machine, symbols.namesake, Regular language, 010201 computation theory & mathematics, If and only if, Bounded function, 0202 electrical engineering, electronic engineering, information engineering, symbols, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Computer Science::Operating Systems, Mathematics
Abstract: In highly dynamic systems (such as wireless mobile ad hoc networks, robotic swarms, vehicular networks, etc.) connectivity does not necessarily hold at a given time but temporal paths, or journeys, may still exist over time and space, rendering computing possible; some of these systems allow waiting (i.e., pauses at intermediate nodes, also referred to as store-carry-forward strategies) while others do not. These systems are naturally modeled as time-varying graphs, where the presence of an edge and its latency vary as a function of time; in these graphs, the distinction between waiting and not waiting corresponds to the one between indirect and direct journeys.We consider the expressivity of time-varying graphs, in terms of the languages generated by the feasible journeys. We examine the impact of waiting by studying the difference in the type of language expressed by indirect journeys (i.e., waiting is allowed) and by direct journeys (i.e., waiting is unfeasible), under various assumptions on the functions that control the presence and latency of edges. We prove a general result which implies that, if waiting is not allowed, then the set of languages Lnowait that can be generated contains all computable languages when the presence and latency functions are computable. On the other end, we prove that, if waiting is allowed, then the set of languages Lwait contains all and only regular languages; this result, established using algebraic properties of quasi-orders, holds even if the presence and latency are unrestricted (e.g., possibly non-computable) functions of time.In other words, we prove that, when waiting is allowed, the power of the accepting automaton can drop drastically from being at least as powerful as a Turing machine, to becoming that of a Finite-State Machine. This large gap provides an insight on the impact of waiting in time-varying graphs.We also study bounded waiting, in which waiting is allowed at a node for at most d time units, and prove that Lwait[d]=Lnowait; that is, the power of the accepting automaton decreases only if waiting time is unbounded.
Published: 2015
Full Text: View/download PDF

41. A characterization of oblivious message adversaries for which Consensus is solvable

Author: Étienne Coulouma, Emmanuel Godard, Joseph G. Peters, Laboratoire d'informatique Fondamentale de Marseille (LIF), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-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: TheoryofComputation_MISCELLANEOUS, Theoretical computer science, General Computer Science, Computer science, Message passing, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Characterization (mathematics), Adversary, Network topology, Theoretical Computer Science, Set (abstract data type), Consensus, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], ComputingMilieux_MISCELLANEOUS, Adversary model, Computer Science::Cryptography and Security
Abstract: We consider the Consensus problem on arbitrary oblivious message adversaries. A message adversary models a communication network whose topology evolves from round to round. We make no assumptions about the possible topologies. A message adversary is oblivious if the set of possible topologies is the same at every round.We give the first complete necessary and sufficient condition for message adversaries that admits a Consensus algorithm. For the necessary part we present a specialized bivalency proof. For the sufficiency part, we present a new algorithm that is based upon reconstructing a partial, but significant, view of the actual communications that occurred during the evolution of the network. This reconstruction might be of independent interest.
Published: 2015
Full Text: View/download PDF

42. Mapping Simple Polygons

Author: Jérémie Chalopin, Matúš Mihalák, Peter Widmayer, Shantanu Das, Yann Disser, Laboratoire d'informatique Fondamentale de Marseille (LIF), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), Centre National de la Recherche Scientifique (CNRS), Institut für Mathematik [Berlin], Technische Universität Berlin (TU), Institute of Theoretical Computer Science [Zurich], Eidgenössische Technische Hochschule - Swiss Federal Institute of Technology [Zürich] (ETH Zürich), Dept. of Advanced Computing Sciences, RS: FSE DACS, Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), and Technical University of Berlin / Technische Universität Berlin (TU)
Subjects: Mathematics::Functional Analysis, Graph center, Visibility graph, Mathematics::History and Overview, ComputingMilieux_PERSONALCOMPUTING, Neighbourhood (graph theory), Computer Science::Computational Geometry, Biconnected graph, Computer Science::Computers and Society, Combinatorics, Physics::Popular Physics, TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, Mathematics (miscellaneous), Graph power, TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY, Wheel graph, [INFO]Computer Science [cs], Path graph, ComputingMilieux_MISCELLANEOUS, Complement graph, MathematicsofComputing_DISCRETEMATHEMATICS, Mathematics
Abstract: We consider the exploration of a simple polygon P by a robot that moves from vertex to vertex along edges of the visibility graph of P . The visibility graph has a vertex for every vertex of P and an edge between two vertices if they see each other—that is, if the line segment connecting them lies inside P entirely. While located at a vertex, the robot is capable of ordering the vertices it sees in counterclockwise order as they appear on the boundary, and for every two such vertices, it can distinguish whether the angle between them is convex (⩽ π) or reflex ( > π). Other than that, distant vertices are indistinguishable to the robot. We assume that an upper bound on the number of vertices is known. We obtain the general result that a robot exploring any locally oriented, arc-labeled graph G can always determine the base graph of G . Roughly speaking, this is the smallest graph that cannot be distinguished by a robot from G by its observations alone, no matter how it moves. Combining this result with various other techniques allows the ability to show that a robot exploring a polygon P with the preceding capabilities is always capable of reconstructing the visibility graph of P . We also show that multiple identical, indistinguishable, and deterministic robots of this kind can always solve the weak rendezvous problem in which they need to position themselves such that they mutually see each other—for instance, such that they form a clique in the visibility graph.
Published: 2015
Full Text: View/download PDF

43. A Reliability Theory of Truth

Author: Schlechta, Karl, Laboratoire d'informatique Fondamentale de Marseille (LIF), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), and Schlechta, Karl
Subjects: FOS: Computer and information sciences, [MATH.MATH-LO]Mathematics [math]/Logic [math.LO], Artificial Intelligence (cs.AI), Computer Science - Artificial Intelligence, [MATH.MATH-LO] Mathematics [math]/Logic [math.LO]
Abstract: Our approach is basically a coherence approach, but we avoid the well-known pitfalls of coherence theories of truth. Consistency is replaced by reliability, which expresses support and attack, and, in principle, every theory (or agent, message) counts. At the same time, we do not require a priviledged access to " reality ". A centerpiece of our approach is that we attribute reliability also to agents, messages, etc., so an unreliable source of information will be less important in future. Our ideas can also be extended to value systems, and even actions, e.g., of animals.
Published: 2017

44. Enhancing Security in the Cloud: when Traceability meets Access Control

Author: Clara Bertolissi, Omar Boucelma, Worachet Uttha, Modélisation et Vérification (MOVE), Laboratoire d'Informatique et Systèmes (LIS), Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU), Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU), Nakhon Pathom Rajabhat University, Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'informatique Fondamentale de Marseille ( LIF ), Aix Marseille Université ( AMU ) -Ecole Centrale de Marseille ( ECM ) -Centre National de la Recherche Scientifique ( CNRS ), Laboratoire d'Informatique et Systèmes ( LIS ), and Aix Marseille Université ( AMU ) -Université de Toulon ( UTLN ) -Centre National de la Recherche Scientifique ( CNRS )
Subjects: Traceability, Computer science, [ INFO.INFO-CR ] Computer Science [cs]/Cryptography and Security [cs.CR], Cloud computing, Access control, Computer security, computer.software_genre, 01 natural sciences, GeneralLiterature_MISCELLANEOUS, Data modeling, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], 0505 law, Momentum (technical analysis), [ INFO.INFO-ET ] Computer Science [cs]/Emerging Technologies [cs.ET], 010405 organic chemistry, business.industry, 05 social sciences, 0104 chemical sciences, Categorization, [ INFO.INFO-FL ] Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], Data control, 050501 criminology, Task analysis, [INFO.INFO-ET]Computer Science [cs]/Emerging Technologies [cs.ET], business, computer
Abstract: International audience; —Cloud Computing technology is gaining momentum, however security concerns remain one of the top barrier to cloud projects. We propose a framework that ensures data control and privacy in the cloud by using traceability (aka Provenance) combined with expressive access control policies based on user categorization.
Published: 2017

45. Distance-Preserving Subgraphs of Johnson Graphs

Author: Victor Chepoi, Algorithmique, Combinatoire et Recherche Opérationnelle (ACRO), Laboratoire d'Informatique et Systèmes (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'informatique Fondamentale de Marseille (LIF), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), and Chepoi, Victor
Subjects: [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, Characterization (mathematics), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], 01 natural sciences, Set (abstract data type), Combinatorics, Indifference graph, Cardinality, Chordal graph, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, 0101 mathematics, [MATH.MATH-MG]Mathematics [math]/Metric Geometry [math.MG], ComputingMilieux_MISCELLANEOUS, Mathematics, Discrete mathematics, Johnson graph, 010102 general mathematics, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], Computational Mathematics, 010201 computation theory & mathematics, Embedding, Hypercube, Combinatorics (math.CO)
Abstract: We give a characterization of distance--preserving subgraphs of Johnson graphs, i.e. of graphs which are isometrically embeddable into Johnson graphs (the Johnson graph $J(m,\Lambda)$ has the subsets of cardinality $m$ of a set $\Lambda$ as the vertex--set and two such sets $A,B$ are adjacent iff $|A\triangle B|=2$). Our characterization is similar to the characterization of D. \v{Z}. Djokovi\'c (J. Combin. Th. Ser. B 14 (1973), 263--267) of distance--preserving subgraphs of hypercubes and provides an explicit description of the wallspace (split system) defining the embedding., Comment: 13 pages, 1 figure
Published: 2017
Full Text: View/download PDF

46. Improving Multivariate Time Series Forecasting with Random Walks with Restarts on Causality Graphs

Author: Lotfi Lakhal, Youssef Hmamouche, Piotr Przymus, Alain Casali, Laboratoire d'informatique Fondamentale de Marseille (LIF), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), Laboratoire d'Informatique et Systèmes (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), Data Mining at scale (DANA), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique de Marseille (LIM), Université de la Méditerranée - Aix-Marseille 2-Centre National de la Recherche Scientifique (CNRS), and Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Multivariate statistics, Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 02 engineering and technology, Predictor variables, Machine learning, computer.software_genre, 01 natural sciences, Data modeling, Entropy (classical thermodynamics), 0103 physical sciences, 0202 electrical engineering, electronic engineering, information engineering, Entropy (information theory), Entropy (energy dispersal), Time series, 010306 general physics, Entropy (arrow of time), Economic forecasting, ComputingMilieux_MISCELLANEOUS, [INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB], Artificial neural network, Entropy (statistical thermodynamics), business.industry, Directed graph, Random walk, Causality, [INFO.INFO-IR]Computer Science [cs]/Information Retrieval [cs.IR], 020201 artificial intelligence & image processing, Artificial intelligence, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], business, computer, Entropy (order and disorder)
Abstract: Forecasting models that utilize multiple predictors are gaining popularity in a variety of fields. In some cases they allow constructing more precise forecasting models, leveraging the predictive potential of many variables. Unfortunately, in practice we do not know which observed predictors have a direct impact on the target variable. Moreover, adding unrelated variables may diminish the quality of forecasts. Thus, constructing a set of predictor variables that can be used in a forecast model is one of the greatest challenges in forecasting. We propose a new selection model for predictor variables based on the directed causality graph and a modification of the random walk with restarts model. Experiments conducted using the two popular macroeconomics sets, from the US and Australia, show that this simple and scalable approach performs well compared to other well established methods.
Published: 2017
Full Text: View/download PDF

47. Arithmetic in finite fields based on the Chudnovsky-Chudnovsky multiplication algorithm

Author: Kevin Atighehchi, Stéphane Ballet, Alexis Bonnecaze, Robert Rolland, Laboratoire d'informatique Fondamentale de Marseille (LIF), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), Institut de Mathématiques de Marseille (I2M), and Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU)
Subjects: Multiplication algorithm, Exponentiation, Computation, F-Q, Bilinear interpolation, ALGEBRAIC FUNCTION-FIELDS, 010103 numerical & computational mathematics, DIVISORS, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 12Y05, 01 natural sciences, EXTENSIONS, 0101 mathematics, Mathematics, Discrete mathematics, Algebra and Number Theory, Efficient algorithm, Applied Mathematics, EXPONENTIATION, 010102 general mathematics, EXISTENCE, Algebra, Computational Mathematics, Finite field, Multiplication, [MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG], Knuth's up-arrow notation
Abstract: International audience; Thanks to a new construction of the so-called Chudnovsky-Chudnovsky multiplication algorithm, we design efficient algorithms for both the exponentiation and the multiplication in finite fields. They are tailored to hardware implementation and they allow computations to be parallelized while maintaining a low number of bilinear multiplications. We give an example with the finite field ${\mathbb F}_{16^{13}}$.
Published: 2017
Full Text: View/download PDF

48. Multidimensional skyline analysis based on agree concept lattices

Author: Lotfi Lakhal, Rosine Cicchetti, Sébastien Nedjar, Laboratoire d'informatique Fondamentale de Marseille (LIF), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), Laboratoire d'Informatique et Systèmes (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), Data Mining at scale (DANA), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'informatique Fondamentale de Marseille - UMR 6166 (LIF), Université de la Méditerranée - Aix-Marseille 2-Université de Provence - Aix-Marseille 1-Centre National de la Recherche Scientifique (CNRS), and Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Skyline, [INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB], Computer science, 02 engineering and technology, computer.software_genre, Theoretical Computer Science, Artificial Intelligence, 020204 information systems, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, [INFO]Computer Science [cs], Computer Vision and Pattern Recognition, Data mining, computer, ComputingMilieux_MISCELLANEOUS
Abstract: International audience
Published: 2017
Full Text: View/download PDF

49. Which Broadcast Abstraction Captures k-Set Agreement?

Author: Imbs, Damien, Mostefaoui, Achour, Perrin, Matthieu, Raynal, Michel, Laboratoire d'informatique Fondamentale de Marseille (LIF), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), Algorithmique Distribuée (DALGO), Laboratoire d'Informatique et Systèmes (LIS), Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU), Laboratoire des Sciences du Numérique de Nantes (LS2N), Université de Nantes - UFR des Sciences et des Techniques (UN UFR ST), Université de Nantes (UN)-Université de Nantes (UN)-École Centrale de Nantes (ECN)-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), As Scalable As Possible: foundations of large scale dynamic distributed systems (ASAP), SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Bretagne Sud (UBS)-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)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria), Andréa W. Richa, ANR-16-CE40-0023,DESCARTES,Abstraction modulaire pour le calcul distribué(2016), ANR-14-CE35-0010,DISCMAT,Mathematical Methods in Distributed Computing(2014), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), Université de Nantes (UN)-Université de Nantes (UN)-École Centrale de Nantes (ECN)-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Gestion de Données Distribuées (LS2N - équipe GDD), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Nantes - UFR des Sciences et des Techniques (UN UFR ST), Laboratoire Géomatique et foncier (GeF), Conservatoire National des Arts et Métiers [CNAM] (CNAM), HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)-HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM), Gestion de Données Distribuées (GDD), 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)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes 1 (UR1), and Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique)
Subjects: FOS: Computer and information sciences, Partially ordered set, 000 Computer science, knowledge, general works, Consensus, [INFO.INFO-CE]Computer Science [cs]/Computational Engineering, Finance, and Science [cs.CE], Agreement problem, Antichain, Message-passing system, Communication abstraction, Computer Science - Distributed, Parallel, and Cluster Computing, Computer Science, Distributed, Parallel, and Cluster Computing (cs.DC), Asynchronous system, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Process crash
Abstract: International audience; It is well-known that consensus (one-set agreement) and total order broadcast are equivalent in asynchronous systems prone to process crash failures. Considering wait-free systems, this article addresses and answers the following question: which is the communication abstraction that "captures" k-set agreement? To this end, it introduces a new broadcast communication abstraction, called k-BO-Broadcast, which restricts the disagreement on the local deliveries of the messages that have been broadcast (1-BO-Broadcast boils down to total order broadcast). Hence, in this context, k=1 is not a special number, but only the first integer in an increasing integer sequence. This establishes a new "correspondence" between distributed agreement problems and communication abstractions, which enriches our understanding of the relations linking fundamental issues of fault-tolerant distributed computing.
Published: 2017
Full Text: View/download PDF

50. A Meta-Learning Approach to One-Step Active-Learning

Author: Gabriella Contardo, Denoyer, L., Artieres, T., Machine Learning and Information Access (MLIA), 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 Fondamentale de Marseille (LIF), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), éQuipe AppRentissage et MultimediA [Marseille] (QARMA), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU)-Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), and Artières, Thierry
Subjects: [INFO.INFO-AI] Computer Science [cs]/Artificial Intelligence [cs.AI], [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], Budget Learning, [INFO.INFO-NE] Computer Science [cs]/Neural and Evolutionary Computing [cs.NE], [INFO.INFO-LG] Computer Science [cs]/Machine Learning [cs.LG], [INFO.INFO-NE]Computer Science [cs]/Neural and Evolutionary Computing [cs.NE], [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Abstract: International audience; We consider the problem of learning when obtaining the training labels is costly, which is usually tackled in the literature using active-learning techniques. These approaches provide strategies to choose the examples to label before or during training. These strategies are usually based on heuristics or even theoretical measures, but are not learned as they are directly used during training. We design a model which aims at learning active-learning strategies using a meta-learning setting. More specifically, we consider a pool-based setting, where the system observes all the examples of the dataset of a problem and has to choose the subset of examples to label in a single shot. Experiments show encouraging results.
Published: 2017

Catalog

Books, media, physical & digital resources

See catalog results

Searchworks

Select search scope, currently: Articles Catalog books, media & more in Jio Institute collections Articles journal articles & other e-resources

Search

Search Constraints

Refine your results

Search Limiters

Topic

Publication Year Range

Language

Journal

Database

Publisher

633 results on '"Laboratoire d'informatique Fondamentale de Marseille (LIF)"'

Search Results

Catalog

Select search scope, currently: Articles

Catalog

books, media & more in Jio Institute collections

Articles

journal articles & other e-resources