Search Results

Documents authored by Lee, Edward

Found 3 Possible Name Variants:

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, 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, 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}
}
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