Search Results

Documents authored by Lee, D. T.

Found 11 Possible Name Variants:

Lee, D.T.

Document
DOI: 10.4230/LIPIcs.STACS.2014.226
Online Dynamic Power Management with Hard Real-Time Guarantees

Authors: Jian-Jia Chen, Mong-Jen Kao, D.T. Lee, Ignaz Rutter, and Dorothea Wagner

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Abstract
We consider the problem of online dynamic power management that provides hard real-time guarantees for multi-processor systems. In this problem, a set of jobs, each associated with an arrival time, a deadline, and an execution time, arrives to the system in an online fashion. The objective is to compute a non-migrative preemptive schedule of the jobs and a sequence of power on/off operations of the processors so as to minimize the total energy consumption while ensuring that all the deadlines of the jobs are met. We assume that we can use as many processors as necessary. In this paper we examine the complexity of this problem and provide online strategies that lead to practical energy-efficient solutions for real-time multi-processor systems. First, we consider the case for which we know in advance that the set of jobs can be scheduled feasibly on a single processor. We show that, even in this case, the competitive factor of any online algorithm is at least 2.06. On the other hand, we give a 4-competitive online algorithm that uses at most two processors. For jobs with unit execution times, the competitive factor of this algorithm improves to 3.59. Second, we relax our assumption by considering as input multiple streams of jobs, each of which can be scheduled feasibly on a single processor. We present a trade-off between the energy-efficiency of the schedule and the number of processors to be used. More specifically, for k given job streams and h processors with h>k, we give a scheduling strategy such that the energy usage is at most 4.k/(h-k) times that used by any schedule which schedules each of the k streams on a separate processor. Finally, we drop the assumptions on the input set of jobs. We show that the competitive factor of any online algorithm is at least 2.28, even for the case of unit job execution times for which we further derive an O(1)-competitive algorithm.
Cite as

Jian-Jia Chen, Mong-Jen Kao, D.T. Lee, Ignaz Rutter, and Dorothea Wagner. Online Dynamic Power Management with Hard Real-Time Guarantees. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 226-238, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.STACS.2014.226,
  author =	{Chen, Jian-Jia and Kao, Mong-Jen and Lee, D.T. and Rutter, Ignaz and Wagner, Dorothea},
  title =	{{Online Dynamic Power Management with Hard Real-Time Guarantees}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{226--238},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.226},
  URN =		{urn:nbn:de:0030-drops-44607},
  doi =		{10.4230/LIPIcs.STACS.2014.226},
  annote =	{Keywords: Energy-Efficient Scheduling, Online Dynamic Power Management}
}

Lee, D. T.

Document
DOI: 10.4230/LIPIcs.ISAAC.2017.64
Tight Approximation for Partial Vertex Cover with Hard Capacities

Authors: Jia-Yau Shiau, Mong-Jen Kao, Ching-Chi Lin, and D. T. Lee

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
We consider the partial vertex cover problem with hard capacity constraints (Partial VC-HC) on hypergraphs. In this problem we are given a hypergraph G=(V,E) with a maximum edge size f and a covering requirement R. Each edge is associated with a demand, and each vertex is associated with a capacity and an (integral) available multiplicity. The objective is to compute a minimum vertex multiset such that at least R units of demand from the edges are covered by the capacities of the vertices in the multiset and the multiplicity of each vertex does not exceed its available multiplicity. In this paper we present an f-approximation for this problem, improving over a previous result of (2f+2)(1+epsilon) by Cheung et al to the tight extent possible. Our new ingredient of this work is a generalized analysis on the extreme points of the natural LP, developed from previous works, and a strengthened LP lower-bound obtained for the optimal solutions.
Cite as

