4 Search Results for "Richard, Ga�tan"


Document
Distance Queries over Dynamic Interval Graphs

Authors: Jingbang Chen, Meng He, J. Ian Munro, Richard Peng, Kaiyu Wu, and Daniel J. Zhang

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)


Abstract
We design the first dynamic distance oracles for interval graphs, which are intersection graphs of a set of intervals on the real line, and for proper interval graphs, which are intersection graphs of a set of intervals in which no interval is properly contained in another. For proper interval graphs, we design a linear space data structure which supports distance queries (computing the distance between two query vertices) and vertex insertion or deletion in O(lg n) worst-case time, where n is the number of vertices currently in G. Under incremental (insertion only) or decremental (deletion only) settings, we design linear space data structures that support distance queries in O(lg n) worst-case time and vertex insertion or deletion in O(lg n) amortized time, where n is the maximum number of vertices in the graph. Under fully dynamic settings, we design a data structure that represents an interval graph G in O(n) words of space to support distance queries in O(n lg n/S(n)) worst-case time and vertex insertion or deletion in O(S(n)+lg n) worst-case time, where n is the number of vertices currently in G and S(n) is an arbitrary function that satisfies S(n) = Ω(1) and S(n) = O(n). This implies an O(n)-word solution with O(√{nlg n})-time support for both distance queries and updates. All four data structures can answer shortest path queries by reporting the vertices in the shortest path between two query vertices in O(lg n) worst-case time per vertex. We also study the hardness of supporting distance queries under updates over an intersection graph of 3D axis-aligned line segments, which generalizes our problem to 3D. Finally, we solve the problem of computing the diameter of a dynamic connected interval graph.

Cite as

Jingbang Chen, Meng He, J. Ian Munro, Richard Peng, Kaiyu Wu, and Daniel J. Zhang. Distance Queries over Dynamic Interval Graphs. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 18:1-18:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ISAAC.2023.18,
  author =	{Chen, Jingbang and He, Meng and Munro, J. Ian and Peng, Richard and Wu, Kaiyu and Zhang, Daniel J.},
  title =	{{Distance Queries over Dynamic Interval Graphs}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{18:1--18:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.18},
  URN =		{urn:nbn:de:0030-drops-193207},
  doi =		{10.4230/LIPIcs.ISAAC.2023.18},
  annote =	{Keywords: interval graph, proper interval graph, intersection graph, geometric intersection graph, distance oracle, distance query, shortest path query, dynamic graph}
}
Document
On the Synchronisation Problem over Cellular Automata

Authors: Gaétan Richard

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)


Abstract
Cellular automata are a discrete, synchronous, and uniform dynamical system that give rise to a wide range of dynamical behaviours. In this paper, we investigate whether this system can achieve synchronisation. We study the cases of classical bi-infinite configurations, periodic configurations, and periodic configurations of prime period. In the two former cases, we prove that only a "degenerated" form of synchronisation - there exists a fix-point - is possible. In the latter case, we give an explicit construction of a cellular automaton for which any periodic configuration of prime period eventually converges to cycle of two uniform configurations. Our construction is based upon sophisticated tools: aperiodic NW-deterministic tilings and partitioned intervals.

Cite as

Gaétan Richard. On the Synchronisation Problem over Cellular Automata. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 54:1-54:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{richard:LIPIcs.STACS.2017.54,
  author =	{Richard, Ga\'{e}tan},
  title =	{{On the Synchronisation Problem over Cellular Automata}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{54:1--54:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.54},
  URN =		{urn:nbn:de:0030-drops-69780},
  doi =		{10.4230/LIPIcs.STACS.2017.54},
  annote =	{Keywords: cellular automata, dynamical systems, aperiodic tiling, synchronisation}
}
Document
Fusion of Multimodal Information in Music Content Analysis

Authors: Slim Essid and Gaël Richard

Published in: Dagstuhl Follow-Ups, Volume 3, Multimodal Music Processing (2012)


Abstract
Music is often processed through its acoustic realization. This is restrictive in the sense that music is clearly a highly multimodal concept where various types of heterogeneous information can be associated to a given piece of music (a musical score, musicians' gestures, lyrics, user-generated metadata, etc.). This has recently led researchers to apprehend music through its various facets, giving rise to "multimodal music analysis" studies. This article gives a synthetic overview of methods that have been successfully employed in multimodal signal analysis. In particular, their use in music content processing is discussed in more details through five case studies that highlight different multimodal integration techniques. The case studies include an example of cross-modal correlation for music video analysis, an audiovisual drum transcription system, a description of the concept of informed source separation, a discussion of multimodal dance-scene analysis, and an example of user-interactive music analysis. In the light of these case studies, some perspectives of multimodality in music processing are finally suggested.

Cite as

Slim Essid and Gaël Richard. Fusion of Multimodal Information in Music Content Analysis. In Multimodal Music Processing. Dagstuhl Follow-Ups, Volume 3, pp. 37-52, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)


Copy BibTex To Clipboard

@InCollection{essid_et_al:DFU.Vol3.11041.37,
  author =	{Essid, Slim and Richard, Ga\"{e}l},
  title =	{{Fusion of Multimodal Information in Music Content Analysis}},
  booktitle =	{Multimodal Music Processing},
  pages =	{37--52},
  series =	{Dagstuhl Follow-Ups},
  ISBN =	{978-3-939897-37-8},
  ISSN =	{1868-8977},
  year =	{2012},
  volume =	{3},
  editor =	{M\"{u}ller, Meinard and Goto, Masataka and Schedl, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DFU.Vol3.11041.37},
  URN =		{urn:nbn:de:0030-drops-34652},
  doi =		{10.4230/DFU.Vol3.11041.37},
  annote =	{Keywords: Multimodal music processing, music signals indexing and transcription, information fusion, audio, video}
}
Document
Revisiting the Rice Theorem of Cellular Automata

Authors: Pierre Guillon and Gaétan Richard

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)


Abstract
A cellular automaton is a parallel synchronous computing model, which consists in a juxtaposition of finite automata whose state evolves according to that of their neighbors. It induces a dynamical system on the set of configurations, \ie the infinite sequences of cell states. The limit set of the cellular automaton is the set of configurations which can be reached arbitrarily late in the evolution. In this paper, we prove that all properties of limit sets of cellular automata with binary-state cells are undecidable, except surjectivity. This is a refinement of the classical ``Rice Theorem'' that Kari proved on cellular automata with arbitrary state sets.

Cite as

Pierre Guillon and Gaétan Richard. Revisiting the Rice Theorem of Cellular Automata. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 441-452, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{guillon_et_al:LIPIcs.STACS.2010.2474,
  author =	{Guillon, Pierre and Richard, Ga\'{e}tan},
  title =	{{Revisiting the Rice Theorem of Cellular Automata}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{441--452},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2474},
  URN =		{urn:nbn:de:0030-drops-24744},
  doi =		{10.4230/LIPIcs.STACS.2010.2474},
  annote =	{Keywords: Cellular automata, undecidability}
}
  • Refine by Author
  • 2 Richard, Gaétan
  • 1 Chen, Jingbang
  • 1 Essid, Slim
  • 1 Guillon, Pierre
  • 1 He, Meng
  • Show More...

  • Refine by Classification
  • 1 Information systems → Data structures
  • 1 Theory of computation → Data structures design and analysis

  • Refine by Keyword
  • 1 Cellular automata
  • 1 Multimodal music processing
  • 1 aperiodic tiling
  • 1 audio
  • 1 cellular automata
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2010
  • 1 2012
  • 1 2017
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail