18 Search Results for "Kr�ller, Alexander"

Document
DOI: 10.4230/LIPIcs.TIME.2023.10
The Calculus of Temporal Influence

Authors: Florian Bruse, Marit Kastaun, Martin Lange, and Sören Möller

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

Abstract
We present the Calculus of Temporal Influence, a simple logical calculus that allows reasoning about the behaviour of real-valued functions over time by making assertions that bound their values or the values of their derivatives. The motivation for the design of such a proof system comes from the need to provide the background computational machinery for tools that support learning in experimental subjects in secondary-education classrooms. The end goal is a tool that allows school pupils to formalise hypotheses about phenomena in natural sciences, such that their validity with respect to some formal experiment model can be checked automatically. The Calculus of Temporal Influence provides a language for formal statements and the mechanisms for reasoning about valid logical consequences. It extends (and deviates in parts from) previous work introducing the Calculus of (Non-Temporal) Influence by integrating the ability to model temporal effects in such experiments. We show that reasoning in the calculus is sound with respect to a natural formal semantics, that logical consequence is at least semi-decidable, and that one obtains polynomial-time decidability for a natural stratification of the problem.
Cite as

Florian Bruse, Marit Kastaun, Martin Lange, and Sören Möller. The Calculus of Temporal Influence. In 30th International Symposium on Temporal Representation and Reasoning (TIME 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 278, pp. 10:1-10:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bruse_et_al:LIPIcs.TIME.2023.10,
  author =	{Bruse, Florian and Kastaun, Marit and Lange, Martin and M\"{o}ller, S\"{o}ren},
  title =	{{The Calculus of Temporal Influence}},
  booktitle =	{30th International Symposium on Temporal Representation and Reasoning (TIME 2023)},
  pages =	{10:1--10:19},
  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.10},
  URN =		{urn:nbn:de:0030-drops-191009},
  doi =		{10.4230/LIPIcs.TIME.2023.10},
  annote =	{Keywords: temporal reasoning, formal models, continuous functions, polynomial decidability}
}
Document
Extended Abstract
DOI: 10.4230/LIPIcs.TIME.2023.16
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
DOI: 10.4230/DagRep.12.2.103
Deep Learning and Knowledge Integration for Music Audio Analysis (Dagstuhl Seminar 22082)

Authors: Meinard Müller, Rachel Bittner, Juhan Nam, Michael Krause, and Yigitcan Özer

Published in: Dagstuhl Reports, Volume 12, Issue 2 (2022)

Abstract
Given the increasing amount of digital music, the development of computational tools that allow users to find, organize, analyze, and interact with music has become central to the research field known as Music Information Retrieval (MIR). As in general multimedia processing, many of the recent advances in MIR have been driven by techniques based on deep learning (DL). There is a growing trend to relax problem-specific modeling constraints from MIR systems and instead apply relatively generic DL-based approaches that rely on large quantities of data. In the Dagstuhl Seminar 22082, we critically examined this trend, discussing the strengths and weaknesses of these approaches using music as a challenging application domain. We mainly focused on music analysis tasks applied to audio representations (rather than symbolic music representations) to give the seminar cohesion. In this context, we systematically explored how musical knowledge can be integrated into or relaxed from computational pipelines. We then discussed how this choice could affect the explainability of models or the vulnerability to data biases and confounding factors. Furthermore, besides explainability and generalization, we also addressed efficiency, ethical and educational aspects considering traditional model-based and recent data-driven methods. In this report, we give an overview of the various contributions and results of the seminar. We start with an executive summary describing the main topics, goals, and group activities. Then, we give an overview of the participants' stimulus talks and subsequent discussions (listed alphabetically by the main contributor’s last name) and summarize further activities, including group discussions and music sessions.
Cite as