Jia-Yau Shiau, Mong-Jen Kao, Ching-Chi Lin, and D. T. Lee. Tight Approximation for Partial Vertex Cover with Hard Capacities. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 64:1-64:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{shiau_et_al:LIPIcs.ISAAC.2017.64,
  author =	{Shiau, Jia-Yau and Kao, Mong-Jen and Lin, Ching-Chi and Lee, D. T.},
  title =	{{Tight Approximation for Partial Vertex Cover with Hard Capacities}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{64:1--64:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.64},
  URN =		{urn:nbn:de:0030-drops-82694},
  doi =		{10.4230/LIPIcs.ISAAC.2017.64},
  annote =	{Keywords: Approximation Algorithm, Capacitated Vertex Cover, Hard Capacities}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2016.40
O(f) Bi-Approximation for Capacitated Covering with Hard Capacities

Authors: Mong-Jen Kao, Hai-Lun Tu, and D. T. Lee

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract
We consider capacitated vertex cover with hard capacity constraints (VC-HC) on hypergraphs. In this problem we are given a hypergraph G = (V, E) with a maximum edge size f. Each edge is associated with a demand and each vertex is associated with a weight (cost), a capacity, and an available multiplicity. The objective is to find a minimum-weight vertex multiset such that the demands of the edges can be covered by the capacities of the vertices and the multiplicity of each vertex does not exceed its available multiplicity. In this paper we present an O(f) bi-approximation for VC-HC that gives a trade-off on the number of augmented multiplicity and the cost of the resulting cover. In particular, we show that, by augmenting the available multiplicity by a factor of k geq 2, a cover with a cost ratio of (1+ frac{1}{k - 1})(f - 1) to the optimal cover for the original instance can be obtained. This improves over a previous result, which has a cost ratio of f^2 via augmenting the available multiplicity by a factor of f.
Cite as

Mong-Jen Kao, Hai-Lun Tu, and D. T. Lee. O(f) Bi-Approximation for Capacitated Covering with Hard Capacities. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 40:1-40:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kao_et_al:LIPIcs.ISAAC.2016.40,
  author =	{Kao, Mong-Jen and Tu, Hai-Lun and Lee, D. T.},
  title =	{{O(f) Bi-Approximation for Capacitated Covering with Hard Capacities}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{40:1--40:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.40},
  URN =		{urn:nbn:de:0030-drops-68102},
  doi =		{10.4230/LIPIcs.ISAAC.2016.40},
  annote =	{Keywords: Capacitated Covering, Hard Capacities, Bi-criteria Approximation}
}

Lee, Edward

Document
DOI: 10.4230/LIPIcs.FSTTCS.2014.199
Lift & Project Systems Performing on the Partial Vertex Cover Polytope

Authors: Konstantinos Georgiou and Edward Lee

Published in: LIPIcs, Volume 29, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)

Abstract
We study integrality gap (IG) lower bounds on strong LP and SDP relaxations derived by the Sherali-Adams (SA), Lovász-Schrijver-SDP (LS_+), and Sherali-Adams-SDP (SA_+) lift-and-project (L&P) systems for the t-Partial-Vertex-Cover (t-PVC) problem, a variation of the classic Vertex-Cover problem in which only t edges need to be covered. t-PVC admits a 2-approximation using various algorithmic techniques, all relying on a natural LP relaxation. Starting from this LP relaxation, our main results assert that for every epsilon>0, level-Theta(n) LPs or SDPs derived by all known L&P systems that have been used for positive algorithmic results (but the Lasserre hierarchy) have IGs at least (1-epsilon)n/t, where n is the number of vertices of the input graph. Our lower bounds are nearly tight, in that level-n relaxations, even of the weakest systems, have integrality gap 1. As lift-and-project systems have given the best algorithms known for numerous combinatorial optimization problems, our results show that restricted yet powerful models of computation derived by many L&P systems fail to witness c-approximate solutions to t-PVC for any constant c, and for t=O(n). This is one of the very few known examples of an intractable combinatorial optimization problem for which LP-based algorithms induce a constant approximation ratio, still lift-and-project LP and SDP tightenings of the same LP have unbounded IGs. As further motivation for our results, we show that the SDP that has given the best algorithm known for t-PVC has integrality gap n/t on instances that can be solved by the level-1 LP relaxation derived by the LS system. This constitutes another rare phenomenon where (even in specific instances) a static LP outperforms an SDP that has been used for the best approximation guarantee for the problem at hand. Finally, we believe our results are of independent interest as they are among the very few known integrality gap lower bounds for LP and SDP 0-1 relaxations in which not all variables possess the same semantics in the underlying combinatorial optimization problem. Most importantly, one of our main contributions is that we make explicit of a new and simple methodology of constructing solutions to LP relaxations that almost trivially satisfy constraints derived by all SDP L&P systems known to be useful for algorithmic positive results (except the La system). The latter sheds some light as to why La tightenings seem strictly stronger than LS_+ or SA_+ tightenings.
Cite as

Konstantinos Georgiou and Edward Lee. Lift & Project Systems Performing on the Partial Vertex Cover Polytope. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 199-211, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{georgiou_et_al:LIPIcs.FSTTCS.2014.199,
  author =	{Georgiou, Konstantinos and Lee, Edward},
  title =	{{Lift \& Project Systems Performing on the Partial Vertex Cover Polytope}},
  booktitle =	{34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
  pages =	{199--211},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-77-4},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{29},
  editor =	{Raman, Venkatesh and Suresh, S. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2014.199},
  URN =		{urn:nbn:de:0030-drops-48437},
  doi =		{10.4230/LIPIcs.FSTTCS.2014.199},
  annote =	{Keywords: Partial vertex cover, combinatorial optimization, linear programming, semidefinite programming, lift and project systems, integrality gaps}
}
Document
DOI: 10.4230/DagSemProc.09481.1
09481 Abstracts Collection – SYNCHRON 2009

Authors: Albert Benveniste, Stephen A. Edwards, Edward Lee, Klaus Schneider, and Reinhard von Hanxleden

Published in: Dagstuhl Seminar Proceedings, Volume 9481, SYNCHRON 2009

Abstract
The 16th SYNCHRON workshop has been organized as Dagstuhl seminar 09481 from November 22-27, 2009. Online material of the seminar is available at the following web page: http://www.dagstuhl.de/de/programm/kalender/semhp/?semnr=09481
Cite as

Albert Benveniste, Stephen A. Edwards, Edward Lee, Klaus Schneider, and Reinhard von Hanxleden. 09481 Abstracts Collection – SYNCHRON 2009. In SYNCHRON 2009. Dagstuhl Seminar Proceedings, Volume 9481, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{benveniste_et_al:DagSemProc.09481.1,
  author =	{Benveniste, Albert and Edwards, Stephen A. and Lee, Edward and Schneider, Klaus and von Hanxleden, Reinhard},
  title =	{{09481 Abstracts Collection – SYNCHRON 2009}},
  booktitle =	{SYNCHRON 2009},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9481},
  editor =	{Albert Benveniste and Stephen A. Edwards and Edward Lee and Klaus Schneider and Reinhard von Hanxleden},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09481.1},
  URN =		{urn:nbn:de:0030-drops-24340},
  doi =		{10.4230/DagSemProc.09481.1},
  annote =	{Keywords: Synchronous languages, Safety-critical real-time systems, Model-based design, Discrete and hybrid systems, Combining synchronous and asynchronous models, Formally consistent subsetting of UML, High-level hardware modeling and synthesis, Compilation and code synthesis for embedded systems}
}
Document
DOI: 10.4230/DagSemProc.07451.1
07451 Abstracts Collection – Model-Based Engineering of Embedded Real-Time Systems

Authors: Holger Giese, Gabor Karsai, Edward Lee, Bernhard Rumpe, and Bernhard Schätz

Published in: Dagstuhl Seminar Proceedings, Volume 7451, Model-Based Engineering of Embedded Real-Time Systems (2007)

Abstract
From 04.11. to 09.11.2007, the Dagstuhl Seminar 07451 ``Model-Based Engineering of Embedded Real-Time Systems'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. 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

Holger Giese, Gabor Karsai, Edward Lee, Bernhard Rumpe, and Bernhard Schätz. 07451 Abstracts Collection – Model-Based Engineering of Embedded Real-Time Systems. In Model-Based Engineering of Embedded Real-Time Systems. Dagstuhl Seminar Proceedings, Volume 7451, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{giese_et_al:DagSemProc.07451.1,
  author =	{Giese, Holger and Karsai, Gabor and Lee, Edward and Rumpe, Bernhard and Sch\"{a}tz, Bernhard},
  title =	{{07451 Abstracts Collection – Model-Based Engineering of Embedded Real-Time Systems}},
  booktitle =	{Model-Based Engineering of Embedded Real-Time Systems},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7451},
  editor =	{Holger Giese and Gabor Karsai and Edward Lee and Bernhard Rumpe and Bernhard Sch\"{a}tz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07451.1},
  URN =		{urn:nbn:de:0030-drops-12718},
  doi =		{10.4230/DagSemProc.07451.1},
  annote =	{Keywords: Models, model-based, MDD, embedded systems, real-time systems, validation \& verification, tool-support, domain-specific, languages}
}
Document
DOI: 10.4230/DagSemProc.07451.2
07451 Summary – Model-Based Engineering of Embedded Real-Time Systems

Authors: Holger Giese, Gabor Karsai, Edward Lee, Bernhard Rumpe, and Bernhard Schätz

Published in: Dagstuhl Seminar Proceedings, Volume 7451, Model-Based Engineering of Embedded Real-Time Systems (2007)

Abstract
Today, embedded software plays a central role in most advanced technical systems such as airplanes, cell phones, and cars, and has become the main driver for innovation. Development, evolution, configuration and maintenance of embedded and distributed software nowadays often are serious challenges as a drastic increase of the software complexity can be observed in practice. The application of model-based engineering technologies to embedded real-time systems seems to be a good candidate to tackle some of the resulting problems.
Cite as

Holger Giese, Gabor Karsai, Edward Lee, Bernhard Rumpe, and Bernhard Schätz. 07451 Summary – Model-Based Engineering of Embedded Real-Time Systems. In Model-Based Engineering of Embedded Real-Time Systems. Dagstuhl Seminar Proceedings, Volume 7451, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{giese_et_al:DagSemProc.07451.2,
  author =	{Giese, Holger and Karsai, Gabor and Lee, Edward and Rumpe, Bernhard and Sch\"{a}tz, Bernhard},
  title =	{{07451 Summary – Model-Based Engineering of Embedded Real-Time Systems}},
  booktitle =	{Model-Based Engineering of Embedded Real-Time Systems},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7451},
  editor =	{Holger Giese and Gabor Karsai and Edward Lee and Bernhard Rumpe and Bernhard Sch\"{a}tz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07451.2},
  URN =		{urn:nbn:de:0030-drops-12720},
  doi =		{10.4230/DagSemProc.07451.2},
  annote =	{Keywords: Models, model-based, MDD, embedded systems, real-time systems, validation \& verification, tool-support, domain-specific languages}
}

Lee, Gordon K.

Document
DOI: 10.4230/DagSemProc.10401.4
Intelligent Guidance of an Unmanned Helicopter

Authors: Stuart H. Rubin and Gordon K. Lee

Published in: Dagstuhl Seminar Proceedings, Volume 10401, Learning, Planning and Sharing Robot Knowledge for Human-Robot Interaction (2011)

Abstract
The objective of this project is to define a science which allows for the evolution of complex software systems that can fully utilize massively parallel computers of ever-greater capability (initially dual quad cores running fewer higher-level sensors for tractability) and employ this design in human-robot interaction with a final goal of full autonomy of the robot (in this case, an unmanned helicopter). In order to test a new learning approach that can bestow intelligence on a system, based upon human (tutor) – robot (student) interaction, we are working jointly to design an intelligent system architecture, based on the KASER (Knowledge Amplification by Structural Expert Randomization), and plan to implement the methodology on an aerial vehicle (a helicopter), which will execute several maneuvers such as basic hovering, steep approach, confined area approach, and basic altitude flying. The software to perform these maneuvers will be developed using two methods (teach mode with a human-in-the-loop) and classical control. Then, the knowledge amplification system will autonomously generate another set of software, which will then be tested and compared to the execution of the baseline two software codes using the same helicopter flight scenarios. We anticipate that such complex functional real-time software can be most cost-effectively written through the use of a software-writing system embodying knowledge amplification.
Cite as

Stuart H. Rubin and Gordon K. Lee. Intelligent Guidance of an Unmanned Helicopter. In Learning, Planning and Sharing Robot Knowledge for Human-Robot Interaction. Dagstuhl Seminar Proceedings, Volume 10401, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{rubin_et_al:DagSemProc.10401.4,
  author =	{Rubin, Stuart H. and Lee, Gordon K.},
  title =	{{Intelligent Guidance of an Unmanned Helicopter}},
  booktitle =	{Learning, Planning and Sharing Robot Knowledge for Human-Robot Interaction},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2011},
  volume =	{10401},
  editor =	{Rachid Alami and R\"{u}diger Dillmann and Thomas C. Henderson and Alexandra Kirsch},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10401.4},
  URN =		{urn:nbn:de:0030-drops-29302},
  doi =		{10.4230/DagSemProc.10401.4},
  annote =	{Keywords: Evolution, Heuristics, KASER, System of Systems, Unmanned Helicopter}
}

Lee, Edward A.

Document
Invited Paper
DOI: 10.4230/OASIcs.WCET.2024.4
Invited Paper: Worst-Case Execution Time Analysis of Lingua Franca Applications

Authors: Martin Schoeberl, Ehsan Khodadad, Shaokai Lin, Emad Jacob Maroun, Luca Pezzarossa, and Edward A. Lee

Published in: OASIcs, Volume 121, 22nd International Workshop on Worst-Case Execution Time Analysis (WCET 2024)

Abstract
Real-time systems need to prove that all deadlines will be met. To enable this proof, the full stack of the system must be analyzable, and the right tools must be available. This includes the processor (execution platform), the runtime system, the compiler, and the WCET analysis tool. This paper presents a combination of the time-predictable processor Patmos, the coordination language Lingua Franca, and the WCET analysis tool Platin. We show how carefully written Lingua Franca programs enable static WCET analysis to build safety-critical applications.
Cite as

Martin Schoeberl, Ehsan Khodadad, Shaokai Lin, Emad Jacob Maroun, Luca Pezzarossa, and Edward A. Lee. Invited Paper: Worst-Case Execution Time Analysis of Lingua Franca Applications. In 22nd International Workshop on Worst-Case Execution Time Analysis (WCET 2024). Open Access Series in Informatics (OASIcs), Volume 121, pp. 4:1-4:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{schoeberl_et_al:OASIcs.WCET.2024.4,
  author =	{Schoeberl, Martin and Khodadad, Ehsan and Lin, Shaokai and Maroun, Emad Jacob and Pezzarossa, Luca and Lee, Edward A.},
  title =	{{Invited Paper: Worst-Case Execution Time Analysis of Lingua Franca Applications}},
  booktitle =	{22nd International Workshop on Worst-Case Execution Time Analysis (WCET 2024)},
  pages =	{4:1--4:13},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-346-1},
  ISSN =	{2190-6807},
  year =	{2024},
  volume =	{121},
  editor =	{Carle, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2024.4},
  URN =		{urn:nbn:de:0030-drops-204721},
  doi =		{10.4230/OASIcs.WCET.2024.4},
  annote =	{Keywords: worst-case execution time, coordination language, real-time systems, lingua franca}
}
Document
DOI: 10.4230/OASIcs.NG-RES.2023.3
Beyond the Threaded Programming Model on Real-Time Operating Systems

Authors: Erling Rennemo Jellum, Shaokai Lin, Peter Donovan, Efsane Soyer, Fuzail Shakir, Torleiv Bryne, Milica Orlandic, Marten Lohstroh, and Edward A. Lee

Published in: OASIcs, Volume 108, Fourth Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2023)

