42 Search Results for "Becker, J�rgen"

Document
DOI: 10.4230/DagRep.13.2.183
Algorithmic Foundations of Programmable Matter (Dagstuhl Seminar 23091)

Authors: Aaron Becker, Sándor Fekete, Irina Kostitsyna, Matthew J. Patitz, Damien Woods, and Ioannis Chatzigiannakis

Published in: Dagstuhl Reports, Volume 13, Issue 2 (2023)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 23091, "Algorithmic Foundations of Programmable Matter", a new and emerging field that combines theoretical work on algorithms with a wide spectrum of practical applications that reach all the way from small-scale embedded systems to cyber-physical structures at nano-scale. The aim of this seminar was to bring together researchers from computational geometry, distributed computing, DNA computing, and swarm robotics who have worked on programmable matter to inform one another about the newest developments in each area and to discuss future models, approaches, and directions for new research. Similar to the first two Dagstuhl Seminars on programmable matter (16271 and 18331), we did focus on some basic problems, but also considered new problems that were now within reach to be studied.
Cite as

Aaron Becker, Sándor Fekete, Irina Kostitsyna, Matthew J. Patitz, Damien Woods, and Ioannis Chatzigiannakis. Algorithmic Foundations of Programmable Matter (Dagstuhl Seminar 23091). In Dagstuhl Reports, Volume 13, Issue 2, pp. 183-198, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{becker_et_al:DagRep.13.2.183,
  author =	{Becker, Aaron and Fekete, S\'{a}ndor and Kostitsyna, Irina and Patitz, Matthew J. and Woods, Damien and Chatzigiannakis, Ioannis},
  title =	{{Algorithmic Foundations of Programmable Matter (Dagstuhl Seminar 23091)}},
  pages =	{183--198},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2023},
  volume =	{13},
  number =	{2},
  editor =	{Becker, Aaron and Fekete, S\'{a}ndor and Kostitsyna, Irina and Patitz, Matthew J. and Woods, Damien and Chatzigiannakis, Ioannis},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.13.2.183},
  URN =		{urn:nbn:de:0030-drops-191848},
  doi =		{10.4230/DagRep.13.2.183},
  annote =	{Keywords: computational geometry, distributed algorithms, DNA computing, programmable matter, swarm robotics}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.15
Sorting Finite Automata via Partition Refinement

Authors: Ruben Becker, Manuel Cáceres, Davide Cenzato, Sung-Hwan Kim, Bojana Kodric, Francisco Olivares, and Nicola Prezza

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
Wheeler nondeterministic finite automata (WNFAs) were introduced in (Gagie et al., TCS 2017) as a powerful generalization of prefix sorting from strings to labeled graphs. WNFAs admit optimal solutions to classic hard problems on labeled graphs and languages such as compression and regular expression matching. The problem of deciding whether a given NFA is Wheeler is known to be NP-complete (Gibney and Thankachan, ESA 2019). Recently, however, Alanko et al. (Information and Computation 2021) showed how to side-step this complexity by switching to preorders: letting Q be the set of states and δ the set of transitions, they provided a O(|δ|⋅|Q|²)-time algorithm computing a totally-ordered partition (i.e. equivalence relation) of the WNFA’s states such that (1) equivalent states recognize the same regular language, and (2) the order of (the classes of) non-equivalent states is consistent with any Wheeler order, when one exists. As a result, the output is a preorder of the states as useful for pattern matching as standard Wheeler orders. Further extensions of this line of work (Cotumaccio et al., SODA 2021 and DCC 2022) generalized these concepts to arbitrary NFAs by introducing co-lex partial preorders: in general, any NFA admits a partial preorder of its states reflecting the co-lexicographic order of their accepted strings; the smaller the width of such preorder is, the faster regular expression matching queries can be performed. To date, the fastest algorithm for computing the smallest-width partial preorder on NFAs runs in O(|δ|² + |Q|^{5/2}) time (Cotumaccio, DCC 2022), while on DFAs the same task can be accomplished in O(min(|Q|²log|Q|, |δ|⋅|Q|)) time (Kim et al., CPM 2023). In this paper, we provide much more efficient solutions to the co-lex order computation problem. Our results are achieved by extending a classic algorithm for the relational coarsest partition refinement problem of Paige and Tarjan to work with ordered partitions. More specifically, we provide a O(|δ|log|Q|)-time algorithm computing a co-lex total preorder when the input is a Wheeler NFA, and an algorithm with the same time complexity computing the smallest-width co-lex partial order of any DFA. In addition, we present implementations of our algorithms and show that they are very efficient also in practice.
Cite as

Ruben Becker, Manuel Cáceres, Davide Cenzato, Sung-Hwan Kim, Bojana Kodric, Francisco Olivares, and Nicola Prezza. Sorting Finite Automata via Partition Refinement. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{becker_et_al:LIPIcs.ESA.2023.15,
  author =	{Becker, Ruben and C\'{a}ceres, Manuel and Cenzato, Davide and Kim, Sung-Hwan and Kodric, Bojana and Olivares, Francisco and Prezza, Nicola},
  title =	{{Sorting Finite Automata via Partition Refinement}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{15:1--15:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.15},
  URN =		{urn:nbn:de:0030-drops-186684},
  doi =		{10.4230/LIPIcs.ESA.2023.15},
  annote =	{Keywords: Wheeler automata, prefix sorting, pattern matching, graph compression, sorting, partition refinement}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2020.18
Parameterized Complexity of Feedback Vertex Sets on Hypergraphs

Authors: Pratibha Choudhary, Lawqueen Kanesh, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh

Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)

Abstract
A feedback vertex set in a hypergraph H is a set of vertices S such that deleting S from H results in an acyclic hypergraph. Here, deleting a vertex means removing the vertex and all incident hyperedges, and a hypergraph is acyclic if its vertex-edge incidence graph is acyclic. We study the (parameterized complexity of) the Hypergraph Feedback Vertex Set (HFVS) problem: given as input a hypergraph H and an integer k, determine whether H has a feedback vertex set of size at most k. It is easy to see that this problem generalizes the classic Feedback Vertex Set (FVS) problem on graphs. Remarkably, despite the central role of FVS in parameterized algorithms and complexity, the parameterized complexity of a generalization of FVS to hypergraphs has not been studied previously. In this paper, we fill this void. Our main results are as follows - HFVS is W[2]-hard (as opposed to FVS, which is fixed parameter tractable). - If the input hypergraph is restricted to a linear hypergraph (no two hyperedges intersect in more than one vertex), HFVS admits a randomized algorithm with running time 2^{𝒪(k³log k)}n^{𝒪(1)}. - If the input hypergraph is restricted to a d-hypergraph (hyperedges have cardinality at most d), then HFVS admits a deterministic algorithm with running time d^{𝒪(k)}n^{𝒪(1)}. The algorithm for linear hypergraphs combines ideas from the randomized algorithm for FVS by Becker et al. [J. Artif. Intell. Res., 2000] with the branching algorithm for Point Line Cover by Langerman and Morin [Discrete & Computational Geometry, 2005].
Cite as

Pratibha Choudhary, Lawqueen Kanesh, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Parameterized Complexity of Feedback Vertex Sets on Hypergraphs. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 18:1-18:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{choudhary_et_al:LIPIcs.FSTTCS.2020.18,
  author =	{Choudhary, Pratibha and Kanesh, Lawqueen and Lokshtanov, Daniel and Panolan, Fahad and Saurabh, Saket},
  title =	{{Parameterized Complexity of Feedback Vertex Sets on Hypergraphs}},
  booktitle =	{40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
  pages =	{18:1--18:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-174-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{182},
  editor =	{Saxena, Nitin and Simon, Sunil},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.18},
  URN =		{urn:nbn:de:0030-drops-132596},
  doi =		{10.4230/LIPIcs.FSTTCS.2020.18},
  annote =	{Keywords: feedback vertex sets, hypergraphs, FPT, randomized algorithms}
}
Document
DOI: 10.4230/LIPIcs.SEA.2017.8
Engineering an Approximation Scheme for Traveling Salesman in Planar Graphs

Authors: Amariah Becker, Eli Fox-Epstein, Philip N. Klein, and David Meierfrankenfeld

Published in: LIPIcs, Volume 75, 16th International Symposium on Experimental Algorithms (SEA 2017)

Abstract
We present an implementation of a linear-time approximation scheme for the traveling salesman problem on planar graphs with edge weights. We observe that the theoretical algorithm involves constants that are too large for practical use. Our implementation, which is not subject to the theoretical algorithm's guarantee, can quickly find good tours in very large planar graphs.
Cite as

Amariah Becker, Eli Fox-Epstein, Philip N. Klein, and David Meierfrankenfeld. Engineering an Approximation Scheme for Traveling Salesman in Planar Graphs. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{becker_et_al:LIPIcs.SEA.2017.8,
  author =	{Becker, Amariah and Fox-Epstein, Eli and Klein, Philip N. and Meierfrankenfeld, David},
  title =	{{Engineering an Approximation Scheme for Traveling Salesman in Planar Graphs}},
  booktitle =	{16th International Symposium on Experimental Algorithms (SEA 2017)},
  pages =	{8:1--8:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-036-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{75},
  editor =	{Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.8},
  URN =		{urn:nbn:de:0030-drops-76305},
  doi =		{10.4230/LIPIcs.SEA.2017.8},
  annote =	{Keywords: Traveling Salesman, Approximation Schemes, Planar Graph Algorithms, Algorithm Engineering}
}
Document
Multimedia Contribution
DOI: 10.4230/LIPIcs.SoCG.2017.62
Zapping Zika with a Mosquito-Managing Drone: Computing Optimal Flight Patterns with Minimum Turn Cost (Multimedia Contribution)

Authors: Aaron T. Becker, Mustapha Debboun, Sándor P. Fekete, Dominik Krupke, and An Nguyen

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
We present results arising from the problem of sweeping a mosquito-infested area with an Un-manned Aerial Vehicle (UAV) equipped with an electrified metal grid. This is related to the Traveling Salesman Problem, the Lawn Mower Problem and, most closely, Milling with TurnCost. Planning a good trajectory can be reduced to considering penalty and budget variants of covering a grid graph with minimum turn cost. On the theoretical side, we show the solution of a problem from The Open Problems Project that had been open for more than 15 years, and hint at approximation algorithms. On the practical side, we describe an exact method based on Integer Programming that is able to compute provably optimal instances with over 500 pixels. These solutions are actually used for practical trajectories, as demonstrated in the video.
Cite as

Aaron T. Becker, Mustapha Debboun, Sándor P. Fekete, Dominik Krupke, and An Nguyen. Zapping Zika with a Mosquito-Managing Drone: Computing Optimal Flight Patterns with Minimum Turn Cost (Multimedia Contribution). In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 62:1-62:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{becker_et_al:LIPIcs.SoCG.2017.62,
  author =	{Becker, Aaron T. and Debboun, Mustapha and Fekete, S\'{a}ndor P. and Krupke, Dominik and Nguyen, An},
  title =	{{Zapping Zika with a Mosquito-Managing Drone: Computing Optimal Flight Patterns with Minimum Turn Cost}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{62:1--62:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, 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.SoCG.2017.62},
  URN =		{urn:nbn:de:0030-drops-72394},
  doi =		{10.4230/LIPIcs.SoCG.2017.62},
  annote =	{Keywords: Covering tours, turn cost, complexity, exact optimization}
}
Document
DOI: 10.4230/DagMan.6.1.1
Engineering Academic Software (Dagstuhl Perspectives Workshop 16252)

Authors: Alice Allen, Cecilia Aragon, Christoph Becker, Jeffrey Carver, Andrei Chis, Benoit Combemale, Mike Croucher, Kevin Crowston, Daniel Garijo, Ashish Gehani, Carole Goble, Robert Haines, Robert Hirschfeld, James Howison, Kathryn Huff, Caroline Jay, Daniel S. Katz, Claude Kirchner, Katie Kuksenok, Ralf Lämmel, Oscar Nierstrasz, Matt Turk, Rob van Nieuwpoort, Matthew Vaughn, and Jurgen J. Vinju

Published in: Dagstuhl Manifestos, Volume 6, Issue 1 (2017)

Abstract
Software is often a critical component of scientific research. It can be a component of the academic research methods used to produce research results, or it may itself be an academic research result. Software, however, has rarely been considered to be a citable artifact in its own right. With the advent of open-source software, artifact evaluation committees of conferences, and journals that include source code and running systems as part of the published artifacts, we foresee that software will increasingly be recognized as part of the academic process. The quality and sustainability of this software must be accounted for, both a prioro and a posteriori. The Dagstuhl Perspectives Workshop on "Engineering Academic Software" has examined the strengths, weaknesses, risks, and opportunities of academic software engineering. A key outcome of the workshop is this Dagstuhl Manifesto, serving as a roadmap towards future professional software engineering for software-based research instruments and other software produced and used in an academic context. The manifesto is expressed in terms of a series of actionable "pledges" that users and developers of academic research software can take as concrete steps towards improving the environment in which that software is produced.
Cite as

Alice Allen, Cecilia Aragon, Christoph Becker, Jeffrey Carver, Andrei Chis, Benoit Combemale, Mike Croucher, Kevin Crowston, Daniel Garijo, Ashish Gehani, Carole Goble, Robert Haines, Robert Hirschfeld, James Howison, Kathryn Huff, Caroline Jay, Daniel S. Katz, Claude Kirchner, Katie Kuksenok, Ralf Lämmel, Oscar Nierstrasz, Matt Turk, Rob van Nieuwpoort, Matthew Vaughn, and Jurgen J. Vinju. Engineering Academic Software (Dagstuhl Perspectives Workshop 16252). In Dagstuhl Manifestos, Volume 6, Issue 1, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{allen_et_al:DagMan.6.1.1,
  author =	{Allen, Alice and Aragon, Cecilia and Becker, Christoph and Carver, Jeffrey and Chis, Andrei and Combemale, Benoit and Croucher, Mike and Crowston, Kevin and Garijo, Daniel and Gehani, Ashish and Goble, Carole and Haines, Robert and Hirschfeld, Robert and Howison, James and Huff, Kathryn and Jay, Caroline and Katz, Daniel S. and Kirchner, Claude and Kuksenok, Katie and L\"{a}mmel, Ralf and Nierstrasz, Oscar and Turk, Matt and van Nieuwpoort, Rob and Vaughn, Matthew and Vinju, Jurgen J.},
  title =	{{Engineering Academic Software (Dagstuhl Perspectives Workshop 16252)}},
  pages =	{1--20},
  journal =	{Dagstuhl Manifestos},
  ISSN =	{2193-2433},
  year =	{2017},
  volume =	{6},
  number =	{1},
  editor =	{Allen, Alice and Aragon, Cecilia and Becker, Christoph and Carver, Jeffrey and Chis, Andrei and Combemale, Benoit and Croucher, Mike and Crowston, Kevin and Garijo, Daniel and Gehani, Ashish and Goble, Carole and Haines, Robert and Hirschfeld, Robert and Howison, James and Huff, Kathryn and Jay, Caroline and Katz, Daniel S. and Kirchner, Claude and Kuksenok, Katie and L\"{a}mmel, Ralf and Nierstrasz, Oscar and Turk, Matt and van Nieuwpoort, Rob and Vaughn, Matthew and Vinju, Jurgen J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagMan.6.1.1},
  URN =		{urn:nbn:de:0030-drops-71468},
  doi =		{10.4230/DagMan.6.1.1},
  annote =	{Keywords: Academic software, Research software, Software citation, Software sustainability}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.16
Tilt: The Video - Designing Worlds to Control Robot Swarms with Only Global Signals

Authors: Aaron T. Becker, Erik D. Demaine, Sándor P. Fekete, Hamed Mohtasham Shad, and Rose Morris-Wright

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
We present fundamental progress on the computational universality of swarms of micro- or nano-scale robots in complex environments, controlled not by individual navigation, but by a uniform global, external force. More specifically, we consider a 2D grid world, in which all obstacles and robots are unit squares, and for each actuation, robots move maximally until they collide with an obstacle or another robot. The objective is to control robot motion within obstacles, design obstacles in order to achieve desired permutation of robots, and establish controlled interaction that is complex enough to allow arbitrary computations. In this video, we illustrate progress on all these challenges: we demonstrate NP-hardness of parallel navigation, we describe how to construct obstacles that allow arbitrary permutations, and we establish the necessary logic gates for performing arbitrary in-system computations.
Cite as

Aaron T. Becker, Erik D. Demaine, Sándor P. Fekete, Hamed Mohtasham Shad, and Rose Morris-Wright. Tilt: The Video - Designing Worlds to Control Robot Swarms with Only Global Signals. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 16-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{becker_et_al:LIPIcs.SOCG.2015.16,
  author =	{Becker, Aaron T. and Demaine, Erik D. and Fekete, S\'{a}ndor P. and Shad, Hamed Mohtasham and Morris-Wright, Rose},
  title =	{{Tilt: The Video - Designing Worlds to Control Robot Swarms with Only Global Signals}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{16--18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.16},
  URN =		{urn:nbn:de:0030-drops-50870},
  doi =		{10.4230/LIPIcs.SOCG.2015.16},
  annote =	{Keywords: Particle swarms, global control, complexity, geometric computation}
}
Document
DOI: 10.4230/DagSemProc.10281.1
10281 Abstracts Collection – Dynamically Reconfigurable Architectures

Authors: Peter M. Athanas, Jürgen Becker, Jürgen Teich, and Ingrid Verbauwhede

Published in: Dagstuhl Seminar Proceedings, Volume 10281, Dynamically Reconfigurable Architectures (2010)

Abstract
From 11.07.10 to 16.07.10, Dagstuhl Seminar 10281 ``Dynamically Reconfigurable Architectures '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Peter M. Athanas, Jürgen Becker, Jürgen Teich, and Ingrid Verbauwhede. 10281 Abstracts Collection – Dynamically Reconfigurable Architectures. In Dynamically Reconfigurable Architectures. Dagstuhl Seminar Proceedings, Volume 10281, pp. 1-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{athanas_et_al:DagSemProc.10281.1,
  author =	{Athanas, Peter M. and Becker, J\"{u}rgen and Teich, J\"{u}rgen and Verbauwhede, Ingrid},
  title =	{{10281 Abstracts Collection – Dynamically Reconfigurable Architectures}},
  booktitle =	{Dynamically Reconfigurable Architectures},
  pages =	{1--23},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10281},
  editor =	{Peter M. Athanas and J\"{u}rgen Becker and J\"{u}rgen Teich and Ingrid Verbauwhede},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10281.1},
  URN =		{urn:nbn:de:0030-drops-28962},
  doi =		{10.4230/DagSemProc.10281.1},
  annote =	{Keywords: Dynamically Run-Time Reconfigurable Computing Architectures, Self- adaptive Systems, Computational Models, Circuit Technologies, System Architecture, Reconfigurable/Adaptive Computing based on Nanotechnologies}
}
Document
DOI: 10.4230/DagSemProc.10281.4
A new project to address run-time reconfigurable hardware systems

Authors: Jim Torresen and Dirk Koch

Published in: Dagstuhl Seminar Proceedings, Volume 10281, Dynamically Reconfigurable Architectures (2010)

Abstract
Last autumn, we started a new project named Context Switching Reconfigurable Hardware for Communication Systems (COSRECOS). In this talk, I would like to present how we plan to address the challenge of changing hardware configurations while a system is in operation. The overall goal of the project is to contribute in making run-time reconfigurable systems more feasible in general. This includes introducing architectures for reducing reconfiguration time as well as undertaking tool development. Case studies by applications in network and communication systems will be a part of the project. Comments to the planned outline are much welcome.
Cite as

Jim Torresen and Dirk Koch. A new project to address run-time reconfigurable hardware systems. In Dynamically Reconfigurable Architectures. Dagstuhl Seminar Proceedings, Volume 10281, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{torresen_et_al:DagSemProc.10281.4,
  author =	{Torresen, Jim and Koch, Dirk},
  title =	{{A new project to address run-time reconfigurable hardware systems}},
  booktitle =	{Dynamically Reconfigurable Architectures},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10281},
  editor =	{Peter M. Athanas and J\"{u}rgen Becker and J\"{u}rgen Teich and Ingrid Verbauwhede},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10281.4},
  URN =		{urn:nbn:de:0030-drops-28943},
  doi =		{10.4230/DagSemProc.10281.4},
  annote =	{Keywords: }
}
Document
DOI: 10.4230/DagSemProc.10281.13
Towards a reconfigurable hardware architecture for implementing a LDPC module suitable for software radio systems

Authors: Rene Cumplido, Juan Manuel Campos, Claudia Feregrino-Uribe, and Jose Roberto Perez-Andrade

Published in: Dagstuhl Seminar Proceedings, Volume 10281, Dynamically Reconfigurable Architectures (2010)

Abstract
Forward Error Correction is a key piece in modern digital communications. When a signal is transmitted over a noisy channel, multiple errors are generated. FEC techniques are directed towards the recovery of such errors. In last years, LDPC (Low Density Parity Check) codes have attracted attention of researchers because of their excellent error correction capabilities, but for actual radios high performance is not enough since they require to communicate with other multiple radios too. In general, communication between multiple radios requires the use of different standards. In this sense, Software Defined Radio (SDR) approach allows building multi standard radios based on reconfigurability abilities which means that base components including recovery errors block must provide reconfigurable options. In this paper, some open problems in designing and implementing reconfigurable LDPC components are presented and discussed. Some features of works in the state of the art are commented and possible research lines proposed.
Cite as

Rene Cumplido, Juan Manuel Campos, Claudia Feregrino-Uribe, and Jose Roberto Perez-Andrade. Towards a reconfigurable hardware architecture for implementing a LDPC module suitable for software radio systems. In Dynamically Reconfigurable Architectures. Dagstuhl Seminar Proceedings, Volume 10281, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{cumplido_et_al:DagSemProc.10281.13,
  author =	{Cumplido, Rene and Campos, Juan Manuel and Feregrino-Uribe, Claudia and Perez-Andrade, Jose Roberto},
  title =	{{Towards a reconfigurable hardware architecture for implementing a LDPC module suitable for software radio systems}},
  booktitle =	{Dynamically Reconfigurable Architectures},
  pages =	{1--8},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10281},
  editor =	{Peter M. Athanas and J\"{u}rgen Becker and J\"{u}rgen Teich and Ingrid Verbauwhede},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10281.13},
  URN =		{urn:nbn:de:0030-drops-28950},
  doi =		{10.4230/DagSemProc.10281.13},
  annote =	{Keywords: LDPC codes, Software Defined Radio, Hardware Implementation}
}
Document
DOI: 10.4230/DagSemProc.10281.2
10281 Summary – Dynamically Reconfigurable Architectures

Authors: Peter M. Athanas, Jürgen Becker, Jürgen Teich, and Ingrid Verbauwhede

Published in: Dagstuhl Seminar Proceedings, Volume 10281, Dynamically Reconfigurable Architectures (2010)

Abstract
Dynamic and partial reconfiguration of hardware architectures such as FPGAs and coarse grain processing arrays bring an additional level of flexibility in the design of electronic systems by exploiting the possibility of configuring functions on-demand during run-time. When compared to emerging software-programmable Multi-Processor System-on-a-Chip (MPSoC) solutions, they benefit a lot from lower cost, more dedication and fit to a certain problem class as well as power and area efficiency. This has led to many new ways of approaching existing research topics in the area of hardware design and optimization techniques. For example, the possibility of performing adaptation during run-time raises questions in the areas of dynamic control, real-time response, on-line power management and design complexity, since the reconfigurability increases the design space towards infinity.
Cite as

Peter M. Athanas, Jürgen Becker, Jürgen Teich, and Ingrid Verbauwhede. 10281 Summary – Dynamically Reconfigurable Architectures. In Dynamically Reconfigurable Architectures. Dagstuhl Seminar Proceedings, Volume 10281, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{athanas_et_al:DagSemProc.10281.2,
  author =	{Athanas, Peter M. and Becker, J\"{u}rgen and Teich, J\"{u}rgen and Verbauwhede, Ingrid},
  title =	{{10281 Summary – Dynamically Reconfigurable Architectures}},
  booktitle =	{Dynamically Reconfigurable Architectures},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10281},
  editor =	{Peter M. Athanas and J\"{u}rgen Becker and J\"{u}rgen Teich and Ingrid Verbauwhede},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10281.2},
  URN =		{urn:nbn:de:0030-drops-28926},
  doi =		{10.4230/DagSemProc.10281.2},
  annote =	{Keywords: Dynamically Run-Time Reconfigurable Computing Architectures, Self- adaptive Systems, Computational Models, Circuit Technologies, System Architecture, CAD Tool Support, Reconfigurable/Adaptive Computing based on Nanotechnologies}
}
Document
DOI: 10.4230/DagSemProc.10281.3
A mathematical approach towards hardware design

Authors: Gerard J. M. Smit, Jan Kuper, and Christiaan P. R. Baaij

Published in: Dagstuhl Seminar Proceedings, Volume 10281, Dynamically Reconfigurable Architectures (2010)

Abstract
Today the hardware for embedded systems is often specified in VHDL. However, VHDL describes the system at a rather low level, which is cumbersome and may lead to design faults in large real life applications. There is a need of higher level abstraction mechanisms. In the embedded systems group of the University of Twente we are working on systematic and transformational methods to design hardware architectures, both multi core and single core. The main line in this approach is to start with a straightforward (often mathematical) specification of the problem. The next step is to find some adequate transformations on this specification, in particular to find specific optimizations, to be able to distribute the application over different cores. The result of these transformations is then translated into the functional programming language Haskell since Haskell is close to mathematics and such a translation often is straightforward. Besides, the Haskell code is executable, so one immediately has a simulation of the intended system. Next, the resulting Haskell specification is given to a compiler, called CëaSH (for CAES LAnguage for Synchronous Hardware) which translates the specification into VHDL. The resulting VHDL is synthesizable, so from there on standard VHDL-tooling can be used for synthesis. In this work we primarily focus on streaming applications: i.e. applications that can be modeled as data-flow graphs. At the moment the CëaSH system is ready in prototype form and in the presentation we will give several examples of how it can be used. In these examples it will be shown that the specification code is clear and concise. Furthermore, it is possible to use powerful abstraction mechanisms, such as polymorphism, higher order functions, pattern matching, lambda abstraction, partial application. These features allow a designer to describe circuits in a more natural and concise way than possible with the language elements found in the traditional hardware description languages. In addition we will give some examples of transformations that are possible in a mathematical specification, and which do not suffer from the problems encountered in, e.g., automatic parallelization of nested for-loops in C-programs.
Cite as

Gerard J. M. Smit, Jan Kuper, and Christiaan P. R. Baaij. A mathematical approach towards hardware design. In Dynamically Reconfigurable Architectures. Dagstuhl Seminar Proceedings, Volume 10281, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{smit_et_al:DagSemProc.10281.3,
  author =	{Smit, Gerard J. M. and Kuper, Jan and Baaij, Christiaan P. R.},
  title =	{{A mathematical approach towards hardware design}},
  booktitle =	{Dynamically Reconfigurable Architectures},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10281},
  editor =	{Peter M. Athanas and J\"{u}rgen Becker and J\"{u}rgen Teich and Ingrid Verbauwhede},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10281.3},
  URN =		{urn:nbn:de:0030-drops-28407},
  doi =		{10.4230/DagSemProc.10281.3},
  annote =	{Keywords: Hardware design, mathematical specification, streaming applications}
}
Document
DOI: 10.4230/DagSemProc.10281.5
Advances in Component-based System Design and Partial Run-time Reconfiguration

Authors: Dirk Koch

Published in: Dagstuhl Seminar Proceedings, Volume 10281, Dynamically Reconfigurable Architectures (2010)

Abstract
With passing over the 1M LUT barrier, FPGA technology is heading into new challenges and opportunities. While the present ASIC-like design methodology and tools will struggle to scale with such huge devices, providing partial run-time reconfiguration will be become obligatory for dealing with long configuration times and the increasing vulnerability to single event upsets. Within the COSRECOS project, we address these issues by developing methods and tools that allow to compose systems rapidly by plugging together fully physically implemented components. Moreover, by allowing a hot-swapping of such components, the tremendous advantages of partial run-time reconfiguration can be utilized. This talk will give an overview of recent trends, our present research activities, and will discuss open issues.
Cite as

Dirk Koch. Advances in Component-based System Design and Partial Run-time Reconfiguration. In Dynamically Reconfigurable Architectures. Dagstuhl Seminar Proceedings, Volume 10281, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{koch:DagSemProc.10281.5,
  author =	{Koch, Dirk},
  title =	{{Advances in Component-based System Design and Partial Run-time Reconfiguration}},
  booktitle =	{Dynamically Reconfigurable Architectures},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10281},
  editor =	{Peter M. Athanas and J\"{u}rgen Becker and J\"{u}rgen Teich and Ingrid Verbauwhede},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10281.5},
  URN =		{urn:nbn:de:0030-drops-28410},
  doi =		{10.4230/DagSemProc.10281.5},
  annote =	{Keywords: FPGA design, partial reconfiguretion, component-based design}
}
Document
DOI: 10.4230/DagSemProc.10281.6
Compiling Geometric Algebra Computations into Reconfigurable Hardware Accelerators

Authors: Jens Huthmann, Peter Müller, Florian Stock, Dietmar Hildenbrand, and Andreas Koch

Published in: Dagstuhl Seminar Proceedings, Volume 10281, Dynamically Reconfigurable Architectures (2010)

Abstract
Geometric Algebra (GA), a generalization of quaternions and complex numbers, is a very powerful framework for intuitively expressing and manipulating the complex geometric relationships common to engineering problems. However, actual processing of GA expressions is very compute intensive, and acceleration is generally required for practical use. GPUs and FPGAs offer such acceleration, while requiring only low-power per operation. In this paper, we present key components of a proof-of-concept compile flow combining symbolic and hardware optimization techniques to automatically generate hardware accelerators from the abstract GA descriptions that are suitable for high-performance embedded computing.
Cite as

Jens Huthmann, Peter Müller, Florian Stock, Dietmar Hildenbrand, and Andreas Koch. Compiling Geometric Algebra Computations into Reconfigurable Hardware Accelerators. In Dynamically Reconfigurable Architectures. Dagstuhl Seminar Proceedings, Volume 10281, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{huthmann_et_al:DagSemProc.10281.6,
  author =	{Huthmann, Jens and M\"{u}ller, Peter and Stock, Florian and Hildenbrand, Dietmar and Koch, Andreas},
  title =	{{Compiling Geometric Algebra Computations into Reconfigurable  Hardware Accelerators}},
  booktitle =	{Dynamically Reconfigurable Architectures},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10281},
  editor =	{Peter M. Athanas and J\"{u}rgen Becker and J\"{u}rgen Teich and Ingrid Verbauwhede},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10281.6},
  URN =		{urn:nbn:de:0030-drops-28389},
  doi =		{10.4230/DagSemProc.10281.6},
  annote =	{Keywords: Geometric Algebra FPGA High-Level-Compiler Gaalop}
}
Document
DOI: 10.4230/DagSemProc.10281.7
Design and Implementation of an Object-Oriented DPR-Framework

Authors: Norbert Abel

Published in: Dagstuhl Seminar Proceedings, Volume 10281, Dynamically Reconfigurable Architectures (2010)

Abstract
Nowadays, two innovative future trends regarding hardware development and hardware description can be found. The first trend concerns the hardware itself. Modern Xilinx FPGAs provide the possibility to be reconfigured partially and dynamically - which is called dynamical partial reconfiguration (DPR). DPR opens a huge field of new functionalities on FPGAs. However, using DPR means struggling with architectural details of the used FPGAs and the according synthesis and implementation tools. A developer would focus most of the time on DPR and only a small part of the time on the implementation of the actual modules - of course that is the opposite of what hardware engineers want to do. The second trend concerns the way hardware is described. Many hardware developing groups are looking forward to an HDL which operates on the algorithmic level, since this would come with a significant increase in productivity. The aim is to be able to translate common software algorithms to hardware in an efficient way (which is called high-level synthesis or HLS). Although both DPR and HLS are important future trends regarding hardware design, they develop quite independently. Today's software-to-hardware compilers focus on conventional hardware and therefore have to remove dynamic aspects such as the instantiation of calculating modules at runtime. Even object-oriented languages like SystemC do not support the dynamic instantiation of objects (that means the usage of new or delete outside of the constructor) for synthesis at all. On the other hand, DPR tools are working on the lowest possible layer regarding FPGAs: the bitfile level. Our research focuses on the design and the implementation of a Framework combining the two technologies, since this has the potential to kill two birds with one stone. Firstly, DPR can change the programming paradigm in future HDLs regarding dynamic instantiations. Dynamic parts would not have to be removed any longer but could be realized on the target FPGA using DPR. Secondly, a high-level language support of DPR technologies could help end its shadowy existence and turn it into a commonly used method.
Cite as

Norbert Abel. Design and Implementation of an Object-Oriented DPR-Framework. In Dynamically Reconfigurable Architectures. Dagstuhl Seminar Proceedings, Volume 10281, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{abel:DagSemProc.10281.7,
  author =	{Abel, Norbert},
  title =	{{Design and Implementation of an Object-Oriented DPR-Framework}},
  booktitle =	{Dynamically Reconfigurable Architectures},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10281},
  editor =	{Peter M. Athanas and J\"{u}rgen Becker and J\"{u}rgen Teich and Ingrid Verbauwhede},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10281.7},
  URN =		{urn:nbn:de:0030-drops-28365},
  doi =		{10.4230/DagSemProc.10281.7},
  annote =	{Keywords: FPGA, DPR, HLS, Object-Orientation}
}
  • Refine by Author
  • 7 Becker, Jürgen
  • 6 Athanas, Peter M.
  • 6 Teich, Jürgen
  • 3 Brebner, Gordon
  • 3 Verbauwhede, Ingrid
  • Show More...

  • Refine by Classification
  • 1 Computer systems organization → Robotics
  • 1 Computing methodologies → Artificial intelligence
  • 1 Theory of computation → Computational geometry
  • 1 Theory of computation → Distributed algorithms
  • 1 Theory of computation → Graph algorithms analysis
  • Show More...

  • Refine by Keyword
  • 4 FPGA
  • 2 Circuit Technologies
  • 2 Computational Models
  • 2 Dynamic Reconfiguration
  • 2 Dynamically Run-Time Reconfigurable Computing Architectures
  • Show More...

  • Refine by Type
  • 42 document

  • Refine by Publication Year
  • 19 2006
  • 14 2010
  • 3 2017
  • 2 2023
  • 1 2003
  • Show More...

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