Meinard Müller, Rachel Bittner, Juhan Nam, Michael Krause, and Yigitcan Özer. Deep Learning and Knowledge Integration for Music Audio Analysis (Dagstuhl Seminar 22082). In Dagstuhl Reports, Volume 12, Issue 2, pp. 103-133, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{muller_et_al:DagRep.12.2.103,
  author =	{M\"{u}ller, Meinard and Bittner, Rachel and Nam, Juhan and Krause, Michael and \"{O}zer, Yigitcan},
  title =	{{Deep Learning and Knowledge Integration for Music Audio Analysis (Dagstuhl Seminar 22082)}},
  pages =	{103--133},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2022},
  volume =	{12},
  number =	{2},
  editor =	{M\"{u}ller, Meinard and Bittner, Rachel and Nam, Juhan and Krause, Michael and \"{O}zer, Yigitcan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.12.2.103},
  URN =		{urn:nbn:de:0030-drops-169333},
  doi =		{10.4230/DagRep.12.2.103},
  annote =	{Keywords: Audio signal processing, deep learning, knowledge representation, music information retrieval, user interaction and interfaces}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.68
A Lower Bound on the Space Overhead of Fault-Tolerant Quantum Computation

Authors: Omar Fawzi, Alexander Müller-Hermes, and Ala Shayeghi

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation stating that arbitrarily long quantum computations can be performed with a polylogarithmic overhead provided the noise level is below a constant level. A recent work by Fawzi, Grospellier and Leverrier (FOCS 2018) building on a result by Gottesman (QIC 2013) has shown that the space overhead can be asymptotically reduced to a constant independent of the circuit provided we only consider circuits with a length bounded by a polynomial in the width. In this work, using a minimal model for quantum fault tolerance, we establish a general lower bound on the space overhead required to achieve fault tolerance. For any non-unitary qubit channel 𝒩 and any quantum fault tolerance schemes against i.i.d. noise modeled by 𝒩, we prove a lower bound of max{Q(𝒩)^{-1}n,α_𝒩 log T} on the number of physical qubits, for circuits of length T and width n. Here, Q(𝒩) denotes the quantum capacity of 𝒩 and α_𝒩 > 0 is a constant only depending on the channel 𝒩. In our model, we allow for qubits to be replaced by fresh ones during the execution of the circuit and in the case of unital noise, we allow classical computation to be free and perfect. This improves upon results that assumed classical computations to be also affected by noise, and that sometimes did not allow for fresh qubits to be added. Along the way, we prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude damping noise resolving a conjecture by Ben-Or, Gottesman and Hassidim (2013).
Cite as

Omar Fawzi, Alexander Müller-Hermes, and Ala Shayeghi. A Lower Bound on the Space Overhead of Fault-Tolerant Quantum Computation. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 68:1-68:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{fawzi_et_al:LIPIcs.ITCS.2022.68,
  author =	{Fawzi, Omar and M\"{u}ller-Hermes, Alexander and Shayeghi, Ala},
  title =	{{A Lower Bound on the Space Overhead of Fault-Tolerant Quantum Computation}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{68:1--68:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.68},
  URN =		{urn:nbn:de:0030-drops-156649},
  doi =		{10.4230/LIPIcs.ITCS.2022.68},
  annote =	{Keywords: Fault-tolerant quantum computation, quantum error correction}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2021.3
Towards Improved Robustness of Public Transport by a Machine-Learned Oracle

Authors: Matthias Müller-Hannemann, Ralf Rückert, Alexander Schiewe, and Anita Schöbel

Published in: OASIcs, Volume 96, 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)

Abstract
The design and optimization of public transport systems is a highly complex and challenging process. Here, we focus on the trade-off between two criteria which shall make the transport system attractive for passengers: their travel time and the robustness of the system. The latter is time-consuming to evaluate. A passenger-based evaluation of robustness requires a performance simulation with respect to a large number of possible delay scenarios, making this step computationally very expensive. For optimizing the robustness, we hence apply a machine-learned oracle from previous work which approximates the robustness of a public transport system. We apply this oracle to bi-criteria optimization of integrated public transport planning (timetabling and vehicle scheduling) in two ways: First, we explore a local search based framework studying several variants of neighborhoods. Second, we evaluate a genetic algorithm. Computational experiments with artificial and close to real-word benchmark datasets yield promising results. In all cases, an existing pool of solutions (i.e., public transport plans) can be significantly improved by finding a number of new non-dominated solutions, providing better and different trade-offs between robustness and travel time.
Cite as

Matthias Müller-Hannemann, Ralf Rückert, Alexander Schiewe, and Anita Schöbel. Towards Improved Robustness of Public Transport by a Machine-Learned Oracle. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 3:1-3:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{mullerhannemann_et_al:OASIcs.ATMOS.2021.3,
  author =	{M\"{u}ller-Hannemann, Matthias and R\"{u}ckert, Ralf and Schiewe, Alexander and Sch\"{o}bel, Anita},
  title =	{{Towards Improved Robustness of Public Transport by a Machine-Learned Oracle}},
  booktitle =	{21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
  pages =	{3:1--3:20},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-213-6},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{96},
  editor =	{M\"{u}ller-Hannemann, Matthias and Perea, Federico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.3},
  URN =		{urn:nbn:de:0030-drops-148721},
  doi =		{10.4230/OASIcs.ATMOS.2021.3},
  annote =	{Keywords: Public Transportation, Timetabling, Machine Learning, Robustness}
}
Document
Short Paper
DOI: 10.4230/OASIcs.ATMOS.2021.17
Efficient Algorithms for the Multi-Period Line Planning Problem in Public Transportation (Short Paper)

Authors: Güvenç Şahin, Amin Ahmadi Digehsara, and Ralf Borndörfer

Published in: OASIcs, Volume 96, 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)

Abstract
In order to plan and schedule a demand-responsive public transportation system, both temporal and spatial changes in demand should be taken into account even at the line planning stage. We study the multi-period line planning problem with integrated decisions regarding dynamic allocation of vehicles among the lines. Given the NP-hard nature of the line planning problem, the multi-period version is clearly difficult to solve for large public transit networks even with advanced solvers. It becomes necessary to develop algorithms that are capable of solving even the very-large instances in reasonable time. For instances which belong to real public transit networks, we present results of a heuristic local branching algorithm and an exact approach based on constraint propagation.
Cite as

Güvenç Şahin, Amin Ahmadi Digehsara, and Ralf Borndörfer. Efficient Algorithms for the Multi-Period Line Planning Problem in Public Transportation (Short Paper). In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 17:1-17:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{sahin_et_al:OASIcs.ATMOS.2021.17,
  author =	{\c{S}ahin, G\"{u}ven\c{c} and Ahmadi Digehsara, Amin and Bornd\"{o}rfer, Ralf},
  title =	{{Efficient Algorithms for the Multi-Period Line Planning Problem in Public Transportation}},
  booktitle =	{21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
  pages =	{17:1--17:6},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-213-6},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{96},
  editor =	{M\"{u}ller-Hannemann, Matthias and Perea, Federico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.17},
  URN =		{urn:nbn:de:0030-drops-148863},
  doi =		{10.4230/OASIcs.ATMOS.2021.17},
  annote =	{Keywords: public transportation, line planning, multi-period planning, local branching, constraint propagation}
}
Document
DOI: 10.4230/LIPIcs.ECOOP.2021.6
CodeDJ: Reproducible Queries over Large-Scale Software Repositories

Authors: Petr Maj, Konrad Siek, Alexander Kovalenko, and Jan Vitek

Published in: LIPIcs, Volume 194, 35th European Conference on Object-Oriented Programming (ECOOP 2021)

Abstract
Analyzing massive code bases is a staple of modern software engineering research – a welcome side-effect of the advent of large-scale software repositories such as GitHub. Selecting which projects one should analyze is a labor-intensive process, and a process that can lead to biased results if the selection is not representative of the population of interest. One issue faced by researchers is that the interface exposed by software repositories only allows the most basic of queries. CodeDJ is an infrastructure for querying repositories composed of a persistent datastore, constantly updated with data acquired from GitHub, and an in-memory database with a Rust query interface. CodeDJ supports reproducibility, historical queries are answered deterministically using past states of the datastore; thus researchers can reproduce published results. To illustrate the benefits of CodeDJ, we identify biases in the data of a published study and, by repeating the analysis with new data, we demonstrate that the study’s conclusions were sensitive to the choice of projects.
Cite as

Petr Maj, Konrad Siek, Alexander Kovalenko, and Jan Vitek. CodeDJ: Reproducible Queries over Large-Scale Software Repositories. In 35th European Conference on Object-Oriented Programming (ECOOP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 194, pp. 6:1-6:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{maj_et_al:LIPIcs.ECOOP.2021.6,
  author =	{Maj, Petr and Siek, Konrad and Kovalenko, Alexander and Vitek, Jan},
  title =	{{CodeDJ: Reproducible Queries over Large-Scale Software Repositories}},
  booktitle =	{35th European Conference on Object-Oriented Programming (ECOOP 2021)},
  pages =	{6:1--6:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-190-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{194},
  editor =	{M{\o}ller, Anders and Sridharan, Manu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2021.6},
  URN =		{urn:nbn:de:0030-drops-140498},
  doi =		{10.4230/LIPIcs.ECOOP.2021.6},
  annote =	{Keywords: Software, Mining Code Repositories, Source Code Analysis}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.65
Elimination Distance to Bounded Degree on Planar Graphs

Authors: Alexander Lindermayr, Sebastian Siebertz, and Alexandre Vigny

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
We study the graph parameter elimination distance to bounded degree, which was introduced by Bulian and Dawar in their study of the parameterized complexity of the graph isomorphism problem. We prove that the problem is fixed-parameter tractable on planar graphs, that is, there exists an algorithm that given a planar graph G and integers d and k decides in time f(k,d)⋅ n^c for a computable function f and constant c whether the elimination distance of G to the class of degree d graphs is at most k.
Cite as

Alexander Lindermayr, Sebastian Siebertz, and Alexandre Vigny. Elimination Distance to Bounded Degree on Planar Graphs. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 65:1-65:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{lindermayr_et_al:LIPIcs.MFCS.2020.65,
  author =	{Lindermayr, Alexander and Siebertz, Sebastian and Vigny, Alexandre},
  title =	{{Elimination Distance to Bounded Degree on Planar Graphs}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{65:1--65:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.65},
  URN =		{urn:nbn:de:0030-drops-127557},
  doi =		{10.4230/LIPIcs.MFCS.2020.65},
  annote =	{Keywords: Elimination distance, parameterized complexity, structural graph theory}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.80
Ambiguity Hierarchy of Regular Infinite Tree Languages

Authors: Alexander Rabinovich and Doron Tiferet

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
An automaton is unambiguous if for every input it has at most one accepting computation. An automaton is k-ambiguous (for k > 0) if for every input it has at most k accepting computations. An automaton is boundedly ambiguous if there is k ∈ ℕ, such that for every input it has at most k accepting computations. An automaton is finitely (respectively, countably) ambiguous if for every input it has at most finitely (respectively, countably) many accepting computations. The degree of ambiguity of a regular language is defined in a natural way. A language is k-ambiguous (respectively, boundedly, finitely, countably ambiguous) if it is accepted by a k-ambiguous (respectively, boundedly, finitely, countably ambiguous) automaton. Over finite words every regular language is accepted by a deterministic automaton. Over finite trees every regular language is accepted by an unambiguous automaton. Over ω-words every regular language is accepted by an unambiguous Büchi automaton [Arnold, 1983] and by a deterministic parity automaton. Over infinite trees there are ambiguous languages [Carayol et al., 2010]. We show that over infinite trees there is a hierarchy of degrees of ambiguity: For every k > 1 there are k-ambiguous languages which are not k-1 ambiguous; there are finitely (respectively countably, uncountably) ambiguous languages which are not boundedly (respectively finitely, countably) ambiguous.
Cite as

Alexander Rabinovich and Doron Tiferet. Ambiguity Hierarchy of Regular Infinite Tree Languages. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 80:1-80:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{rabinovich_et_al:LIPIcs.MFCS.2020.80,
  author =	{Rabinovich, Alexander and Tiferet, Doron},
  title =	{{Ambiguity Hierarchy of Regular Infinite Tree Languages}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{80:1--80:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.80},
  URN =		{urn:nbn:de:0030-drops-127495},
  doi =		{10.4230/LIPIcs.MFCS.2020.80},
  annote =	{Keywords: automata on infinite trees, ambiguous automata, monadic second-order logic}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2018.4
Robustness as a Third Dimension for Evaluating Public Transport Plans

Authors: Markus Friedrich, Matthias Müller-Hannemann, Ralf Rückert, Alexander Schiewe, and Anita Schöbel

Published in: OASIcs, Volume 65, 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)

Abstract
Providing attractive and efficient public transport services is of crucial importance due to higher demands for mobility and the need to reduce air pollution and to save energy. The classical planning process in public transport tries to achieve a reasonable compromise between service quality for passengers and operating costs. Service quality mostly considers quantities like average travel time and number of transfers. Since daily public transport inevitably suffers from delays caused by random disturbances and disruptions, robustness also plays a crucial role. While there are recent attempts to achieve delay-resistant timetables, comparably little work has been done to systematically assess and to compare the robustness of transport plans from a passenger point of view. We here provide a general and flexible framework for evaluating public transport plans (lines, timetables, and vehicle schedules) in various ways. It enables planners to explore several trade-offs between operating costs, service quality (average perceived travel time of passengers), and robustness against delays. For such an assessment we develop several passenger-oriented robustness tests which can be instantiated with parameterized delay scenarios. Important features of our framework include detailed passenger flow models, delay propagation schemes and disposition strategies, rerouting strategies as well as vehicle capacities. To demonstrate possible use cases, our framework has been applied to a variety of public transport plans which have been created for the same given demand for an artificial urban grid network and to instances for long-distance train networks. As one application we study the impact of different strategies to improve the robustness of timetables by insertion of supplement times. We also show that the framework can be used to optimize waiting strategies in delay management.
Cite as

Markus Friedrich, Matthias Müller-Hannemann, Ralf Rückert, Alexander Schiewe, and Anita Schöbel. Robustness as a Third Dimension for Evaluating Public Transport Plans. In 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018). Open Access Series in Informatics (OASIcs), Volume 65, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{friedrich_et_al:OASIcs.ATMOS.2018.4,
  author =	{Friedrich, Markus and M\"{u}ller-Hannemann, Matthias and R\"{u}ckert, Ralf and Schiewe, Alexander and Sch\"{o}bel, Anita},
  title =	{{Robustness as a Third Dimension for Evaluating Public Transport Plans}},
  booktitle =	{18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)},
  pages =	{4:1--4:17},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-096-5},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{65},
  editor =	{Bornd\"{o}rfer, Ralf and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2018.4},
  URN =		{urn:nbn:de:0030-drops-97097},
  doi =		{10.4230/OASIcs.ATMOS.2018.4},
  annote =	{Keywords: robustness, timetabling, vehicle schedules, delays}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2017.6
Robustness Tests for Public Transport Planning

Authors: Markus Friedrich, Matthias Müller-Hannemann, Ralf Rückert, Alexander Schiewe, and Anita Schöbel

Published in: OASIcs, Volume 59, 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)

Abstract
The classical planning process in public transport planning focuses on the two criteria operating costs and quality for passengers. Quality mostly considers quantities like average travel time and number of transfers. Since public transport often suffers from delays caused by random disturbances, we are interested in adding a third dimension: robustness. We propose passenger-oriented robustness indicators for public transport networks and timetables. These robustness indicators are evaluated for several public transport plans which have been created for an artificial urban network with the same demand. The study shows that these indicators are suitable to measure the robustness of a line plan and a timetable. We explore different trade-offs between operating costs, quality (average travel time of passengers), and robustness against delays. Our results show that the proposed robustness indicators give reasonable results.
Cite as

Markus Friedrich, Matthias Müller-Hannemann, Ralf Rückert, Alexander Schiewe, and Anita Schöbel. Robustness Tests for Public Transport Planning. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{friedrich_et_al:OASIcs.ATMOS.2017.6,
  author =	{Friedrich, Markus and M\"{u}ller-Hannemann, Matthias and R\"{u}ckert, Ralf and Schiewe, Alexander and Sch\"{o}bel, Anita},
  title =	{{Robustness Tests for Public Transport Planning}},
  booktitle =	{17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
  pages =	{6:1--6:16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-042-2},
  ISSN =	{2190-6807},
  year =	{2017},
  volume =	{59},
  editor =	{D'Angelo, Gianlorenzo and Dollevoet, Twan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2017.6},
  URN =		{urn:nbn:de:0030-drops-78904},
  doi =		{10.4230/OASIcs.ATMOS.2017.6},
  annote =	{Keywords: robustness measure, timetabling, line planning, delays, passenger-orientation}
}
Document
DOI: 10.4230/DagSemProc.10461.1
10461 Abstracts Collection and Summary – Schematization in Cartography, Visualization, and Computational Geometry

Authors: Jason Dykes, Matthias Müller-Hannemann, and Alexander Wolff

Published in: Dagstuhl Seminar Proceedings, Volume 10461, Schematization in Cartography, Visualization, and Computational Geometry (2011)

Abstract
The Dagstuhl Seminar 10461 ``Schematization in Cartography, Visualization, and Computational Geometry'' was held November 14--19, 2010 in Schloss Dagstuhl~-- Leibniz Center for Informatics. The seminar brought together experts from the areas graph drawing, information visualization, geographic information science, computational geometry, very-large-scale integrated circuit (VLSI) layout, and underground mining. The aim was to discuss problems that arise when computing the layout of complex networks under angular restrictions (that govern the way in which the network edges are drawn). This collection consists of abstracts of three different types of contributions that reflect the different stages of the seminar; (a)~survey talks about the role of schematization in the various communities represented at the seminar, (b)~talks in the open problem and open mic sessions, and (c)~introductory talks.
Cite as

Jason Dykes, Matthias Müller-Hannemann, and Alexander Wolff. 10461 Abstracts Collection and Summary – Schematization in Cartography, Visualization, and Computational Geometry. In Schematization in Cartography, Visualization, and Computational Geometry. Dagstuhl Seminar Proceedings, Volume 10461, pp. 1-36, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{dykes_et_al:DagSemProc.10461.1,
  author =	{Dykes, Jason and M\"{u}ller-Hannemann, Matthias and Wolff, Alexander},
  title =	{{10461 Abstracts Collection and Summary – Schematization in Cartography, Visualization, and Computational Geometry}},
  booktitle =	{Schematization in Cartography, Visualization, and Computational Geometry},
  pages =	{1--36},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2011},
  volume =	{10461},
  editor =	{Jason Dykes and Mattias M\"{u}ller-Hannemann and Alexander Wolff},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10461.1},
  URN =		{urn:nbn:de:0030-drops-30859},
  doi =		{10.4230/DagSemProc.10461.1},
  annote =	{Keywords: Information visualization, geo-visualization, geographic information systems, cartography, graph drawing, VLSI layout, underground mining, cartographic generalization, schematization, building simplification, orthogonal graph drawing, octilinear layout, schematic maps, Steiner trees}
}
Document
DOI: 10.4230/DagSemProc.10141.4
FORTES: Forensic Information Flow Analysis of Business Processes

Authors: Rafael Accorsi and Günter Müller

Published in: Dagstuhl Seminar Proceedings, Volume 10141, Distributed Usage Control (2010)

Abstract
Nearly 70% of all business processes in use today rely on automated workflow systems for their execution. Despite the growing expenses in the design of advanced tools for secure and compliant deployment of workflows, an exponential growth of dependability incidents persists. Concepts beyond access control focusing on information flow control offer new paradigms to design security mechanisms for reliable and secure IT-based workflows. This talk presents FORTES, an approach for the forensic analysis of information flow properties. FORTES claims that information flow control can be made usable as a core of an audit-control system. For this purpose, it reconstructs workflow models from secure log files (i.e. execution traces) and, applying security policies, analyzes the information flows to distinguish security relevant from security irrelevant information flows. FORTES thus cannot prevent security policy violations, but by detecting them with well-founded analysis, improve the precision of audit controls and the generated certificates.
Cite as

Rafael Accorsi and Günter Müller. FORTES: Forensic Information Flow Analysis of Business Processes. In Distributed Usage Control. Dagstuhl Seminar Proceedings, Volume 10141, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{accorsi_et_al:DagSemProc.10141.4,
  author =	{Accorsi, Rafael and M\"{u}ller, G\"{u}nter},
  title =	{{FORTES: Forensic Information Flow Analysis of Business Processes}},
  booktitle =	{Distributed Usage Control},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10141},
  editor =	{Sandro Etalle and Alexander Pretschner and Raiv S. Sandhu and Marianne Winslett},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10141.4},
  URN =		{urn:nbn:de:0030-drops-27167},
  doi =		{10.4230/DagSemProc.10141.4},
  annote =	{Keywords: Audit, Information flow analysis, business processes}
}
Document
DOI: 10.4230/DagSemProc.08141.3
A Generic Framework for the Engineering of Self-Adaptive and Self-Organising Systems

Authors: Giovanna Di Marzo Serugendo, John Fitzgerald, Alexander Romanovsky, and Nicolas Guelfi

Published in: Dagstuhl Seminar Proceedings, Volume 8141, Organic Computing - Controlled Self-organization (2008)

Abstract
This paper provides a unifying view for the engineering of self-adaptive (SA) and self-organising (SO) systems. We first identify requirements for designing and building trustworthy self-adaptive and self-organising systems. Second, we propose a generic framework combining design-time and run-time features, which permit the definition and analysis at design-time of mechanisms that both ensure and constrain the run-time behaviour of an SA or SO system, thereby providing some assurance of its self-* capabilities. We show how this framework applies to both an SA and an SO system, and discuss several current proof-of-concept studies on the enabling technologies.
Cite as

Giovanna Di Marzo Serugendo, John Fitzgerald, Alexander Romanovsky, and Nicolas Guelfi. A Generic Framework for the Engineering of Self-Adaptive and Self-Organising Systems. In Organic Computing - Controlled Self-organization. Dagstuhl Seminar Proceedings, Volume 8141, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{dimarzoserugendo_et_al:DagSemProc.08141.3,
  author =	{Di Marzo Serugendo, Giovanna and Fitzgerald, John and Romanovsky, Alexander and Guelfi, Nicolas},
  title =	{{A Generic Framework for the Engineering of Self-Adaptive and Self-Organising Systems}},
  booktitle =	{Organic Computing - Controlled Self-organization},
  pages =	{1--16},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8141},
  editor =	{Kirstie Bellman and Michael G. Hinchey and Christian M\"{u}ller-Schloer and Hartmut Schmeck and Rolf W\"{u}rtz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08141.3},
  URN =		{urn:nbn:de:0030-drops-15637},
  doi =		{10.4230/DagSemProc.08141.3},
  annote =	{Keywords: Metadata, policies, self-adaptive, self-organising, software architecture}
}
Document
DOI: 10.4230/DagSemProc.08061.3
A Unified Framework for Verification Techniques for Object Invariants

Authors: Sophia Drossopoulou, Adrian Francalanza, P. Müller, and Alexander J. Summers

Published in: Dagstuhl Seminar Proceedings, Volume 8061, Types, Logics and Semantics for State (2008)

Abstract
Object invariants define the consistency of objects. They have subtle semantics, mainly because of call-backs, multi-object invariants, and subclassing. Several verification techniques for object invariants have been proposed. It is difficult to compare these techniques, and to ascertain their soundness, because of their differences in restrictions on programs and invariants, in the use of advanced type systems (e.g., ownership types), in the meaning of invariants, and in proof obligations. We develop a unified framework for such techniques. We distil seven parameters that characterise a verification technique, and identify sufficient conditions on these parameters which guarantee soundness. We instantiate our framework with three verification techniques from the literature, and use it to assess soundness and compare expressiveness.
Cite as

Sophia Drossopoulou, Adrian Francalanza, P. Müller, and Alexander J. Summers. A Unified Framework for Verification Techniques for Object Invariants. In Types, Logics and Semantics for State. Dagstuhl Seminar Proceedings, Volume 8061, pp. 1-25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{drossopoulou_et_al:DagSemProc.08061.3,
  author =	{Drossopoulou, Sophia and Francalanza, Adrian and M\"{u}ller, P. and Summers, Alexander J.},
  title =	{{A Unified Framework for  Verification Techniques for Object Invariants}},
  booktitle =	{Types, Logics and Semantics for State},
  pages =	{1--25},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8061},
  editor =	{Amal Ahmed and Nick Benton and Martin Hofmann and Greg Morrisett},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08061.3},
  URN =		{urn:nbn:de:0030-drops-14278},
  doi =		{10.4230/DagSemProc.08061.3},
  annote =	{Keywords: Object invariants, visible states semantics, verification, sound}
}
  • Refine by Author
  • 4 Müller-Hannemann, Matthias
  • 3 Rückert, Ralf
  • 3 Schiewe, Alexander
  • 3 Schöbel, Anita
  • 2 Fekete, Sándor
  • Show More...

  • Refine by Classification
  • 3 Applied computing → Transportation
  • 1 Applied computing → Interactive learning environments
  • 1 Applied computing → Sound and music computing
  • 1 Computing methodologies → Spatial and physical reasoning
  • 1 Computing methodologies → Temporal reasoning
  • Show More...

  • Refine by Keyword
  • 2 delays
  • 2 line planning
  • 2 timetabling
  • 1 Audio signal processing
  • 1 Audit
  • Show More...

  • Refine by Type
  • 18 document

  • Refine by Publication Year
  • 3 2021
  • 2 2006
  • 2 2008
  • 2 2020
  • 2 2022
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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