Abstract
The use of a real-time operating system (RTOS) raises the abstraction level for embedded systems design when compared to traditional bare-metal programming, resulting in simpler and more reusable application code. Modern RTOSes for resource-constrained platforms, like Zephyr and FreeRTOS, also offer threading support, but this kind of shared memory concurrency is a poor fit for expressing the reactive and interactive behaviors that are common in embedded systems. To address this, alternative concurrency models like the actor model or communicating sequential processes have been proposed. While those alternatives enable reactive design patterns, they fail to deliver determinism and do not address timing. This makes it difficult to verify that implemented behavior is as intended and impossible to specify timing constraints in a portable way. This makes it hard to create reusable library components out of common embedded design patterns, forcing developers to keep reinventing the wheel for each application and each platform. In this paper, we introduce the embedded target of Lingua Franca (LF) as a means to move beyond the threaded programming model provided by RTOSes and improve the state of the art in embedded programming. LF is based on the reactor model of computation, which is reactive, deterministic, and timed, providing a means to express concurrency and timing in a platform-independent way. We compare the performance of LF versus threaded C code - both running on Zephyr - in terms of response time, timing precision, throughput, and memory footprint.
Cite as

Erling Rennemo Jellum, Shaokai Lin, Peter Donovan, Efsane Soyer, Fuzail Shakir, Torleiv Bryne, Milica Orlandic, Marten Lohstroh, and Edward A. Lee. Beyond the Threaded Programming Model on Real-Time Operating Systems. In Fourth Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2023). Open Access Series in Informatics (OASIcs), Volume 108, pp. 3:1-3:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{jellum_et_al:OASIcs.NG-RES.2023.3,
  author =	{Jellum, Erling Rennemo and Lin, Shaokai and Donovan, Peter and Soyer, Efsane and Shakir, Fuzail and Bryne, Torleiv and Orlandic, Milica and Lohstroh, Marten and Lee, Edward A.},
  title =	{{Beyond the Threaded Programming Model on Real-Time Operating Systems}},
  booktitle =	{Fourth Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2023)},
  pages =	{3:1--3:13},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-268-6},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{108},
  editor =	{Terraneo, Federico and Cattaneo, Daniele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.NG-RES.2023.3},
  URN =		{urn:nbn:de:0030-drops-177348},
  doi =		{10.4230/OASIcs.NG-RES.2023.3},
  annote =	{Keywords: Real time, concurrency, reactors, Lingua Franca, RTOS}
}
Document
DOI: 10.4230/DagSemRep.143
Design Automation for Embedded Systems (Dagstuhl Seminar 9617)

