21 Search Results for "Edwards, Stephen A."

Document
DOI: 10.4230/LIPIcs.ISAAC.2025.42
Parameterized Reunion with Achromatic Number

Authors: Satyabrata Jana, Souvik Saha, Saket Saurabh, and Anannya Upasana

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
In this paper, we study the Achromatic Number problem. Given a graph G and an integer k, the task is to determine whether there exists a proper coloring of G, using at least k colors, in which every pair of distinct colors appears on the endpoints of some edge. It was established early on that the problem is fixed-parameter tractable (FPT)- even before the formal development of parameterized complexity. In fact, Farber, Hahn, Hell, and Miller [JCTB, 1986] devised an algorithm with a running time of 𝒪(f(k) ⋅ |E(G)|). Although the exact form of f(k) was not specified, it appears to be at least doubly exponential in k. In our work, we first present an algorithm with an explicit dependence on k, and then introduce another algorithm that is parameterized by the vertex cover number of the graph. More formally, we show the following. - Achromatic Number is solvable in time 2^𝒪(k⁵)+𝒪(|E(G)|). - Achromatic Number admits a polynomial kernel when the input is restricted to a d-degenerate graph and a more efficient kernel on trees. - We also study the parameterized complexity of the problem with respect to Vertex Cover and show that it admits an FPT algorithm running in time 2^𝒪(𝓁²) ⋅ n^𝒪(1), where 𝓁 is the size of a vertex cover.
Cite as

Satyabrata Jana, Souvik Saha, Saket Saurabh, and Anannya Upasana. Parameterized Reunion with Achromatic Number. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 42:1-42:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{jana_et_al:LIPIcs.ISAAC.2025.42,
  author =	{Jana, Satyabrata and Saha, Souvik and Saurabh, Saket and Upasana, Anannya},
  title =	{{Parameterized Reunion with Achromatic Number}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{42:1--42:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.42},
  URN =		{urn:nbn:de:0030-drops-249502},
  doi =		{10.4230/LIPIcs.ISAAC.2025.42},
  annote =	{Keywords: Achromatic number, Coloring, Fixed-parameter tractability, Kernelization, Lower bound, W-hardness}
}
Document
DOI: 10.4230/OASIcs.Programming.2025.23
The Pyttern Program Query Language

Authors: Julien Liénard, Kim Mens, and Siegfried Nijssen

Published in: OASIcs, Volume 134, Companion Proceedings of the 9th International Conference on the Art, Science, and Engineering of Programming (Programming 2025)

Abstract
Despite the availability of numerous tools and languages for detecting structural patterns in programs, their complexity often presents a steep learning curve. This highlights the need for a program query language that is easier to learn, use, and read while remaining sufficiently expressive for defining and detecting relevant structural coding patterns in program code. To address this challenge, we present Pyttern, a query language that extends Python syntax with regular-expression-inspired wildcards, enabling intuitive pattern-based querying of Python code. Its implementation relies upon a custom pushdown automaton describing how to match patterns over program parse trees, thus providing a robust foundation for structural code analysis. We evaluate Pyttern’s usability and effectiveness through a study involving 35 master’s students, who were asked to write seven different patterns to identify known programming misconceptions. The results demonstrate that Pyttern is both easy to learn and practical to use, at least for analysing small-scale programs.
Cite as

Julien Liénard, Kim Mens, and Siegfried Nijssen. The Pyttern Program Query Language. In Companion Proceedings of the 9th International Conference on the Art, Science, and Engineering of Programming (Programming 2025). Open Access Series in Informatics (OASIcs), Volume 134, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{lienard_et_al:OASIcs.Programming.2025.23,
  author =	{Li\'{e}nard, Julien and Mens, Kim and Nijssen, Siegfried},
  title =	{{The Pyttern Program Query Language}},
  booktitle =	{Companion Proceedings of the 9th International Conference on the Art, Science, and Engineering of Programming (Programming 2025)},
  pages =	{23:1--23:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-382-9},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{134},
  editor =	{Edwards, Jonathan and Perera, Roly and Petricek, Tomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Programming.2025.23},
  URN =		{urn:nbn:de:0030-drops-243075},
  doi =		{10.4230/OASIcs.Programming.2025.23},
  annote =	{Keywords: Pyttern, Program Query Languages, Python, Pattern Matching, Parse Tree, Pushdown Automaton, Static Code Analysis, Wildcards, Tree Pattern Matching}
}
Document
Extended Abstract
DOI: 10.4230/OASIcs.Programming.2025.3
A Pragmatic Approach to Replay Compilation (Extended Abstract)

Authors: Andrej Pečimúth, David Leopoldseder, and Petr Tůma

Published in: OASIcs, Volume 134, Companion Proceedings of the 9th International Conference on the Art, Science, and Engineering of Programming (Programming 2025)

Abstract
Dynamic compilers generate code based on the information provided by the virtual machine (VM) running the corresponding application. Due to the environment’s non-deterministic nature, every compilation result is typically unique. This is a problem when reproducibility is desired, such as when debugging a crash of the JIT compiler or diagnosing performance problems. As a solution, we present a pragmatic approach to replay compilation that is suitable for integration in a production-grade VM. Our approach is based on instrumenting the VM’s compiler interface, allowing us to record the compiler’s queries and their results to the VM. We serialize them and use them to replicate the compiler’s query results in a replayed compilation. Assuming the compiler is deterministic, this approach systematically ensures that the replayed compilation result is equivalent to the recorded one. The dynamic compiler is invoked directly without the need to execute the original application. A compiler developer can replay a compilation with additional diagnostic options or evaluate metrics such as compilation speed. We developed a working prototype for GraalVM, showing that replay compilation can be implemented without requiring extensive compiler or VM changes. We are working with the GraalVM developers to integrate it into the open-source compiler to unlock these benefits and new use cases for the community.
Cite as

Andrej Pečimúth, David Leopoldseder, and Petr Tůma. A Pragmatic Approach to Replay Compilation (Extended Abstract). In Companion Proceedings of the 9th International Conference on the Art, Science, and Engineering of Programming (Programming 2025). Open Access Series in Informatics (OASIcs), Volume 134, pp. 3:1-3:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{pecimuth_et_al:OASIcs.Programming.2025.3,
  author =	{Pe\v{c}im\'{u}th, Andrej and Leopoldseder, David and T\r{u}ma, Petr},
  title =	{{A Pragmatic Approach to Replay Compilation}},
  booktitle =	{Companion Proceedings of the 9th International Conference on the Art, Science, and Engineering of Programming (Programming 2025)},
  pages =	{3:1--3:4},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-382-9},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{134},
  editor =	{Edwards, Jonathan and Perera, Roly and Petricek, Tomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Programming.2025.3},
  URN =		{urn:nbn:de:0030-drops-242874},
  doi =		{10.4230/OASIcs.Programming.2025.3},
  annote =	{Keywords: replay compilation, dynamic compilation, virtual machines}
}
Document
DOI: 10.4230/OASIcs.Programming.2025.25
Who Owns the Contents of a Doubly-Linked List?

Authors: Dimi Racordon

Published in: OASIcs, Volume 134, Companion Proceedings of the 9th International Conference on the Art, Science, and Engineering of Programming (Programming 2025)

Abstract
Despite their popularity, systems enforcing full ownership guarantees such as Rust leave many users frustrated with the inability to represent notionally self-referential data structures - e.g., doubly-linked lists - using first-class references. This frustration has motivated a number of proposals to relax on full ownership to support idioms common in languages with pervasive reference semantics. In this paper, we take a look at the way value-oriented languages address this issue and study representations of arbitrary graph-like data structures without references.
Cite as

Dimi Racordon. Who Owns the Contents of a Doubly-Linked List?. In Companion Proceedings of the 9th International Conference on the Art, Science, and Engineering of Programming (Programming 2025). Open Access Series in Informatics (OASIcs), Volume 134, pp. 25:1-25:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{racordon:OASIcs.Programming.2025.25,
  author =	{Racordon, Dimi},
  title =	{{Who Owns the Contents of a Doubly-Linked List?}},
  booktitle =	{Companion Proceedings of the 9th International Conference on the Art, Science, and Engineering of Programming (Programming 2025)},
  pages =	{25:1--25:10},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-382-9},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{134},
  editor =	{Edwards, Jonathan and Perera, Roly and Petricek, Tomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Programming.2025.25},
  URN =		{urn:nbn:de:0030-drops-243092},
  doi =		{10.4230/OASIcs.Programming.2025.25},
  annote =	{Keywords: self-referential data structures, ownership, mutable value semantics, performance}
}
Document
DOI: 10.4230/OASIcs.ICPEC.2025.1
Exploring Mutation Testing for Teaching Introductory Programming

Authors: Pedro Vasconcelos

Published in: OASIcs, Volume 133, 6th International Computer Programming Education Conference (ICPEC 2025)

Abstract
This paper proposes the use of introductory programming assignments based on mutation testing where students are asked to write tests rather than code. We believe such exercises can be used to teach code reading skills before students could write the corresponding programs on their own. Furthermore, feedback for such exercises can be automatically generated using testing tools. We have extended an existing web-based system for programming exercises with such mutation testing assignments and show some example use cases. This is on-going work that has yet to be validated in the classroom.
Cite as

Pedro Vasconcelos. Exploring Mutation Testing for Teaching Introductory Programming. In 6th International Computer Programming Education Conference (ICPEC 2025). Open Access Series in Informatics (OASIcs), Volume 133, pp. 1:1-1:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{vasconcelos:OASIcs.ICPEC.2025.1,
  author =	{Vasconcelos, Pedro},
  title =	{{Exploring Mutation Testing for Teaching Introductory Programming}},
  booktitle =	{6th International Computer Programming Education Conference (ICPEC 2025)},
  pages =	{1:1--1:8},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-393-5},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{133},
  editor =	{Queir\'{o}s, Ricardo and Pinto, M\'{a}rio and Portela, Filipe and Sim\~{o}es, Alberto},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ICPEC.2025.1},
  URN =		{urn:nbn:de:0030-drops-240319},
  doi =		{10.4230/OASIcs.ICPEC.2025.1},
  annote =	{Keywords: mutation testing, programming education}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.39
Consumable Data via Quantum Communication

Authors: Dar Gilboa, Siddhartha Jain, and Jarrod R. McClean

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
Classical data can be copied and re-used for computation, with adverse consequences economically and in terms of data privacy. Motivated by this, we formulate problems in one-way communication complexity where Alice holds some data x and Bob holds m inputs y_1, …, y_m. They want to compute m instances of a bipartite relation R(⋅,⋅) on every pair (x, y_1), …, (x, y_m). We call this the asymmetric direct sum question for one-way communication. We give examples where the quantum communication complexity of such problems scales polynomially with m, while the classical communication complexity depends at most logarithmically on m. Thus, for such problems, data behaves like a consumable resource that is effectively destroyed upon use when the owner stores and transmits it as quantum states, but not when transmitted classically. We show an application to a strategic data-selling game, and discuss other potential economic implications.
Cite as

Dar Gilboa, Siddhartha Jain, and Jarrod R. McClean. Consumable Data via Quantum Communication. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 39:1-39:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gilboa_et_al:LIPIcs.APPROX/RANDOM.2025.39,
  author =	{Gilboa, Dar and Jain, Siddhartha and McClean, Jarrod R.},
  title =	{{Consumable Data via Quantum Communication}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{39:1--39:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.39},
  URN =		{urn:nbn:de:0030-drops-244059},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.39},
  annote =	{Keywords: quantum communication, one-time programs, data markets}
}
Document
DOI: 10.4230/OASIcs.ICPEC.2025.10
Standards-Based Grading in Undergraduate Courses for Technology Majors

Authors: Ruth Lamprecht, Jonathan McCurdy, Melanie Butler, Brian Heinold, and Daniel Salinas Duron

Published in: OASIcs, Volume 133, 6th International Computer Programming Education Conference (ICPEC 2025)

Abstract
This paper outlines the methods employed by several instructors within a single department to implement standards-based assessments. The authors began integrating standards across multiple courses in their computer science, cybersecurity, data science, and mathematics programs. This shift was driven by a desire to promote equity in grading and to address the growing influence of artificial intelligence, which can obscure a student’s true understanding. In this work, the authors examine the supporting research that guided their motivation and informed their implementation of various grading techniques. With an emphasis on courses involving technology, they also detail the processes they use to manage the new assessments, provide examples of assessment questions, and share key lessons learned in making this transition successful for both instructors and students. This work addresses a significant gap in the literature, as there appears to be a notable lack of resources on the application of standards-based grading in technical disciplines.
Cite as

Ruth Lamprecht, Jonathan McCurdy, Melanie Butler, Brian Heinold, and Daniel Salinas Duron. Standards-Based Grading in Undergraduate Courses for Technology Majors. In 6th International Computer Programming Education Conference (ICPEC 2025). Open Access Series in Informatics (OASIcs), Volume 133, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{lamprecht_et_al:OASIcs.ICPEC.2025.10,
  author =	{Lamprecht, Ruth and McCurdy, Jonathan and Butler, Melanie and Heinold, Brian and Salinas Duron, Daniel},
  title =	{{Standards-Based Grading in Undergraduate Courses for Technology Majors}},
  booktitle =	{6th International Computer Programming Education Conference (ICPEC 2025)},
  pages =	{10:1--10:14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-393-5},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{133},
  editor =	{Queir\'{o}s, Ricardo and Pinto, M\'{a}rio and Portela, Filipe and Sim\~{o}es, Alberto},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ICPEC.2025.10},
  URN =		{urn:nbn:de:0030-drops-240408},
  doi =		{10.4230/OASIcs.ICPEC.2025.10},
  annote =	{Keywords: Alternative Grading, Standards-Based Grading, Computer Science}
}
Document
DOI: 10.4230/LIPIcs.GIScience.2025.18
U-Prithvi: Integrating a Foundation Model and U-Net for Enhanced Flood Inundation Mapping

Authors: Vit Kostejn, Yamil Essus, Jenna Abrahamson, and Ranga Raju Vatsavai

Published in: LIPIcs, Volume 346, 13th International Conference on Geographic Information Science (GIScience 2025)

Abstract
In recent years, large pre-trained models, commonly referred to as foundation models, have become increasingly popular for various tasks leveraging transfer learning. This trend has expanded to remote sensing, where transformer-based foundation models such as Prithvi, msGFM, and SatSwinMAE have been utilized for a range of applications. While these transformer-based models, particularly the Prithvi model, exhibit strong generalization capabilities, they have limitations on capturing fine-grained details compared to convolutional neural network architectures like U-Net in segmentation tasks. In this paper, we propose a novel architecture, U-Prithvi, which combines the strengths of the Prithvi transformer with those of U-Net. We introduce a RandomHalfMaskLayer to ensure balanced learning from both models during training. Our approach is evaluated on the Sen1Floods11 dataset for flood inundation mapping, and experimental results demonstrate better performance of U-Prithvi over both individual models, achieving improved performance on out-of-sample data. While this principle is illustrated using the Prithvi model, it is easily adaptable to other foundation models.
Cite as

Vit Kostejn, Yamil Essus, Jenna Abrahamson, and Ranga Raju Vatsavai. U-Prithvi: Integrating a Foundation Model and U-Net for Enhanced Flood Inundation Mapping. In 13th International Conference on Geographic Information Science (GIScience 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 346, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kostejn_et_al:LIPIcs.GIScience.2025.18,
  author =	{Kostejn, Vit and Essus, Yamil and Abrahamson, Jenna and Vatsavai, Ranga Raju},
  title =	{{U-Prithvi: Integrating a Foundation Model and U-Net for Enhanced Flood Inundation Mapping}},
  booktitle =	{13th International Conference on Geographic Information Science (GIScience 2025)},
  pages =	{18:1--18:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-378-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{346},
  editor =	{Sila-Nowicka, Katarzyna and Moore, Antoni and O'Sullivan, David and Adams, Benjamin and Gahegan, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2025.18},
  URN =		{urn:nbn:de:0030-drops-238479},
  doi =		{10.4230/LIPIcs.GIScience.2025.18},
  annote =	{Keywords: GeoAI, flood mapping, foundation model, U-Net, Prithvi}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.42
Fitting Tree Metrics and Ultrametrics in Data Streams

Authors: Amir Carmel, Debarati Das, Evangelos Kipouridis, and Evangelos Pipis

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Fitting distances to tree metrics and ultrametrics are two widely used methods in hierarchical clustering, primarily explored within the context of numerical taxonomy. Formally, given a positive distance function D: binom(V,2) → ℝ_{>0}, the goal is to find a tree (or an ultrametric) T including all elements of set V, such that the difference between the distances among vertices in T and those specified by D is minimized. Numerical taxonomy was first introduced by Sneath and Sokal [Nature 1962], and since then it has been studied extensively in both biology and computer science. In this paper, we initiate the study of ultrametric and tree metric fitting problems in the semi-streaming model, where the distances between pairs of elements from V (with |V| = n), defined by the function D, can arrive in an arbitrary order. We study these problems under various distance norms; namely the 𝓁₀ objective, which aims to minimize the number of modified entries in D to fit a tree-metric or an ultrametric; the 𝓁₁ objective, which seeks to minimize the total sum of distance errors across all pairs of points in V; and the 𝓁_∞ objective, which focuses on minimizing the maximum error incurred by any entries in D. - Our first result addresses the 𝓁₀ objective. We provide a single-pass polynomial-time Õ(n)-space O(1) approximation algorithm for ultrametrics and prove that no single-pass exact algorithm exists, even with exponential time. - Next, we show that the algorithm for 𝓁₀ implies an O(Δ/δ) approximation for the 𝓁₁ objective, where Δ is the maximum, and δ is the minimum absolute difference between distances in the input. This bound matches the best-known approximation for the RAM model using a combinatorial algorithm when Δ/δ = O(n). - For the 𝓁_∞ objective, we provide a complete characterization of the ultrametric fitting problem. First, we present a single-pass polynomial-time Õ(n)-space 2-approximation algorithm and show that no better than 2-approximation is possible, even with exponential time. Furthermore, we show that with an additional pass, it is possible to achieve a polynomial-time exact algorithm for ultrametrics. - Finally, we extend all these results to tree metrics by using only one additional pass through the stream and without asymptotically increasing the approximation factor.
Cite as

Amir Carmel, Debarati Das, Evangelos Kipouridis, and Evangelos Pipis. Fitting Tree Metrics and Ultrametrics in Data Streams. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 42:1-42:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{carmel_et_al:LIPIcs.ICALP.2025.42,
  author =	{Carmel, Amir and Das, Debarati and Kipouridis, Evangelos and Pipis, Evangelos},
  title =	{{Fitting Tree Metrics and Ultrametrics in Data Streams}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{42:1--42:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.42},
  URN =		{urn:nbn:de:0030-drops-234197},
  doi =		{10.4230/LIPIcs.ICALP.2025.42},
  annote =	{Keywords: Streaming, Clustering, Ultrametrics, Tree metrics, Distance fitting}
}
Document
DOI: 10.4230/LITES.10.1.2
Towards a Coq-verified Chain of Esterel Semantics

Authors: Lionel Rieg and Gérard Berry

Published in: LITES, Volume 10, Issue 1 (2025). Leibniz Transactions on Embedded Systems, Volume 10, Issue 1

Abstract
This article focuses on formally specifying and verifying the chain of formal semantics of the Esterel synchronous programming language using the Coq proof assistant. In particular, in addition to the standard logical (LBS) semantics, constructive semantics (CBS) and constructive state semantics (CSS), we introduce a novel microstep semantics that gets rid of the Must/Can potential function pair of the constructive semantics and can be viewed as an abstract version of Esterel’s circuit semantics used by compilers to generate software code and hardware designs. The article also comes with formal proofs in Coq of the equivalence between the CBS and CSS semantics and of the refinement of the CSS by the microstep semantics, except for the loop construct of Esterel.
Cite as

Lionel Rieg and Gérard Berry. Towards a Coq-verified Chain of Esterel Semantics. In LITES, Volume 10, Issue 1 (2025). Leibniz Transactions on Embedded Systems, Volume 10, Issue 1, pp. 2:1-2:54, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Article{rieg_et_al:LITES.10.1.2,
  author =	{Rieg, Lionel and Berry, G\'{e}rard},
  title =	{{Towards a Coq-verified Chain of Esterel Semantics}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{2:1--2:54},
  ISSN =	{2199-2002},
  year =	{2025},
  volume =	{10},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES.10.1.2},
  URN =		{urn:nbn:de:0030-drops-230144},
  doi =		{10.4230/LITES.10.1.2},
  annote =	{Keywords: Esterel programming language, formal verification, Coq proof assistant}
}
Document
DOI: 10.4230/OASIcs.NG-RES.2025.1
Programming Time-Predictable Processors with Lingua Franca

Authors: Magnus Mæhlum, Erling Rennemo Jellum, Shaokai Lin, Marten Lohstroh, Martin Schoeberl, Sverre Hendseth, and Edward A. Lee

Published in: OASIcs, Volume 128, Sixth Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2025)

Abstract
Precision-timed (PRET) machines are an alternative to modern processors that provide precise control over the timing of software execution. This paper describes a platform for developing predictable real-time embedded systems that pair PRET machines with Lingua Franca (LF), a recent reactor-based coordination language with temporal semantics. Specifically, we port LF to FlexPRET, a PRET machine with flexible hardware thread scheduling. We evaluate single-threaded LF with a tight control loop style application on four embedded platforms, including the FlexPRET. The results reveal the underlying platform’s timing variability and how LF plus FlexPRET can remedy this timing variability. Finally, we compare single-threaded to multithreaded LF, again concerning timing. The four embedded platforms used are FlexPRET (bare-metal), RP2040 (bare-metal), nRF52 (with Zephyr), and Raspberry Pi 3b+ (with Linux). Our results indicate that FlexPRET with LF is attractive when precise timing is essential.
Cite as

Magnus Mæhlum, Erling Rennemo Jellum, Shaokai Lin, Marten Lohstroh, Martin Schoeberl, Sverre Hendseth, and Edward A. Lee. Programming Time-Predictable Processors with Lingua Franca. In Sixth Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2025). Open Access Series in Informatics (OASIcs), Volume 128, pp. 1:1-1:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{maehlum_et_al:OASIcs.NG-RES.2025.1,
  author =	{M{\ae}hlum, Magnus and Jellum, Erling Rennemo and Lin, Shaokai and Lohstroh, Marten and Schoeberl, Martin and Hendseth, Sverre and Lee, Edward A.},
  title =	{{Programming Time-Predictable Processors with Lingua Franca}},
  booktitle =	{Sixth Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2025)},
  pages =	{1:1--1:13},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-366-9},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{128},
  editor =	{Yomsi, Patrick Meumeu and Wildermann, Stefan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.NG-RES.2025.1},
  URN =		{urn:nbn:de:0030-drops-229876},
  doi =		{10.4230/OASIcs.NG-RES.2025.1},
  annote =	{Keywords: Real-time systems, time-predictable architecture, embedded system, coordination language}
}
Document
Vision
DOI: 10.4230/TGDK.1.1.9
Trust, Accountability, and Autonomy in Knowledge Graph-Based AI for Self-Determination

Authors: Luis-Daniel Ibáñez, John Domingue, Sabrina Kirrane, Oshani Seneviratne, Aisling Third, and Maria-Esther Vidal

Published in: TGDK, Volume 1, Issue 1 (2023): Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge, Volume 1, Issue 1

Abstract
Knowledge Graphs (KGs) have emerged as fundamental platforms for powering intelligent decision-making and a wide range of Artificial Intelligence (AI) services across major corporations such as Google, Walmart, and AirBnb. KGs complement Machine Learning (ML) algorithms by providing data context and semantics, thereby enabling further inference and question-answering capabilities. The integration of KGs with neuronal learning (e.g., Large Language Models (LLMs)) is currently a topic of active research, commonly named neuro-symbolic AI. Despite the numerous benefits that can be accomplished with KG-based AI, its growing ubiquity within online services may result in the loss of self-determination for citizens as a fundamental societal issue. The more we rely on these technologies, which are often centralised, the less citizens will be able to determine their own destinies. To counter this threat, AI regulation, such as the European Union (EU) AI Act, is being proposed in certain regions. The regulation sets what technologists need to do, leading to questions concerning How the output of AI systems can be trusted? What is needed to ensure that the data fuelling and the inner workings of these artefacts are transparent? How can AI be made accountable for its decision-making? This paper conceptualises the foundational topics and research pillars to support KG-based AI for self-determination. Drawing upon this conceptual framework, challenges and opportunities for citizen self-determination are illustrated and analysed in a real-world scenario. As a result, we propose a research agenda aimed at accomplishing the recommended objectives.
Cite as

Luis-Daniel Ibáñez, John Domingue, Sabrina Kirrane, Oshani Seneviratne, Aisling Third, and Maria-Esther Vidal. Trust, Accountability, and Autonomy in Knowledge Graph-Based AI for Self-Determination. In Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge (TGDK), Volume 1, Issue 1, pp. 9:1-9:32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{ibanez_et_al:TGDK.1.1.9,
  author =	{Ib\'{a}\~{n}ez, Luis-Daniel and Domingue, John and Kirrane, Sabrina and Seneviratne, Oshani and Third, Aisling and Vidal, Maria-Esther},
  title =	{{Trust, Accountability, and Autonomy in Knowledge Graph-Based AI for Self-Determination}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{9:1--9:32},
  ISSN =	{2942-7517},
  year =	{2023},
  volume =	{1},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.1.1.9},
  URN =		{urn:nbn:de:0030-drops-194839},
  doi =		{10.4230/TGDK.1.1.9},
  annote =	{Keywords: Trust, Accountability, Autonomy, AI, Knowledge Graphs}
}
Document
DOI: 10.4230/LITES-v002-i002-a001
From Dataflow Specification to Multiprocessor Partitioned Time-triggered Real-time Implementation

Authors: Thomas Carle, Dumitru Potop-Butucaru, Yves Sorel, and David Lesens

Published in: LITES, Volume 2, Issue 2 (2015). Leibniz Transactions on Embedded Systems, Volume 2, Issue 2

Abstract
Our objective is to facilitate the development of complex time-triggered systems by automating the allocation and scheduling steps. We show that full automation is possible while taking into account the elements of complexity needed by a complex embedded control system. More precisely, we consider deterministic functional specifications provided (as often in an industrial setting) by means of synchronous data-flow models with multiple modes and multiple relative periods. We first extend this functional model with an original real-time characterization that takes advantage of our time-triggered framework to provide a simpler representation of complex end-to-end flow requirements. We also extend our specifications with additional non-functional properties specifying partitioning, allocation, and preemptability constraints. Then, we provide novel algorithms for the off-line scheduling of these extended specifications onto partitioned time-triggered architectures à la ARINC 653. The main originality of our work is that it takes into account at the same time multiple complexity elements: various types of non-functional properties (real-time, partitioning, allocation, preemptability) and functional specifications with conditional execution and multiple modes. Allocation of time slots/windows to partitions can be fully or partially provided, or synthesized by our tool. Our algorithms allow the automatic allocation and scheduling onto multi-processor (distributed) systems with a global time base, taking into account communication costs. We demonstrate our technique on a model of space flight software system with strong real-time determinism requirements.
Cite as

Thomas Carle, Dumitru Potop-Butucaru, Yves Sorel, and David Lesens. From Dataflow Specification to Multiprocessor Partitioned Time-triggered Real-time Implementation. In LITES, Volume 2, Issue 2 (2015). Leibniz Transactions on Embedded Systems, Volume 2, Issue 2, pp. 01:1-01:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Article{carle_et_al:LITES-v002-i002-a001,
  author =	{Carle, Thomas and Potop-Butucaru, Dumitru and Sorel, Yves and Lesens, David},
  title =	{{From Dataflow Specification to Multiprocessor Partitioned Time-triggered Real-time Implementation}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{01:1--01:30},
  ISSN =	{2199-2002},
  year =	{2015},
  volume =	{2},
  number =	{2},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES-v002-i002-a001},
  URN =		{urn:nbn:de:0030-drops-192540},
  doi =		{10.4230/LITES-v002-i002-a001},
  annote =	{Keywords: Time-triggered, Off-line real-time scheduling, Temporal partitioning}
}
Document
DOI: 10.4230/DagRep.3.11.117
Synchronous Programming (Dagstuhl Seminar 13471)

Authors: Stephen A. Edwards, Alain Girault, and Klaus Schneider

Published in: Dagstuhl Reports, Volume 3, Issue 11 (2014)

Abstract
Synchronous programming languages are programming languages with an abstract (logical) notion of time: The execution of such programs is divided into discrete reaction steps, and in each of these reactions steps, the program reads new inputs and reacts by computing corresponding outputs of the considered reaction step. The programs are called synchronous because all outputs are computed together in zero time within a step and because parallel components synchronize their reaction steps by the semantics of the languages. For this reason, the synchronous composition is deterministic, which is a great advantage concerning predictability, verification of system design, and embedded code generation. Starting with the definition of the classic synchronous languages Esterel, Lustre and Signal in the late 1980's, the research during the past 20 years was very fruitful and lead to new languages, compilation techniques, software and hardware architectures, as well as extensions, transformations, and interfaces to other models of computations, in particular to asynchronous and hybrid systems. This report is a summary of the Dagstuhl Seminar 13471 "Synchronous Programming", which took place during November 18-22, 2013, and which was the 20th edition of the yearly workshop of the synchronous programming community. The report contains the abstracts of the presentations given during the seminar in addition to the documents provided by the participants on the web pages of the seminar.
Cite as

Stephen A. Edwards, Alain Girault, and Klaus Schneider. Synchronous Programming (Dagstuhl Seminar 13471). In Dagstuhl Reports, Volume 3, Issue 11, pp. 117-143, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Article{edwards_et_al:DagRep.3.11.117,
  author =	{Edwards, Stephen A. and Girault, Alain and Schneider, Klaus},
  title =	{{Synchronous Programming (Dagstuhl Seminar 13471)}},
  pages =	{117--143},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2014},
  volume =	{3},
  number =	{11},
  editor =	{Edwards, Stephen A. and Girault, Alain and Schneider, Klaus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.3.11.117},
  URN =		{urn:nbn:de:0030-drops-44395},
  doi =		{10.4230/DagRep.3.11.117},
  annote =	{Keywords: Synchronous Languages, Hybrid Systems, Formal Verification, Models of Computation, WCET-Analysis, Embedded Systems}
}
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}
}
  • Refine by Type
  • 21 Document/PDF
  • 11 Document/HTML

  • Refine by Publication Year
  • 11 2025
  • 1 2023
  • 1 2015
  • 1 2014
  • 1 2010
  • Show More...

  • Refine by Author
  • 5 Edwards, Stephen A.
  • 5 von Hanxleden, Reinhard
  • 2 Halbwachs, Nicholas
  • 2 Schneider, Klaus
  • 2 Stauner, Thomas
  • Show More...

  • Refine by Series/Journal
  • 4 LIPIcs
  • 6 OASIcs
  • 2 LITES
  • 1 TGDK
  • 1 DagRep
  • Show More...

  • Refine by Classification
  • 2 Social and professional topics → Computing education
  • 2 Software and its engineering → Runtime environments
  • 1 Computer systems organization
  • 1 Computer systems organization → Embedded and cyber-physical systems
  • 1 Computer systems organization → Real-time languages
  • Show More...

  • Refine by Keyword
  • 4 Esterel
  • 3 Synchronous languages
  • 2 Lustre
  • 2 Synchronous Languages
  • 2 executive summary
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact