5 Search Results for "Meunier, No�mie"

Document
DOI: 10.4230/LIPIcs.DNA.2020.9
scadnano: A Browser-Based, Scriptable Tool for Designing DNA Nanostructures

Authors: David Doty, Benjamin L Lee, and Tristan Stérin

Published in: LIPIcs, Volume 174, 26th International Conference on DNA Computing and Molecular Programming (DNA 26) (2020)

Abstract
We introduce scadnano (short for "scriptable cadnano"), a computational tool for designing synthetic DNA structures. Its design is based heavily on cadnano [Douglas et al., 2009], the most widely-used software for designing DNA origami [Paul W. K. Rothemund, 2006], with three main differences: 1) scadnano runs entirely in the browser, with no software installation required. 2) scadnano designs, while they can be edited manually, can also be created and edited by a well-documented Python scripting library, to help automate tedious tasks. 3) The scadnano file format is easily human-readable. This goal is closely aligned with the scripting library, intended to be helpful when debugging scripts or interfacing with other software. The format is also somewhat more expressive than that of cadnano, able to describe a broader range of DNA structures than just DNA origami.
Cite as

David Doty, Benjamin L Lee, and Tristan Stérin. scadnano: A Browser-Based, Scriptable Tool for Designing DNA Nanostructures. In 26th International Conference on DNA Computing and Molecular Programming (DNA 26). Leibniz International Proceedings in Informatics (LIPIcs), Volume 174, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{doty_et_al:LIPIcs.DNA.2020.9,
  author =	{Doty, David and Lee, Benjamin L and St\'{e}rin, Tristan},
  title =	{{scadnano: A Browser-Based, Scriptable Tool for Designing DNA Nanostructures}},
  booktitle =	{26th International Conference on DNA Computing and Molecular Programming (DNA 26)},
  pages =	{9:1--9:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-163-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{174},
  editor =	{Geary, Cody and Patitz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.2020.9},
  URN =		{urn:nbn:de:0030-drops-129624},
  doi =		{10.4230/LIPIcs.DNA.2020.9},
  annote =	{Keywords: computer-aided design, structural DNA nanotechnology, DNA origami}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.31
No-Dimensional Tverberg Theorems and Algorithms

Authors: Aruni Choudhary and Wolfgang Mulzer

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
Tverberg’s theorem states that for any k ≥ 2 and any set P ⊂ ℝ^d of at least (d + 1)(k - 1) + 1 points, we can partition P into k subsets whose convex hulls have a non-empty intersection. The associated search problem lies in the complexity class PPAD ∩ PLS, but no hardness results are known. In the colorful Tverberg theorem, the points in P have colors, and under certain conditions, P can be partitioned into colorful sets, in which each color appears exactly once and whose convex hulls intersect. To date, the complexity of the associated search problem is unresolved. Recently, Adiprasito, Bárány, and Mustafa [SODA 2019] gave a no-dimensional Tverberg theorem, in which the convex hulls may intersect in an approximate fashion. This relaxes the requirement on the cardinality of P. The argument is constructive, but does not result in a polynomial-time algorithm. We present a deterministic algorithm that finds for any n-point set P ⊂ ℝ^d and any k ∈ {2, … , n} in O(nd ⌈log k⌉) time a k-partition of P such that there is a ball of radius O((k/√n)diam(P)) that intersects the convex hull of each set. Given that this problem is not known to be solvable exactly in polynomial time, and that there are no approximation algorithms that are truly polynomial in any dimension, our result provides a remarkably efficient and simple new notion of approximation. Our main contribution is to generalize Sarkaria’s method [Israel Journal Math., 1992] to reduce the Tverberg problem to the Colorful Carathéodory problem (in the simplified tensor product interpretation of Bárány and Onn) and to apply it algorithmically. It turns out that this not only leads to an alternative algorithmic proof of a no-dimensional Tverberg theorem, but it also generalizes to other settings such as the colorful variant of the problem.
Cite as

Aruni Choudhary and Wolfgang Mulzer. No-Dimensional Tverberg Theorems and Algorithms. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 31:1-31:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{choudhary_et_al:LIPIcs.SoCG.2020.31,
  author =	{Choudhary, Aruni and Mulzer, Wolfgang},
  title =	{{No-Dimensional Tverberg Theorems and Algorithms}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{31:1--31:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.31},
  URN =		{urn:nbn:de:0030-drops-121893},
  doi =		{10.4230/LIPIcs.SoCG.2020.31},
  annote =	{Keywords: Tverberg’s theorem, Colorful Carath\'{e}odory Theorem, Tensor lifting}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.23
Proving the Turing Universality of Oritatami Co-Transcriptional Folding

Authors: Cody Geary, Pierre-Étienne Meunier, Nicolas Schabanel, and Shinnosuke Seki

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
We study the oritatami model for molecular co-transcriptional folding. In oritatami systems, the transcript (the "molecule") folds as it is synthesized (transcribed), according to a local energy optimisation process, which is similar to how actual biomolecules such as RNA fold into complex shapes and functions as they are transcribed. We prove that there is an oritatami system embedding universal computation in the folding process itself. Our result relies on the development of a generic toolbox, which is easily reusable for future work to design complex functions in oritatami systems. We develop "low-level" tools that allow to easily spread apart the encoding of different "functions" in the transcript, even if they are required to be applied at the same geometrical location in the folding. We build upon these low-level tools, a programming framework with increasing levels of abstraction, from encoding of instructions into the transcript to logical analysis. This framework is similar to the hardware-to-algorithm levels of abstractions in standard algorithm theory. These various levels of abstractions allow to separate the proof of correctness of the global behavior of our system, from the proof of correctness of its implementation. Thanks to this framework, we were able to computerise the proof of correctness of its implementation and produce certificates, in the form of a relatively small number of proof trees, compact and easily readable/checkable by human, while encapsulating huge case enumerations. We believe this particular type of certificates can be generalised to other discrete dynamical systems, where proofs involve large case enumerations as well.
Cite as

Cody Geary, Pierre-Étienne Meunier, Nicolas Schabanel, and Shinnosuke Seki. Proving the Turing Universality of Oritatami Co-Transcriptional Folding. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 23:1-23:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{geary_et_al:LIPIcs.ISAAC.2018.23,
  author =	{Geary, Cody and Meunier, Pierre-\'{E}tienne and Schabanel, Nicolas and Seki, Shinnosuke},
  title =	{{Proving the Turing Universality of Oritatami Co-Transcriptional Folding}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{23:1--23:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.23},
  URN =		{urn:nbn:de:0030-drops-99715},
  doi =		{10.4230/LIPIcs.ISAAC.2018.23},
  annote =	{Keywords: Molecular computing, Turing universality, co-transcriptional folding}
}
Document
DOI: 10.4230/LIPIcs.CSL.2015.504
Weak Subgame Perfect Equilibria and their Application to Quantitative Reachability

Authors: Thomas Brihaye, Véronique Bruyère, Noémie Meunier, and Jean-Francois Raskin

Published in: LIPIcs, Volume 41, 24th EACSL Annual Conference on Computer Science Logic (CSL 2015)

Abstract
We study n-player turn-based games played on a finite directed graph. For each play, the players have to pay a cost that they want to minimize. Instead of the well-known notion of Nash equilibrium (NE), we focus on the notion of subgame perfect equilibrium (SPE), a refinement of NE well-suited in the framework of games played on graphs. We also study natural variants of SPE, named weak (resp. very weak) SPE, where players who deviate cannot use the full class of strategies but only a subclass with a finite number of (resp. a unique) deviation step(s). Our results are threefold. Firstly, we characterize in the form of a Folk theorem the set of all plays that are the outcome of a weak SPE. Secondly, for the class of quantitative reachability games, we prove the existence of a finite-memory SPE and provide an algorithm for computing it (only existence was known with no information regarding the memory). Moreover, we show that the existence of a constrained SPE, i.e. an SPE such that each player pays a cost less than a given constant, can be decided. The proofs rely on our Folk theorem for weak SPEs (which coincide with SPEs in the case of quantitative reachability games) and on the decidability of MSO logic on infinite words. Finally with similar techniques, we provide a second general class of games for which the existence of a (constrained) weak SPE is decidable.
Cite as

Thomas Brihaye, Véronique Bruyère, Noémie Meunier, and Jean-Francois Raskin. Weak Subgame Perfect Equilibria and their Application to Quantitative Reachability. In 24th EACSL Annual Conference on Computer Science Logic (CSL 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 41, pp. 504-518, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{brihaye_et_al:LIPIcs.CSL.2015.504,
  author =	{Brihaye, Thomas and Bruy\`{e}re, V\'{e}ronique and Meunier, No\'{e}mie and Raskin, Jean-Francois},
  title =	{{Weak Subgame Perfect Equilibria and their Application to Quantitative Reachability}},
  booktitle =	{24th EACSL Annual Conference on Computer Science Logic (CSL 2015)},
  pages =	{504--518},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-90-3},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{41},
  editor =	{Kreutzer, Stephan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2015.504},
  URN =		{urn:nbn:de:0030-drops-54345},
  doi =		{10.4230/LIPIcs.CSL.2015.504},
  annote =	{Keywords: multi-player games on graphs, quantitative objectives, Nash equilibrium, subgame perfect equilibrium, quantitative reachability}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2014.34
Online Train Shunting

Authors: Vianney Boeuf and Frédéric Meunier

Published in: OASIcs, Volume 42, 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2014)

Abstract
At the occasion of ATMOS 2012, Tim Nonner and Alexander Souza defined a new train shunting problem that can roughly be described as follows. We are given a train visiting stations in a given order and cars located at some source stations. Each car has a target station. During the trip of the train, the cars are added to the train at their source stations and removed from it at their target stations. An addition or a removal of a car in the strict interior of the train incurs a cost higher than when the operation is performed at the end of the train. The problem consists in minimizing the total cost, and thus, at each source station of a car, the position the car takes in the train must be carefully decided. Among other results, Nonner and Souza showed that this problem is polynomially solvable by reducing the problem to the computation of a minimum independent set in a bipartite graph. They worked in the offline setting, i.e. the sources and the targets of all cars are known before the trip of the train starts. We study the online version of the problem, in which cars become known at their source stations. We derive a 2-competitive algorithm and prove than no better ratios are achievable. Other related questions are also addressed.
Cite as

Vianney Boeuf and Frédéric Meunier. Online Train Shunting. In 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 42, pp. 34-45, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{boeuf_et_al:OASIcs.ATMOS.2014.34,
  author =	{Boeuf, Vianney and Meunier, Fr\'{e}d\'{e}ric},
  title =	{{Online Train Shunting}},
  booktitle =	{14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{34--45},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-75-0},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{42},
  editor =	{Funke, Stefan and Mihal\'{a}k, Mat\'{u}s},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2014.34},
  URN =		{urn:nbn:de:0030-drops-47512},
  doi =		{10.4230/OASIcs.ATMOS.2014.34},
  annote =	{Keywords: Bipartite graph, competitive analysis, online algorithm, train shunting problem, vertex cover}
}
  • Refine by Author
  • 1 Boeuf, Vianney
  • 1 Brihaye, Thomas
  • 1 Bruyère, Véronique
  • 1 Choudhary, Aruni
  • 1 Doty, David
  • Show More...

  • Refine by Classification
  • 1 Applied computing → Computer-aided design
  • 1 Applied computing → Life and medical sciences
  • 1 Hardware → Biology-related information processing
  • 1 Theory of computation → Computational geometry
  • 1 Theory of computation → Graph algorithms analysis
  • Show More...

  • Refine by Keyword
  • 1 Bipartite graph
  • 1 Colorful Carathéodory Theorem
  • 1 DNA origami
  • 1 Molecular computing
  • 1 Nash equilibrium
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 2 2020
  • 1 2014
  • 1 2015
  • 1 2018

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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact