41 Search Results for "May, Alexander"


Document
Invited Talk
How Database Theory Helps Teach Relational Queries in Database Education (Invited Talk)

Authors: Sudeepa Roy, Amir Gilad, Yihao Hu, Hanze Meng, Zhengjie Miao, Kristin Stephens-Martinez, and Jun Yang

Published in: LIPIcs, Volume 290, 27th International Conference on Database Theory (ICDT 2024)


Abstract
Data analytics skills have become an indispensable part of any education that seeks to prepare its students for the modern workforce. Essential in this skill set is the ability to work with structured relational data. Relational queries are based on logic and may be declarative in nature, posing new challenges to novices and students. Manual teaching resources being limited and enrollment growing rapidly, automated tools that help students debug queries and explain errors are potential game-changers in database education. We present a suite of tools built on the foundations of database theory that has been used by over 1600 students in database classes at Duke University, showcasing a high-impact application of database theory in database education.

Cite as

Sudeepa Roy, Amir Gilad, Yihao Hu, Hanze Meng, Zhengjie Miao, Kristin Stephens-Martinez, and Jun Yang. How Database Theory Helps Teach Relational Queries in Database Education (Invited Talk). In 27th International Conference on Database Theory (ICDT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 290, pp. 2:1-2:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{roy_et_al:LIPIcs.ICDT.2024.2,
  author =	{Roy, Sudeepa and Gilad, Amir and Hu, Yihao and Meng, Hanze and Miao, Zhengjie and Stephens-Martinez, Kristin and Yang, Jun},
  title =	{{How Database Theory Helps Teach Relational Queries in Database Education}},
  booktitle =	{27th International Conference on Database Theory (ICDT 2024)},
  pages =	{2:1--2:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-312-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{290},
  editor =	{Cormode, Graham and Shekelyan, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2024.2},
  URN =		{urn:nbn:de:0030-drops-197841},
  doi =		{10.4230/LIPIcs.ICDT.2024.2},
  annote =	{Keywords: Query Debugging, SQL, Relational Algebra, Relational Calculus, Database Education, Boolean Provenance}
}
Document
Non-Clairvoyant Makespan Minimization Scheduling with Predictions

Authors: Evripidis Bampis, Alexander Kononov, Giorgio Lucarelli, and Fanny Pascual

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)


Abstract
We revisit the classical non-clairvoyant problem of scheduling a set of n jobs on a set of m parallel identical machines where the processing time of a job is not known until the job finishes. Our objective is the minimization of the makespan, i.e., the date at which the last job terminates its execution. We adopt the framework of learning-augmented algorithms and we study the question of whether (possibly erroneous) predictions may help design algorithms with a competitive ratio which is good when the prediction is accurate (consistency), deteriorates gradually with respect to the prediction error (smoothness), and not too bad and bounded when the prediction is arbitrarily bad (robustness). We first consider the non-preemptive case and we devise lower bounds, as a function of the error of the prediction, for any deterministic learning-augmented algorithm. Then we analyze a variant of Longest Processing Time first (LPT) algorithm (with and without release dates) and we prove that it is consistent, smooth, and robust. Furthermore, we study the preemptive case and we provide lower bounds for any deterministic algorithm with predictions as a function of the prediction error. Finally, we introduce a variant of the classical Round Robin algorithm (RR), the Predicted Proportional Round Robin algorithm (PPRR), which we prove to be consistent, smooth and robust.

Cite as

Evripidis Bampis, Alexander Kononov, Giorgio Lucarelli, and Fanny Pascual. Non-Clairvoyant Makespan Minimization Scheduling with Predictions. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 9:1-9:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{bampis_et_al:LIPIcs.ISAAC.2023.9,
  author =	{Bampis, Evripidis and Kononov, Alexander and Lucarelli, Giorgio and Pascual, Fanny},
  title =	{{Non-Clairvoyant Makespan Minimization Scheduling with Predictions}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{9:1--9:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.9},
  URN =		{urn:nbn:de:0030-drops-193114},
  doi =		{10.4230/LIPIcs.ISAAC.2023.9},
  annote =	{Keywords: scheduling, online, learning-augmented algorithm}
}
Document
Analyzing Complex Systems with Cascades Using Continuous-Time Bayesian Networks

Authors: Alessandro Bregoli, Karin Rathsman, Marco Scutari, Fabio Stella, and Søren Wengel Mogensen

Published in: LIPIcs, Volume 278, 30th International Symposium on Temporal Representation and Reasoning (TIME 2023)


Abstract
Interacting systems of events may exhibit cascading behavior where events tend to be temporally clustered. While the cascades themselves may be obvious from the data, it is important to understand which states of the system trigger them. For this purpose, we propose a modeling framework based on continuous-time Bayesian networks (CTBNs) to analyze cascading behavior in complex systems. This framework allows us to describe how events propagate through the system and to identify likely sentry states, that is, system states that may lead to imminent cascading behavior. Moreover, CTBNs have a simple graphical representation and provide interpretable outputs, both of which are important when communicating with domain experts. We also develop new methods for knowledge extraction from CTBNs and we apply the proposed methodology to a data set of alarms in a large industrial system.

Cite as

Alessandro Bregoli, Karin Rathsman, Marco Scutari, Fabio Stella, and Søren Wengel Mogensen. Analyzing Complex Systems with Cascades Using Continuous-Time Bayesian Networks. In 30th International Symposium on Temporal Representation and Reasoning (TIME 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 278, pp. 8:1-8:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{bregoli_et_al:LIPIcs.TIME.2023.8,
  author =	{Bregoli, Alessandro and Rathsman, Karin and Scutari, Marco and Stella, Fabio and Mogensen, S{\o}ren Wengel},
  title =	{{Analyzing Complex Systems with Cascades Using Continuous-Time Bayesian Networks}},
  booktitle =	{30th International Symposium on Temporal Representation and Reasoning (TIME 2023)},
  pages =	{8:1--8:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-298-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{278},
  editor =	{Artikis, Alexander and Bruse, Florian and Hunsberger, Luke},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2023.8},
  URN =		{urn:nbn:de:0030-drops-190980},
  doi =		{10.4230/LIPIcs.TIME.2023.8},
  annote =	{Keywords: event model, continuous-time Bayesian network, alarm network, graphical models, event cascade}
}
Document
Extended Abstract
A Decomposition Framework for Inconsistency Handling in Qualitative Spatial and Temporal Reasoning (Extended Abstract)

Authors: Yakoub Salhi and Michael Sioutis

Published in: LIPIcs, Volume 278, 30th International Symposium on Temporal Representation and Reasoning (TIME 2023)


Abstract
Dealing with inconsistency is a central problem in AI, due to the fact that inconsistency can arise for many reasons in real-world applications, such as context dependency, multi-source information, vagueness, noisy data, etc. Among the approaches that are involved in inconsistency handling, we can mention argumentation, non-monotonic reasoning, and paraconsistency, e.g., see [Philippe Besnard and Anthony Hunter, 2008; Gerhard Brewka et al., 1997; Koji Tanaka et al., 2013]. In the work of [Yakoub Salhi and Michael Sioutis, 2023], we are interested in dealing with inconsistency in the context of Qualitative Spatio-Temporal Reasoning (QSTR) [Ligozat, 2013]. QSTR is an AI framework that aims to mimic, natural, human-like representation and reasoning regarding space and time. This framework is applied to a variety of domains, such as qualitative case-based reasoning and learning [Thiago Pedro Donadon Homem et al., 2020] and visual sensemaking [Jakob Suchan et al., 2021]; the interested reader is referred to [Michael Sioutis and Diedrich Wolter, 2021] for a recent survey. Motivation. In [Yakoub Salhi and Michael Sioutis, 2023], we study the decomposition of an inconsistent constraint network into consistent subnetworks under, possible, mandatory constraints. To illustrate the interest of such a decomposition, we provide a simple example described in Figure 1. The QCN depicted in the top part of the figure corresponds to a description of an inconsistent plan. Further, we assume that the constraint Task A {before} Task B is mandatory. To handle inconsistency, this plan can be transformed into a decomposition of two consistent plans, depicted in the bottom part of the figure; this decomposition can be used, e.g., to capture the fact that Task C must be performed twice. More generally, network decomposition can be involved in inconsistency handling in several ways: it can be used to identify potential contexts that explain the presence of inconsistent information; it can also be used to restore consistency through a compromise between the components of a decomposition, e.g., by using belief merging [Jean-François Condotta et al., 2010]; in addition, QCN decomposition can be used as the basis for defining inconsistency measures. Contributions. We summarize the contributions of [Yakoub Salhi and Michael Sioutis, 2023] as follows. First, we propose a theoretical study of a problem that consists in decomposing an inconsistent QCN into a bounded number of consistent QCNs that may satisfy a specified part in the original QCN; intuitively, the required common part corresponds to the constraints that are considered necessary, if any. To this end, we provide upper bounds for the minimum number of components in a decomposition as well as computational complexity results. Secondly, we provide two methods for solving our decomposition problem. The first method corresponds to a greedy constraint-based algorithm, a variant of which involves the use of spanning trees; the basic idea of this variant is that any acyclic constraint graph in QSTR is consistent, and such a graph can be used as a starting point for building consistent components. The second method corresponds to a SAT-based encoding; every model of this encoding is used to construct a valid decomposition. Thirdly, we consider two optimization versions of the initial decomposition problem that focus on minimizing the number of components and maximizing the similarity between components, respectively. The similarity between two QCNs is quantified by the number of common non-universal constraints; the interest in maximizing the similarity lies mainly in the fact that it reduces the number of constraints that allow each component to be distinguished from the rest. Of course, our previous methods are adapted to tackle these optimization versions, too. Additionally, we introduce two inconsistency measures based on QCN decomposition, which can be seen as counterparts of measures for propositional KBs introduced in [Matthias Thimm, 2016; Meriem Ammoura et al., 2017], and show that they satisfy several desired properties in the literature. Finally, we provide implementations of our methods for computing decompositions and experimentally evaluate them using different metrics.

Cite as

Yakoub Salhi and Michael Sioutis. A Decomposition Framework for Inconsistency Handling in Qualitative Spatial and Temporal Reasoning (Extended Abstract). In 30th International Symposium on Temporal Representation and Reasoning (TIME 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 278, pp. 16:1-16:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{salhi_et_al:LIPIcs.TIME.2023.16,
  author =	{Salhi, Yakoub and Sioutis, Michael},
  title =	{{A Decomposition Framework for Inconsistency Handling in Qualitative Spatial and Temporal Reasoning}},
  booktitle =	{30th International Symposium on Temporal Representation and Reasoning (TIME 2023)},
  pages =	{16:1--16:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-298-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{278},
  editor =	{Artikis, Alexander and Bruse, Florian and Hunsberger, Luke},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2023.16},
  URN =		{urn:nbn:de:0030-drops-191062},
  doi =		{10.4230/LIPIcs.TIME.2023.16},
  annote =	{Keywords: Spatial and Temporal Reasoning, Qualitative Constraints, Inconsistency Handling, Decomposition, Inconsistency Measures}
}
Document
Extended Abstract
A Benchmark for Early Time-Series Classification (Extended Abstract)

Authors: Petro-Foti Kamberi, Evgenios Kladis, and Charilaos Akasiadis

Published in: LIPIcs, Volume 278, 30th International Symposium on Temporal Representation and Reasoning (TIME 2023)


Abstract
The objective of Early Time-Series Classification (ETSC) is to predict the class of incoming time-series by observing the fewest time-points possible. Although many approaches have been proposed in the past, not all techniques are suitable for every problem type. In particular, the characteristics of the input data may impact performance. To aid researchers and developers with deciding which kind of method suits their needs best, we developed a framework that allows the comparison of five existing ETSC algorithms, and also introduce a new method that is based on the selective truncation of time-series principle. To promote results reproducibility and the alignment of algorithm comparisons, we also include a bundle of datasets originating from real-world time-critical applications, and for which the application of ETSC algorithms can be considered quite valuable.

Cite as

Petro-Foti Kamberi, Evgenios Kladis, and Charilaos Akasiadis. A Benchmark for Early Time-Series Classification (Extended Abstract). In 30th International Symposium on Temporal Representation and Reasoning (TIME 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 278, pp. 18:1-18:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{kamberi_et_al:LIPIcs.TIME.2023.18,
  author =	{Kamberi, Petro-Foti and Kladis, Evgenios and Akasiadis, Charilaos},
  title =	{{A Benchmark for Early Time-Series Classification}},
  booktitle =	{30th International Symposium on Temporal Representation and Reasoning (TIME 2023)},
  pages =	{18:1--18:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-298-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{278},
  editor =	{Artikis, Alexander and Bruse, Florian and Hunsberger, Luke},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2023.18},
  URN =		{urn:nbn:de:0030-drops-191084},
  doi =		{10.4230/LIPIcs.TIME.2023.18},
  annote =	{Keywords: Time-series analysis, Classification, Benchmark}
}
Document
Extended Abstract
Converting Simple Temporal Networks with Uncertainty into Dispatchable Form - Faster (Extended Abstract)

Authors: Luke Hunsberger and Roberto Posenato

Published in: LIPIcs, Volume 278, 30th International Symposium on Temporal Representation and Reasoning (TIME 2023)


Abstract
In many sectors of real-world industry, it is necessary to plan and schedule tasks allocated to agents participating in complex processes. Temporal planning aims to schedule tasks while respecting temporal constraints such as release times, maximum durations, and deadlines, which requires quantitative temporal reasoning. Over the years, several major application developers have highlighted the need for the explicit representation of actions with uncertain durations; efficient algorithms for determining whether plans involving such actions are controllable; and efficient algorithms for converting such plans into forms that enable them to be executed in real time with minimal computation, while preserving maximum flexibility. A Simple Temporal Network with Uncertainty (STNU) is a data structure for reasoning about time constraints on actions that may have uncertain durations. An STNU is a triple (𝒯, 𝒞, ℒ) where 𝒯 is a set of real-valued variables called timepoints, 𝒞 is a set of constraints of the form Y-X ≤ δ, where X, Y ∈ 𝒯 and δ ∈ 𝐑, and ℒ is a set of contingent links of the form (A,x,y,C), where A,C ∈ 𝒯 and 0 < x < y < ∞. A contingent link (A,x,y,C) represents an uncertain duration where A is the activation timepoint, C is the contingent timepoint, and y-x is the uncertainty in the duration C-A. Typically, an executor controls the execution of A, but only observes the execution of C in real time. Although uncontrollable, the duration is guaranteed to satisfy C-A ∈ [x,y]. We let n = |𝒯|, m = |𝒞| and k = |ℒ|. An STNU graph is a pair (𝒯, ℰ), where the timepoints in 𝒯 serve as nodes in the graph, and the edges in ℰ correspond to the constraints in 𝒞 and contingent links in ℒ. For each Y-X ≤ δ in 𝒞, ℰ contains an ordinary edge X-δ->Y. For each (A,x,y,C) ∈ ℒ, ℰ contains a lower-case (LC) edge, A-c:y->C, and an upper-case (UC) edge, C-C:-y->A, representing the respective possibilities that C-A might take its minimum or maximum value. The LO-edges are the LC or ordinary edges; the OU-edges are the ordinary or UC edges. For any STNU, it is important to determine whether it is dynamically controllable (DC) (i.e., whether it is possible, in real time, to schedule its non-contingent timepoints such that all constraints will necessarily be satisfied no matter what durations turn out for the contingent links). Polynomial-time algorithms are available to solve this DC-checking problem. Each uses rules to generate new edges aiming to bypass certain kinds of edges in the STNU graph. Morris' O(n⁴)-time DC-checking algorithm [Paul Morris, 2006] starts from LC edges, propagating forward along OU-edges, looking for opportunities to generate new OU-edges that bypass the LC edges. Morris' O(n³)-time algorithm [Morris, 2014] starts from negative OU-edges, propagating backward along LO-edges, aiming to bypass negative edges with non-negative edges. The O(mn+k²n + knlog n)-time RUL¯ algorithm [Massimo Cairo et al., 2018] starts from UC edges, propagating backward along LO-edges, aiming to bypass UC edges with ordinary edges. After propagating, each algorithm checks for certain kinds of negative cycles to decide DC-vs.-non-DC. However, being DC only asserts the existence of a dynamic scheduler. It is also crucial to be able to execute a DC STNU efficiently in real time. For maximum flexibility and minimal space and time requirements, a dynamic scheduler for an STNU is typically computed incrementally, in real time, so that it can react to observations of contingent executions as they occur. An efficient dynamic scheduler can be realized by first transforming an STNU into an equivalent dispatchable form [Muscettola et al., 1998; Ioannis Tsamardinos et al., 1998]. Then, to execute the dispatchable STNU, it suffices to maintain time-windows for each timepoint and, as each timepoint X is executed, only updating time-windows for neighbors of X in the graph. Dispatchable STNUs are very important in applications that demand quick responses to observations of contingent events. Of the existing DC-checking algorithms, only Morris' O(n³)-time algorithm necessarily generates a dispatchable STNU for DC inputs. This abstract describes a faster, O(mn + kn² + n² log n)-time algorithm for converting DC STNUs into dispatchable form. (The full journal article is available elsewhere [Luke Hunsberger and Roberto Posenato, 2023].) This improvement is significant for applications (e.g., modeling business processes) where networks are typically sparse. For example, if m = O(n log n) and k = O(log n), then our algorithm runs in O(n²log n) ≪ O(n³) time. Our new Fast Dispatch algorithm, FD_STNU, has three phases. The first phase is similar to the RUL¯ DC-checking algorithm, but generates an order-of-magnitude fewer edges overall, while also generating new UC edges that correspond to wait constraints. The second phase is a version of Morris' 2006 algorithm that propagates forward from LC edges, but only along LO-edges, aiming to generate ordinary bypass edges. The third phase focuses on the subgraph of ordinary edges, which comprise a Simple Temporal Network (STN). It uses an existing dispatchability algorithm for STNs [Ioannis Tsamardinos et al., 1998] to convert that ordinary subgraph into a dispatchable STN. After completing the three phases, the STNU is guaranteed to be dispatchable. We provide the source code of a Java implementation of the considered algorithms (Morris, RUL¯, and FD_STNU) [Posenato, 2022] and the benchmarks used to compare their performances.

Cite as

Luke Hunsberger and Roberto Posenato. Converting Simple Temporal Networks with Uncertainty into Dispatchable Form - Faster (Extended Abstract). In 30th International Symposium on Temporal Representation and Reasoning (TIME 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 278, pp. 20:1-20:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{hunsberger_et_al:LIPIcs.TIME.2023.20,
  author =	{Hunsberger, Luke and Posenato, Roberto},
  title =	{{Converting Simple Temporal Networks with Uncertainty into Dispatchable Form - Faster}},
  booktitle =	{30th International Symposium on Temporal Representation and Reasoning (TIME 2023)},
  pages =	{20:1--20:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-298-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{278},
  editor =	{Artikis, Alexander and Bruse, Florian and Hunsberger, Luke},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2023.20},
  URN =		{urn:nbn:de:0030-drops-191104},
  doi =		{10.4230/LIPIcs.TIME.2023.20},
  annote =	{Keywords: Temporal constraint networks, contingent durations, dispatchable network}
}
Document
Quality of Sustainable Experience (QoSE) (Dagstuhl Seminar 23042)

Authors: Katrien De Moor, Markus Fiedler, Ashok Jhunjhunwala, and Alexander Raake

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


Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 23042 "Quality of Sustainable Experience (QoSE)". The seminar aimed to bring together people from different fields, perspectives and backgrounds. The participants discussed how experiences - as the main selling point of products and services – in various ICT-related domains can be made more sustainable, how they can contribute to relevant sustainable development goals, and how the quality and degree of sustainability of such experiences may be evaluated and be better understood. The main objectives of the seminar were to foster new alliances, to inspire, to trigger scientific renewal, as well as to identify future opportunities and research challenges through a hands-on approach.

Cite as

Katrien De Moor, Markus Fiedler, Ashok Jhunjhunwala, and Alexander Raake. Quality of Sustainable Experience (QoSE) (Dagstuhl Seminar 23042). In Dagstuhl Reports, Volume 13, Issue 1, pp. 184-215, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@Article{demoor_et_al:DagRep.13.1.184,
  author =	{De Moor, Katrien and Fiedler, Markus and Jhunjhunwala, Ashok and Raake, Alexander},
  title =	{{Quality of Sustainable Experience (QoSE) (Dagstuhl Seminar 23042)}},
  pages =	{184--215},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2023},
  volume =	{13},
  number =	{1},
  editor =	{De Moor, Katrien and Fiedler, Markus and Jhunjhunwala, Ashok and Raake, Alexander},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.13.1.184},
  URN =		{urn:nbn:de:0030-drops-191212},
  doi =		{10.4230/DagRep.13.1.184},
  annote =	{Keywords: Design for Sustainability, Digitalisation, Human-Computer Interaction, Information and Communication Technology, Wellbeing}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
Action Codes

Authors: Frits Vaandrager and Thorsten Wißmann

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)


Abstract
We provide a new perspective on the problem how high-level state machine models with abstract actions can be related to low-level models in which these actions are refined by sequences of concrete actions. We describe the connection between high-level and low-level actions using action codes, a variation of the prefix codes known from coding theory. For each action code ℛ, we introduce a contraction operator α_ℛ that turns a low-level model ℳ into a high-level model, and a refinement operator ϱ_ℛ that transforms a high-level model 𝒩 into a low-level model. We establish a Galois connection ϱ_ℛ(𝒩) ⊑ ℳ ⇔ 𝒩 ⊑ α_ℛ(ℳ), where ⊑ is the well-known simulation preorder. For conformance, we typically want to obtain an overapproximation of model ℳ. To this end, we also introduce a concretization operator γ_ℛ, which behaves like the refinement operator but adds arbitrary behavior at intermediate points, giving us a second Galois connection α_ℛ(ℳ) ⊑ 𝒩 ⇔ ℳ ⊑ γ_ℛ(𝒩). Action codes may be used to construct adaptors that translate between concrete and abstract actions during learning and testing of Mealy machines. If Mealy machine ℳ models a black-box system then α_ℛ(ℳ) describes the behavior that can be observed by a learner/tester that interacts with this system via an adaptor derived from code ℛ. Whenever α_ℛ(ℳ) implements (or conforms to) 𝒩, we may conclude that ℳ implements (or conforms to) γ_ℛ (𝒩). Almost all results, examples, and counter-examples are formalized in Coq.

Cite as

Frits Vaandrager and Thorsten Wißmann. Action Codes. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 137:1-137:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{vaandrager_et_al:LIPIcs.ICALP.2023.137,
  author =	{Vaandrager, Frits and Wi{\ss}mann, Thorsten},
  title =	{{Action Codes}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{137:1--137:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.137},
  URN =		{urn:nbn:de:0030-drops-181895},
  doi =		{10.4230/LIPIcs.ICALP.2023.137},
  annote =	{Keywords: Automata, Models of Reactive Systems, LTS, Action Codes, Action Refinement, Action Contraction, Galois Connection, Model-Based Testing, Model Learning}
}
Document
Delay Management with Integrated Decisions on the Vehicle Circulations

Authors: Vera Grafe, Alexander Schiewe, and Anita Schöbel

Published in: OASIcs, Volume 106, 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)


Abstract
The task of delay management in public transport is to decide whether a vehicle should wait for a delayed vehicle in order to maintain the connection for transferring passengers. So far, the vehicle circulations are often ignored in the optimization process, although they have an influence on the propagation of the delay through the network. In this paper we consider different ways from literature to incorporate vehicle circulations in the delay management stage of public transport planning. Since the IP formulation for the integrated problem is hard to solve, we investigate bounds and develop several heuristics for the integrated problem. Our experiments on close-to real-world instances show that integrating delay management and decisions on vehicle circulations may reduce the overall delay by up to 39 percent. We also compare the runtimes and objective function values of the different heuristics. We conclude that we can find competitive solutions in a reasonable amount of time.

Cite as

Vera Grafe, Alexander Schiewe, and Anita Schöbel. Delay Management with Integrated Decisions on the Vehicle Circulations. In 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022). Open Access Series in Informatics (OASIcs), Volume 106, pp. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{grafe_et_al:OASIcs.ATMOS.2022.7,
  author =	{Grafe, Vera and Schiewe, Alexander and Sch\"{o}bel, Anita},
  title =	{{Delay Management with Integrated Decisions on the Vehicle Circulations}},
  booktitle =	{22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)},
  pages =	{7:1--7:18},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-259-4},
  ISSN =	{2190-6807},
  year =	{2022},
  volume =	{106},
  editor =	{D'Emidio, Mattia and Lindner, Niels},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2022.7},
  URN =		{urn:nbn:de:0030-drops-171119},
  doi =		{10.4230/OASIcs.ATMOS.2022.7},
  annote =	{Keywords: Public Transport, Delay Management, Vehicle Circulations, Integer Programming}
}
Document
SAT-Based Circuit Local Improvement

Authors: Alexander S. Kulikov, Danila Pechenev, and Nikita Slezkin

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)


Abstract
Finding exact circuit size is notoriously hard. Whereas modern computers and algorithmic techniques allow to find a circuit of size seven in the blink of an eye, it may take more than a week to search for a circuit of size thirteen. One of the reasons of this behavior is that the search space is enormous: the number of circuits of size s is s^Θ(s), the number of Boolean functions on n variables is 2^(2ⁿ). In this paper, we explore the following natural heuristic idea for decreasing the size of a given circuit: go through all its subcircuits of moderate size and check whether any of them can be improved by reducing to SAT. This may be viewed as a local search approach: we search for a smaller circuit in a ball around a given circuit. Through this approach, we prove new upper bounds on the circuit size of various symmetric functions. We also demonstrate that some upper bounds that were proved by hand decades ago, can nowadays be found automatically in a few seconds.

Cite as

Alexander S. Kulikov, Danila Pechenev, and Nikita Slezkin. SAT-Based Circuit Local Improvement. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 67:1-67:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{kulikov_et_al:LIPIcs.MFCS.2022.67,
  author =	{Kulikov, Alexander S. and Pechenev, Danila and Slezkin, Nikita},
  title =	{{SAT-Based Circuit Local Improvement}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{67:1--67:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.67},
  URN =		{urn:nbn:de:0030-drops-168659},
  doi =		{10.4230/LIPIcs.MFCS.2022.67},
  annote =	{Keywords: circuits, algorithms, complexity theory, SAT, SAT solvers, heuristics}
}
Document
Explaining Propagation for Gini and Spread with Variable Mean

Authors: Alexander Ek, Andreas Schutt, Peter J. Stuckey, and Guido Tack

Published in: LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)


Abstract
In optimisation problems involving multiple agents (stakeholders) we often want to make sure that the solution is balanced and fair. That is, we want to maximise total utility subject to an upper bound on the statistical dispersion (e.g., spread or the Gini coefficient) of the utility given to different agents, or minimise dispersion subject to some lower bounds on utility. These needs arise in, for example, balancing tardiness in scheduling, unwanted shifts in rostering, and desired resources in resource allocation, or minimising deviation from a baseline in schedule repair, to name a few. These problems are often quite challenging. To solve them efficiently we want to effectively reason about dispersion. Previous work has studied the case where the mean is fixed, but this may not be possible for many problems, e.g., scheduling where total utility depends on the final schedule. In this paper we introduce two log-linear-time dispersion propagators - (a) spread (variance, and indirectly standard deviation) and (b) the Gini coefficient - capable of explaining their propagations, thus allowing effective clause learning solvers to be applied to these problems. Propagators for (a) exist in the literature but do not explain themselves, while propagators for (b) have not been previously studied. We avoid introducing floating-point variables, which are usually not supported by learning solvers, by reasoning about scaled, integer versions of the constraints. We show through experimentation that clause learning can substantially improve the solving of problems where we want to bound dispersion and optimise total utility and vice versa.

Cite as

Alexander Ek, Andreas Schutt, Peter J. Stuckey, and Guido Tack. Explaining Propagation for Gini and Spread with Variable Mean. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 21:1-21:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{ek_et_al:LIPIcs.CP.2022.21,
  author =	{Ek, Alexander and Schutt, Andreas and Stuckey, Peter J. and Tack, Guido},
  title =	{{Explaining Propagation for Gini and Spread with Variable Mean}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{21:1--21:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-240-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{235},
  editor =	{Solnon, Christine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2022.21},
  URN =		{urn:nbn:de:0030-drops-166503},
  doi =		{10.4230/LIPIcs.CP.2022.21},
  annote =	{Keywords: Spread constraint, Gini index, Filtering algorithm, Constraint programming, Lazy clause generation}
}
Document
Pseudorandom Generators, Resolution and Heavy Width

Authors: Dmitry Sokolov

Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)


Abstract
Following the paper of Alekhnovich, Ben-Sasson, Razborov, Wigderson [Michael Alekhnovich et al., 2004] we call a pseudorandom generator ℱ:{0, 1}ⁿ → {0, 1}^m hard for a propositional proof system P if P cannot efficiently prove the (properly encoded) statement b ∉ Im(ℱ) for any string b ∈ {0, 1}^m. In [Michael Alekhnovich et al., 2004] the authors suggested the "functional encoding" of the considered statement for Nisan-Wigderson generator that allows the introduction of "local" extension variables. These extension variables may potentially significantly increase the power of the proof system. In [Michael Alekhnovich et al., 2004] authors gave a lower bound of exp[Ω(n²/{m⋅2^{2^Δ}})] on the length of Resolution proofs where Δ is the degree of the dependency graph of the generator. This lower bound meets the barrier for the restriction technique. In this paper, we introduce a "heavy width" measure for Resolution that allows us to show a lower bound of exp[n²/{m 2^𝒪(εΔ)}] on the length of Resolution proofs of the considered statement for the Nisan-Wigderson generator. This gives an exponential lower bound up to Δ := log^{2 - δ} n (the bigger degree the more extension variables we can use). In [Michael Alekhnovich et al., 2004] authors left an open problem to get rid of scaling factor 2^{2^Δ}, it is a solution to this open problem.

Cite as

Dmitry Sokolov. Pseudorandom Generators, Resolution and Heavy Width. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 15:1-15:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{sokolov:LIPIcs.CCC.2022.15,
  author =	{Sokolov, Dmitry},
  title =	{{Pseudorandom Generators, Resolution and Heavy Width}},
  booktitle =	{37th Computational Complexity Conference (CCC 2022)},
  pages =	{15:1--15:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-241-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{234},
  editor =	{Lovett, Shachar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.15},
  URN =		{urn:nbn:de:0030-drops-165770},
  doi =		{10.4230/LIPIcs.CCC.2022.15},
  annote =	{Keywords: proof complexity, pseudorandom generators, resolution, lower bounds}
}
Document
Syntactic Minimization Of Nondeterministic Finite Automata

Authors: Robert S. R. Myers and Henning Urbat

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)


Abstract
Nondeterministic automata may be viewed as succinct programs implementing deterministic automata, i.e. complete specifications. Converting a given deterministic automaton into a small nondeterministic one is known to be computationally very hard; in fact, the ensuing decision problem is PSPACE-complete. This paper stands in stark contrast to the status quo. We restrict attention to subatomic nondeterministic automata, whose individual states accept unions of syntactic congruence classes. They are general enough to cover almost all structural results concerning nondeterministic state-minimality. We prove that converting a monoid recognizing a regular language into a small subatomic acceptor corresponds to an NP-complete problem. The NP certificates are solutions of simple equations involving relations over the syntactic monoid. We also consider the subclass of atomic nondeterministic automata introduced by Brzozowski and Tamm. Given a deterministic automaton and another one for the reversed language, computing small atomic acceptors is shown to be NP-complete with analogous certificates. Our complexity results emerge from an algebraic characterization of (sub)atomic acceptors in terms of deterministic automata with semilattice structure, combined with an equivalence of categories leading to succinct representations.

Cite as

Robert S. R. Myers and Henning Urbat. Syntactic Minimization Of Nondeterministic Finite Automata. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 78:1-78:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{myers_et_al:LIPIcs.MFCS.2021.78,
  author =	{Myers, Robert S. R. and Urbat, Henning},
  title =	{{Syntactic Minimization Of Nondeterministic Finite Automata}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{78:1--78:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.78},
  URN =		{urn:nbn:de:0030-drops-145186},
  doi =		{10.4230/LIPIcs.MFCS.2021.78},
  annote =	{Keywords: Algebraic language theory, Nondeterministic automata, NP-completeness}
}
Document
Computing Zigzag Persistence on Graphs in Near-Linear Time

Authors: Tamal K. Dey and Tao Hou

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)


Abstract
Graphs model real-world circumstances in many applications where they may constantly change to capture the dynamic behavior of the phenomena. Topological persistence which provides a set of birth and death pairs for the topological features is one instrument for analyzing such changing graph data. However, standard persistent homology defined over a growing space cannot always capture such a dynamic process unless shrinking with deletions is also allowed. Hence, zigzag persistence which incorporates both insertions and deletions of simplices is more appropriate in such a setting. Unlike standard persistence which admits nearly linear-time algorithms for graphs, such results for the zigzag version improving the general O(m^ω) time complexity are not known, where ω < 2.37286 is the matrix multiplication exponent. In this paper, we propose algorithms for zigzag persistence on graphs which run in near-linear time. Specifically, given a filtration with m additions and deletions on a graph with n vertices and edges, the algorithm for 0-dimension runs in O(mlog² n+mlog m) time and the algorithm for 1-dimension runs in O(mlog⁴ n) time. The algorithm for 0-dimension draws upon another algorithm designed originally for pairing critical points of Morse functions on 2-manifolds. The algorithm for 1-dimension pairs a negative edge with the earliest positive edge so that a 1-cycle containing both edges resides in all intermediate graphs. Both algorithms achieve the claimed time complexity via dynamic graph data structures proposed by Holm et al. In the end, using Alexander duality, we extend the algorithm for 0-dimension to compute the (p-1)-dimensional zigzag persistence for ℝ^p-embedded complexes in O(mlog² n+mlog m+nlog n) time.

Cite as

Tamal K. Dey and Tao Hou. Computing Zigzag Persistence on Graphs in Near-Linear Time. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 30:1-30:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.SoCG.2021.30,
  author =	{Dey, Tamal K. and Hou, Tao},
  title =	{{Computing Zigzag Persistence on Graphs in Near-Linear Time}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{30:1--30:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.30},
  URN =		{urn:nbn:de:0030-drops-138292},
  doi =		{10.4230/LIPIcs.SoCG.2021.30},
  annote =	{Keywords: persistent homology, zigzag persistence, graph filtration, dynamic networks}
}
Document
Locally Decodable/Correctable Codes for Insertions and Deletions

Authors: Alexander R. Block, Jeremiah Blocki, Elena Grigorescu, Shubhang Kulkarni, and Minshen Zhu

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


Abstract
Recent efforts in coding theory have focused on building codes for insertions and deletions, called insdel codes, with optimal trade-offs between their redundancy and their error-correction capabilities, as well as efficient encoding and decoding algorithms. In many applications, polynomial running time may still be prohibitively expensive, which has motivated the study of codes with super-efficient decoding algorithms. These have led to the well-studied notions of Locally Decodable Codes (LDCs) and Locally Correctable Codes (LCCs). Inspired by these notions, Ostrovsky and Paskin-Cherniavsky (Information Theoretic Security, 2015) generalized Hamming LDCs to insertions and deletions. To the best of our knowledge, these are the only known results that study the analogues of Hamming LDCs in channels performing insertions and deletions. Here we continue the study of insdel codes that admit local algorithms. Specifically, we reprove the results of Ostrovsky and Paskin-Cherniavsky for insdel LDCs using a different set of techniques. We also observe that the techniques extend to constructions of LCCs. Specifically, we obtain insdel LDCs and LCCs from their Hamming LDCs and LCCs analogues, respectively. The rate and error-correction capability blow up only by a constant factor, while the query complexity blows up by a poly log factor in the block length. Since insdel locally decodable/correctble codes are scarcely studied in the literature, we believe our results and techniques may lead to further research. In particular, we conjecture that constant-query insdel LDCs/LCCs do not exist.

Cite as

Alexander R. Block, Jeremiah Blocki, Elena Grigorescu, Shubhang Kulkarni, and Minshen Zhu. Locally Decodable/Correctable Codes for Insertions and Deletions. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{block_et_al:LIPIcs.FSTTCS.2020.16,
  author =	{Block, Alexander R. and Blocki, Jeremiah and Grigorescu, Elena and Kulkarni, Shubhang and Zhu, Minshen},
  title =	{{Locally Decodable/Correctable Codes for Insertions and Deletions}},
  booktitle =	{40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
  pages =	{16:1--16:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-174-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{182},
  editor =	{Saxena, Nitin and Simon, Sunil},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.16},
  URN =		{urn:nbn:de:0030-drops-132577},
  doi =		{10.4230/LIPIcs.FSTTCS.2020.16},
  annote =	{Keywords: Locally decodable/correctable codes, insert-delete channel}
}
  • Refine by Author
  • 3 May, Alexander
  • 3 Pilz, Alexander
  • 2 Fischlin, Marc
  • 2 Malkhi, Dahlia
  • 2 Schiewe, Alexander
  • Show More...

  • Refine by Classification
  • 3 Applied computing → Transportation
  • 2 Computing methodologies → Temporal reasoning
  • 2 Theory of computation → Constraint and logic programming
  • 1 Computer systems organization → Embedded and cyber-physical systems
  • 1 Computer systems organization → Multicore architectures
  • Show More...

  • Refine by Keyword
  • 2 algorithms
  • 2 scheduling
  • 1 Action Codes
  • 1 Action Contraction
  • 1 Action Refinement
  • Show More...

  • Refine by Type
  • 41 document

  • Refine by Publication Year
  • 7 2018
  • 7 2023
  • 5 2020
  • 4 2022
  • 3 2016
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail