4 Search Results for "Schmidt, Michael"

Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2020.73
Space Ants: Constructing and Reconfiguring Large-Scale Structures with Finite Automata (Media Exposition)

Authors: Amira Abdel-Rahman, Aaron T. Becker, Daniel E. Biediger, Kenneth C. Cheung, Sándor P. Fekete, Neil A. Gershenfeld, Sabrina Hugo, Benjamin Jenett, Phillip Keldenich, Eike Niehs, Christian Rieck, Arne Schmidt, Christian Scheffer, and Michael Yannuzzi

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

Abstract
In this video, we consider recognition and reconfiguration of lattice-based cellular structures by very simple robots with only basic functionality. The underlying motivation is the construction and modification of space facilities of enormous dimensions, where the combination of new materials with extremely simple robots promises structures of previously unthinkable size and flexibility. We present algorithmic methods that are able to detect and reconfigure arbitrary polyominoes, based on finite-state robots, while also preserving connectivity of a structure during reconfiguration. Specific results include methods for determining a bounding box, scaling a given arrangement, and adapting more general algorithms for transforming polyominoes.
Cite as

Amira Abdel-Rahman, Aaron T. Becker, Daniel E. Biediger, Kenneth C. Cheung, Sándor P. Fekete, Neil A. Gershenfeld, Sabrina Hugo, Benjamin Jenett, Phillip Keldenich, Eike Niehs, Christian Rieck, Arne Schmidt, Christian Scheffer, and Michael Yannuzzi. Space Ants: Constructing and Reconfiguring Large-Scale Structures with Finite Automata (Media Exposition). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 73:1-73:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{abdelrahman_et_al:LIPIcs.SoCG.2020.73,
  author =	{Abdel-Rahman, Amira and Becker, Aaron T. and Biediger, Daniel E. and Cheung, Kenneth C. and Fekete, S\'{a}ndor P. and Gershenfeld, Neil A. and Hugo, Sabrina and Jenett, Benjamin and Keldenich, Phillip and Niehs, Eike and Rieck, Christian and Schmidt, Arne and Scheffer, Christian and Yannuzzi, Michael},
  title =	{{Space Ants: Constructing and Reconfiguring Large-Scale Structures with Finite Automata}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{73:1--73:6},
  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.73},
  URN =		{urn:nbn:de:0030-drops-122310},
  doi =		{10.4230/LIPIcs.SoCG.2020.73},
  annote =	{Keywords: Finite automata, reconfiguration, construction, scaling}
}
Document
DOI: 10.4230/OASIcs.WCET.2018.8
Embedded Program Annotations for WCET Analysis

Authors: Bernhard Schommer, Christoph Cullmann, Gernot Gebhard, Xavier Leroy, Michael Schmidt, and Simon Wegener

Published in: OASIcs, Volume 63, 18th International Workshop on Worst-Case Execution Time Analysis (WCET 2018)

Abstract
We present __builtin_ais_annot(), a user-friendly, versatile way to transfer annotations (also known as flow facts) written on the source code level to the machine code level. To do so, we couple two tools often used during the development of safety-critical hard real-time systems, the formally verified C compiler CompCert and the static WCET analyzer aiT. CompCert stores the AIS annotations given via __builtin_ais_annot() in a special section of the ELF binary, which can later be extracted automatically by aiT.
Cite as

Bernhard Schommer, Christoph Cullmann, Gernot Gebhard, Xavier Leroy, Michael Schmidt, and Simon Wegener. Embedded Program Annotations for WCET Analysis. In 18th International Workshop on Worst-Case Execution Time Analysis (WCET 2018). Open Access Series in Informatics (OASIcs), Volume 63, pp. 8:1-8:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{schommer_et_al:OASIcs.WCET.2018.8,
  author =	{Schommer, Bernhard and Cullmann, Christoph and Gebhard, Gernot and Leroy, Xavier and Schmidt, Michael and Wegener, Simon},
  title =	{{Embedded Program Annotations for WCET Analysis}},
  booktitle =	{18th International Workshop on Worst-Case Execution Time Analysis (WCET 2018)},
  pages =	{8:1--8:13},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-073-6},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{63},
  editor =	{Brandner, Florian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2018.8},
  URN =		{urn:nbn:de:0030-drops-97543},
  doi =		{10.4230/OASIcs.WCET.2018.8},
  annote =	{Keywords: Worst-Case Execution Time (WCET) Analysis, Annotation Support, CompCert, Tool Coupling, aiT}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.66
Approximation Algorithms for Aversion k-Clustering via Local k-Median

Authors: Anupam Gupta, Guru Guruganesh, and Melanie Schmidt

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
In the aversion k-clustering problem, given a metric space, we want to cluster the points into k clusters. The cost incurred by each point is the distance to the furthest point in its cluster, and the cost of the clustering is the sum of all these per-point-costs. This problem is motivated by questions in generating automatic abstractions of extensive-form games. We reduce this problem to a "local" k-median problem where each facility has a prescribed radius and can only connect to clients within that radius. Our main results is a constant-factor approximation algorithm for the aversion k-clustering problem via the local k-median problem. We use a primal-dual approach; our technical contribution is a non-local rounding step which we feel is of broader interest.
Cite as

Anupam Gupta, Guru Guruganesh, and Melanie Schmidt. Approximation Algorithms for Aversion k-Clustering via Local k-Median. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 66:1-66:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{gupta_et_al:LIPIcs.ICALP.2016.66,
  author =	{Gupta, Anupam and Guruganesh, Guru and Schmidt, Melanie},
  title =	{{Approximation Algorithms for Aversion k-Clustering via Local k-Median}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{66:1--66:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.66},
  URN =		{urn:nbn:de:0030-drops-62180},
  doi =		{10.4230/LIPIcs.ICALP.2016.66},
  annote =	{Keywords: Approximation algorithms, clustering, k-median, primal-dual}
}
Document
DOI: 10.4230/DagSemProc.09391.5
Weighted L_2 B Discrepancy and Approximation of Integrals over Reproducing Kernel Hilbert Spaces

Authors: Michael Gnewuch

Published in: Dagstuhl Seminar Proceedings, Volume 9391, Algorithms and Complexity for Continuous Problems (2009)

Abstract
We extend the notion of $L_2$ $B$ discrepancy provided in [E. Novak, H. Wo'zniakowski, $L_2$ discrepancy and multivariate integration, in: Analytic number theory. Essays in honour of Klaus Roth. W. W. L. Chen, W. T. Gowers, H. Halberstam, W. M. Schmidt, and R. C. Vaughan (Eds.), Cambridge University Press, Cambridge, 2009, 359 – 388] to the weighted $L_2$ $mathcal{B}$ discrepancy. This newly defined notion allows to consider weights, but also volume measures different from the Lebesgue measure and classes of test sets different from measurable subsets of some Euclidean space. We relate the weighted $L_2$ $mathcal{B}$ discrepancy to numerical integration defined over weighted reproducing kernel Hilbert spaces and settle in this way an open problem posed by Novak and Wo'zniakowski.
Cite as

Michael Gnewuch. Weighted L_2 B Discrepancy and Approximation of Integrals over Reproducing Kernel Hilbert Spaces. In Algorithms and Complexity for Continuous Problems. Dagstuhl Seminar Proceedings, Volume 9391, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{gnewuch:DagSemProc.09391.5,
  author =	{Gnewuch, Michael},
  title =	{{Weighted L\underline2 B Discrepancy and Approximation of Integrals over Reproducing Kernel Hilbert Spaces}},
  booktitle =	{Algorithms and Complexity for Continuous Problems},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9391},
  editor =	{Thomas M\"{u}ller-Gronbach and Leszek Plaskota and Joseph. F. Traub},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09391.5},
  URN =		{urn:nbn:de:0030-drops-22966},
  doi =		{10.4230/DagSemProc.09391.5},
  annote =	{Keywords: Discrepancy, Numerical Integration, Quasi-Monte Carlo, Reproducing Kernel Hilbert Space}
}
  • Refine by Author
  • 1 Abdel-Rahman, Amira
  • 1 Becker, Aaron T.
  • 1 Biediger, Daniel E.
  • 1 Cheung, Kenneth C.
  • 1 Cullmann, Christoph
  • Show More...

  • Refine by Classification
  • 1 Computer systems organization → Real-time systems
  • 1 Hardware → Static timing analysis
  • 1 Software and its engineering → Automated static analysis
  • 1 Software and its engineering → Compilers
  • 1 Software and its engineering → Embedded software
  • Show More...

  • Refine by Keyword
  • 1 Annotation Support
  • 1 Approximation algorithms
  • 1 CompCert
  • 1 Discrepancy
  • 1 Finite automata
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2009
  • 1 2016
  • 1 2018
  • 1 2020

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