Authors: Edward A. Lee, Giovanni de Micheli, Wofgang Rosenstiel, and Lothar Thiele

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Edward A. Lee, Giovanni de Micheli, Wofgang Rosenstiel, and Lothar Thiele. Design Automation for Embedded Systems (Dagstuhl Seminar 9617). Dagstuhl Seminar Report 143, pp. 1-25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1997)

Copy BibTex To Clipboard

@TechReport{lee_et_al:DagSemRep.143,
  author =	{Lee, Edward A. and de Micheli, Giovanni and Rosenstiel, Wofgang and Thiele, Lothar},
  title =	{{Design Automation for Embedded Systems (Dagstuhl Seminar 9617)}},
  pages =	{1--25},
  ISSN =	{1619-0203},
  year =	{1997},
  type = 	{Dagstuhl Seminar Report},
  number =	{143},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.143},
  URN =		{urn:nbn:de:0030-drops-150305},
  doi =		{10.4230/DagSemRep.143},
}

Lee, Matias David

Document
DOI: 10.4230/LIPIcs.MFCS.2016.29
Logical Characterization of Bisimulation for Transition Relations over Probability Distributions with Internal Actions

Authors: Matias David Lee and Erik P. de Vink

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
In recent years the study of probabilistic transition systems has shifted to transition relations over distributions to allow for a smooth adaptation of the standard non-probabilistic apparatus. In this paper we study transition relations over probability distributions in a setting with internal actions. We provide new logics that characterize probabilistic strong, weak and branching bisimulation. Because these semantics may be considered too strong in the probabilistic context, Eisentraut et al. recently proposed weak distribution bisimulation. To show the flexibility of our approach based on the framework of van Glabbeek for the non-deterministic setting, we provide a novel logical characterization for the latter probabilistic equivalence as well.
Cite as

Matias David Lee and Erik P. de Vink. Logical Characterization of Bisimulation for Transition Relations over Probability Distributions with Internal Actions. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 29:1-29:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{lee_et_al:LIPIcs.MFCS.2016.29,
  author =	{Lee, Matias David and de Vink, Erik P.},
  title =	{{Logical Characterization of Bisimulation for Transition Relations over Probability Distributions with Internal Actions}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{29:1--29:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.29},
  URN =		{urn:nbn:de:0030-drops-64441},
  doi =		{10.4230/LIPIcs.MFCS.2016.29},
  annote =	{Keywords: probabilistic transition systems, weak bisimulations, logical characterization, transition relation over distributions, modal logics}
}

Lee, Der-Tsai

Document
Complete Volume
DOI: 10.4230/LIPIcs.ISAAC.2018
LIPIcs, Volume 123, ISAAC'18, Complete Volume

Authors: Wen-Lian Hsu, Der-Tsai Lee, and Chung-Shou Liao

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

Abstract
LIPIcs, Volume 123, ISAAC'18, Complete Volume
Cite as

29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Proceedings{hsu_et_al:LIPIcs.ISAAC.2018,
  title =	{{LIPIcs, Volume 123, ISAAC'18, Complete Volume}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2019},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018},
  URN =		{urn:nbn:de:0030-drops-101600},
  doi =		{10.4230/LIPIcs.ISAAC.2018},
  annote =	{Keywords: Mathematics of computing, Theory of computation, Data structures design and analysis, Computing methodologies}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.ISAAC.2018.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Wen-Lian Hsu, Der-Tsai Lee, and Chung-Shou Liao

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

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 0:i-0:xviii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{hsu_et_al:LIPIcs.ISAAC.2018.0,
  author =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{0:i--0:xviii},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.0},
  URN =		{urn:nbn:de:0030-drops-99488},
  doi =		{10.4230/LIPIcs.ISAAC.2018.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2016.64
The (1|1)-Centroid Problem on the Plane Concerning Distance Constraints

Authors: Hung-I Yu, Tien-Ching Lin, and Der-Tsai Lee

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract
In 1982, Drezner proposed the (1|1)-centroid problem on the plane, in which two players, called the leader and the follower, open facilities to provide service to customers in a competitive manner. The leader opens the first facility, and then the follower opens the second. Each customer will patronize the facility closest to him (ties broken in favor of the leader's one), thereby decides the market share of the two players. The goal is to find the best position for the leader’s facility so that his market share is maximized. The best algorithm for this problem is an O(n^2 log n)-time parametric search approach, which searches over the space of possible market share values. In the same paper, Drezner also proposed a general version of (1|1)-centroid problem by introducing a minimal distance constraint R, such that the follower's facility is not allowed to be located within a distance R from the leader's. He proposed an O(n^5 log n)-time algorithm for this general version by identifying O(n^4) points as the candidates of the optimal solution and checking the market share for each of them. In this paper, we develop a new parametric search approach searching over the O(n^4) candidate points, and present an O(n^2 log n)-time algorithm for the general version, thereby closing the O(n^3) gap between the two bounds.
Cite as

Hung-I Yu, Tien-Ching Lin, and Der-Tsai Lee. The (1|1)-Centroid Problem on the Plane Concerning Distance Constraints. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 64:1-64:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{yu_et_al:LIPIcs.ISAAC.2016.64,
  author =	{Yu, Hung-I and Lin, Tien-Ching and Lee, Der-Tsai},
  title =	{{The (1|1)-Centroid Problem on the Plane Concerning Distance Constraints}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{64:1--64:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.64},
  URN =		{urn:nbn:de:0030-drops-68337},
  doi =		{10.4230/LIPIcs.ISAAC.2016.64},
  annote =	{Keywords: competitive facility, Euclidean plane, parametric search}
}

Lee, Edward J.

Document
DOI: 10.4230/LIPIcs.ICALP.2017.69
Exact Algorithms via Multivariate Subroutines

Authors: Serge Gaspers and Edward J. Lee

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
We consider the family of Phi-Subset problems, where the input consists of an instance I of size N over a universe U_I of size n and the task is to check whether the universe contains a subset with property Phi (e.g., Phi could be the property of being a feedback vertex set for the input graph of size at most k). Our main tool is a simple randomized algorithm which solves Phi-Subset in time (1+b-(1/c))^n N^(O(1)), provided that there is an algorithm for the Phi-Extension problem with running time b^{n-|X|} c^k N^{O(1)}. Here, the input for Phi-Extension is an instance I of size N over a universe U_I of size n, a subset X \subseteq U_I, and an integer k, and the task is to check whether there is a set Y with X \subseteq Y \subseteq U_I and |Y \ X| <= k with property Phi. We derandomize this algorithm at the cost of increasing the running time by a subexponential factor in n, and we adapt it to the enumeration setting where we need to enumerate all subsets of the universe with property Phi. This generalizes the results of Fomin et al. [STOC 2016] who proved the case where b=1. As case studies, we use these results to design faster deterministic algorithms for: - checking whether a graph has a feedback vertex set of size at most k - enumerating all minimal feedback vertex sets - enumerating all minimal vertex covers of size at most k, and - enumerating all minimal 3-hitting sets. We obtain these results by deriving new b^{n-|X|} c^k N^{O(1)}-time algorithms for the corresponding Phi-Extension problems (or enumeration variant). In some cases, this is done by adapting the analysis of an existing algorithm, or in other cases by designing a new algorithm. Our analyses are based on Measure and Conquer, but the value to minimize, 1+b-(1/c), is unconventional and requires non-convex optimization.
Cite as

Serge Gaspers and Edward J. Lee. Exact Algorithms via Multivariate Subroutines. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 69:1-69:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{gaspers_et_al:LIPIcs.ICALP.2017.69,
  author =	{Gaspers, Serge and Lee, Edward J.},
  title =	{{Exact Algorithms via Multivariate Subroutines}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{69:1--69:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.69},
  URN =		{urn:nbn:de:0030-drops-74251},
  doi =		{10.4230/LIPIcs.ICALP.2017.69},
  annote =	{Keywords: enumeration algorithms, exponential time algorithms, feedback vertex set, hitting set}
}

Lee, David J.

Document
DOI: 10.4230/LIPIcs.ESA.2021.60
Telescoping Filter: A Practical Adaptive Filter

Authors: David J. Lee, Samuel McCauley, Shikha Singh, and Max Stein

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
Filters are small, fast, and approximate set membership data structures. They are often used to filter out expensive accesses to a remote set S for negative queries (that is, filtering out queries x ∉ S). Filters have one-sided errors: on a negative query, a filter may say "present" with a tunable false-positive probability of ε. Correctness is traded for space: filters only use log (1/ε) + O(1) bits per element. The false-positive guarantees of most filters, however, hold only for a single query. In particular, if x is a false positive, a subsequent query to x is a false positive with probability 1, not ε. With this in mind, recent work has introduced the notion of an adaptive filter. A filter is adaptive if each query is a false positive with probability ε, regardless of answers to previous queries. This requires "fixing" false positives as they occur. Adaptive filters not only provide strong false positive guarantees in adversarial environments but also improve query performance on practical workloads by eliminating repeated false positives. Existing work on adaptive filters falls into two categories. On the one hand, there are practical filters, based on the cuckoo filter, that attempt to fix false positives heuristically without meeting the adaptivity guarantee. On the other hand, the broom filter is a very complex adaptive filter that meets the optimal theoretical bounds. In this paper, we bridge this gap by designing the telescoping adaptive filter (TAF), a practical, provably adaptive filter. We provide theoretical false-positive and space guarantees for our filter, along with empirical results where we compare its performance against state-of-the-art filters. We also implement the broom filter and compare it to the TAF. Our experiments show that theoretical adaptivity can lead to improved false-positive performance on practical inputs, and can be achieved while maintaining throughput that is similar to non-adaptive filters.
Cite as

David J. Lee, Samuel McCauley, Shikha Singh, and Max Stein. Telescoping Filter: A Practical Adaptive Filter. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 60:1-60:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{lee_et_al:LIPIcs.ESA.2021.60,
  author =	{Lee, David J. and McCauley, Samuel and Singh, Shikha and Stein, Max},
  title =	{{Telescoping Filter: A Practical Adaptive Filter}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{60:1--60:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.60},
  URN =		{urn:nbn:de:0030-drops-146410},
  doi =		{10.4230/LIPIcs.ESA.2021.60},
  annote =	{Keywords: Filters, approximate-membership query data structures (AMQs), Bloom filters, quotient filters, cuckoo filters, adaptivity, succinct data structures}
}

Lee, Duksang

Document
DOI: 10.4230/LIPIcs.ISAAC.2021.70
Γ-Graphic Delta-Matroids and Their Applications

Authors: Donggyu Kim, Duksang Lee, and Sang-il Oum

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
For an abelian group Γ, a Γ-labelled graph is a graph whose vertices are labelled by elements of Γ. We prove that a certain collection of edge sets of a Γ-labelled graph forms a delta-matroid, which we call a Γ-graphic delta-matroid, and provide a polynomial-time algorithm to solve the separation problem, which allows us to apply the symmetric greedy algorithm of Bouchet to find a maximum weight feasible set in such a delta-matroid. We present two algorithmic applications on graphs; Maximum Weight Packing of Trees of Order Not Divisible by k and Maximum Weight S-Tree Packing. We also discuss various properties of Γ-graphic delta-matroids.
Cite as

Donggyu Kim, Duksang Lee, and Sang-il Oum. Γ-Graphic Delta-Matroids and Their Applications. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 70:1-70:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{kim_et_al:LIPIcs.ISAAC.2021.70,
  author =	{Kim, Donggyu and Lee, Duksang and Oum, Sang-il},
  title =	{{\Gamma-Graphic Delta-Matroids and Their Applications}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{70:1--70:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.70},
  URN =		{urn:nbn:de:0030-drops-155038},
  doi =		{10.4230/LIPIcs.ISAAC.2021.70},
  annote =	{Keywords: delta-matroid, group-labelled graph, greedy algorithm, tree packing}
}

Lee, Dongho

Document
DOI: 10.4230/LIPIcs.FSTTCS.2021.51
Concrete Categorical Model of a Quantum Circuit Description Language with Measurement

Authors: Dongho Lee, Valentin Perrelle, Benoît Valiron, and Zhaowei Xu

Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)

Abstract
In this paper, we introduce dynamic lifting to a quantum circuit-description language, following the Proto-Quipper language approach. Dynamic lifting allows programs to transfer the result of measuring quantum data - qubits - into classical data - booleans -. We propose a type system and an operational semantics for the language and we state safety properties. Next, we introduce a concrete categorical semantics for the proposed language, basing our approach on a recent model from Rios&Selinger for Proto-Quipper-M. Our approach is to construct on top of a concrete category of circuits with measurements a Kleisli category, capturing as a side effect the action of retrieving classical content out of a quantum memory. We then show a soundness result for this semantics.
Cite as

Dongho Lee, Valentin Perrelle, Benoît Valiron, and Zhaowei Xu. Concrete Categorical Model of a Quantum Circuit Description Language with Measurement. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 51:1-51:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{lee_et_al:LIPIcs.FSTTCS.2021.51,
  author =	{Lee, Dongho and Perrelle, Valentin and Valiron, Beno\^{i}t and Xu, Zhaowei},
  title =	{{Concrete Categorical Model of a Quantum Circuit Description Language with Measurement}},
  booktitle =	{41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
  pages =	{51:1--51:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-215-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{213},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.51},
  URN =		{urn:nbn:de:0030-drops-155627},
  doi =		{10.4230/LIPIcs.FSTTCS.2021.51},
  annote =	{Keywords: Categorical semantics, Operational semantics, Quantum circuit description language}
}
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 About DROPS Imprint Privacy Contact