7 Search Results for "Müller, Sebastian"


Document
Decidable (Ac)counting with Parikh and Muller: Adding Presburger Arithmetic to Monadic Second-Order Logic over Tree-Interpretable Structures

Authors: Luisa Herrmann, Vincent Peth, and Sebastian Rudolph

Published in: LIPIcs, Volume 288, 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)


Abstract
We propose ωMSO⋈BAPA , an expressive logic for describing countable structures, which subsumes and transcends both Counting Monadic Second-Order Logic (CMSO) and Boolean Algebra with Presburger Arithmetic (BAPA). We show that satisfiability of ωMSO⋈BAPA is decidable over the class of labeled infinite binary trees, whereas it becomes undecidable even for a rather mild relaxations. The decidability result is established by an elaborate multi-step transformation into a particular normal form, followed by the deployment of Parikh-Muller Tree Automata, a novel kind of automaton for infinite labeled binary trees, integrating and generalizing both Muller and Parikh automata while still exhibiting a decidable (in fact PSpace-complete) emptiness problem. By means of MSO-interpretations, we lift the decidability result to all tree-interpretable classes of structures, including the classes of finite/countable structures of bounded treewidth/cliquewidth/partitionwidth. We generalize the result further by showing that decidability is even preserved when coupling width-restricted ωMSO⋈BAPA with width-unrestricted two-variable logic with advanced counting. A final showcase demonstrates how our results can be leveraged to harvest decidability results for expressive μ-calculi extended by global Presburger constraints.

Cite as

Luisa Herrmann, Vincent Peth, and Sebastian Rudolph. Decidable (Ac)counting with Parikh and Muller: Adding Presburger Arithmetic to Monadic Second-Order Logic over Tree-Interpretable Structures. In 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 288, pp. 33:1-33:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{herrmann_et_al:LIPIcs.CSL.2024.33,
  author =	{Herrmann, Luisa and Peth, Vincent and Rudolph, Sebastian},
  title =	{{Decidable (Ac)counting with Parikh and Muller: Adding Presburger Arithmetic to Monadic Second-Order Logic over Tree-Interpretable Structures}},
  booktitle =	{32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)},
  pages =	{33:1--33:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-310-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{288},
  editor =	{Murano, Aniello 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.CSL.2024.33},
  URN =		{urn:nbn:de:0030-drops-196768},
  doi =		{10.4230/LIPIcs.CSL.2024.33},
  annote =	{Keywords: MSO, BAPA, Parikh-Muller tree automata, decidability, MSO-interpretations}
}
Document
Towards a Reliable and Context-Based System Architecture for Autonomous Vehicles

Authors: Tobias Kain, Philipp Mundhenk, Julian-Steffen Müller, Hans Tompits, Maximilian Wesche, and Hendrik Decke

Published in: OASIcs, Volume 79, 2nd International Workshop on Autonomous Systems Design (ASD 2020)


Abstract
Full vehicle autonomy excludes a takeover by passengers in case a safety-critical application fails. Therefore, the system responsible for operating the autonomous vehicle has to detect and handle failures autonomously. Moreover, this system has to ensure the safety of the passengers, as well as the safety of other road users at any given time. Especially in the initial phase of autonomous vehicles, building up consumer confidence is essential. Therefore, in this regard, handling all failures by simply performing an emergency stop is not desirable. In this paper, we introduce an approach enabling a dynamic and safe reconfiguration of the autonomous driving system to handle occurring hardware and software failures. Since the requirements concerning safe reconfiguration actions are significantly affected by the current context the car is experiencing, the developed reconfiguration approach is sensitive to context changes. Our approach defines three interconnected layers, which are distinguished by their level of awareness. The top layer, referred to as the context layer, is responsible for observing the context. These context observations, in turn, imply a set of requirements, which constitute the input for the reconfiguration layer. The latter layer is required to determine reconfiguration actions, which are then executed by the architecture layer.

Cite as

Tobias Kain, Philipp Mundhenk, Julian-Steffen Müller, Hans Tompits, Maximilian Wesche, and Hendrik Decke. Towards a Reliable and Context-Based System Architecture for Autonomous Vehicles. In 2nd International Workshop on Autonomous Systems Design (ASD 2020). Open Access Series in Informatics (OASIcs), Volume 79, pp. 1:1-1:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{kain_et_al:OASIcs.ASD.2020.1,
  author =	{Kain, Tobias and Mundhenk, Philipp and M\"{u}ller, Julian-Steffen and Tompits, Hans and Wesche, Maximilian and Decke, Hendrik},
  title =	{{Towards a Reliable and Context-Based System Architecture for Autonomous Vehicles}},
  booktitle =	{2nd International Workshop on Autonomous Systems Design (ASD 2020)},
  pages =	{1:1--1:7},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-141-2},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{79},
  editor =	{Steinhorst, Sebastian and Deshmukh, Jyotirmoy V.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ASD.2020.1},
  URN =		{urn:nbn:de:0030-drops-125956},
  doi =		{10.4230/OASIcs.ASD.2020.1},
  annote =	{Keywords: autonomous driving, fail-operational systems, context-based architecture, application placement, optimization, monitoring}
}
Document
Vehicle Capacity-Aware Rerouting of Passengers in Delay Management

Authors: Matthias Müller-Hannemann, Ralf Rückert, and Sebastian S. Schmidt

Published in: OASIcs, Volume 75, 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)


Abstract
Due to the significant growth in passenger numbers, higher vehicle load factors and crowding become more and more of an issue in public transport. For safety reasons and because of an unsatisfactory discomfort, standing of passengers is rather limited in high-speed long-distance trains. In case of delays and (partially) cancelled trains, many passengers have to be rerouted. State-of-the-art rerouting merely focuses on minimizing delay at the destination of affected passengers but neglects limited vehicle capacities and crowding. Not considering capacities allows using highly efficient shortest path algorithms like RAPTOR or the connection scan algorithm (CSA). In this paper, we study the more complicated scenario where passengers compete for scarce capacities. This can be modeled as a piece-wise linear, convex cost multi-source multi-commodity unsplittable flow problem where each passenger group which has to be rerouted corresponds to a commodity. We compare a path-based integer linear programming (ILP) model with a heuristic greedy approach. In experiments with instances from German long-distance train traffic, we quantify the importance of considering vehicle capacities in case of train cancellations. We observe a tradeoff: The ILP approach slightly outperforms the greedy approach and both are much better than capacity unaware rerouting in quality, while the greedy algorithm runs more than three times faster.

Cite as

Matthias Müller-Hannemann, Ralf Rückert, and Sebastian S. Schmidt. Vehicle Capacity-Aware Rerouting of Passengers in Delay Management. In 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019). Open Access Series in Informatics (OASIcs), Volume 75, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{mullerhannemann_et_al:OASIcs.ATMOS.2019.7,
  author =	{M\"{u}ller-Hannemann, Matthias and R\"{u}ckert, Ralf and Schmidt, Sebastian S.},
  title =	{{Vehicle Capacity-Aware Rerouting of Passengers in Delay Management}},
  booktitle =	{19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)},
  pages =	{7:1--7:14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-128-3},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{75},
  editor =	{Cacchiani, Valentina and Marchetti-Spaccamela, Alberto},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2019.7},
  URN =		{urn:nbn:de:0030-drops-114192},
  doi =		{10.4230/OASIcs.ATMOS.2019.7},
  annote =	{Keywords: Delay management, passenger flows, vehicle capacities, rerouting}
}
Document
Recoverable Robust Timetable Information

Authors: Marc Goerigk, Sacha Heße, Matthias Müller-Hannemann, Marie Schmidt, and Anita Schöbel

Published in: OASIcs, Volume 33, 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2013)


Abstract
Timetable information is the process of determining a suitable travel route for a passenger. Due to delays in the original timetable, in practice it often happens that the travel route cannot be used as originally planned. For a passenger being already en route, it would hence be useful to know about alternatives that ensure that his/her destination can be reached. In this work we propose a recoverable robust approach to timetable information; i.e., we aim at finding travel routes that can easily be updated when delays occur during the journey. We present polynomial-time algorithms for this problem and evaluate the performance of the routes obtained this way on schedule data of the German train network of 2013 and simulated delay scenarios.

Cite as

Marc Goerigk, Sacha Heße, Matthias Müller-Hannemann, Marie Schmidt, and Anita Schöbel. Recoverable Robust Timetable Information. In 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 33, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@InProceedings{goerigk_et_al:OASIcs.ATMOS.2013.1,
  author =	{Goerigk, Marc and He{\ss}e, Sacha and M\"{u}ller-Hannemann, Matthias and Schmidt, Marie and Sch\"{o}bel, Anita},
  title =	{{Recoverable Robust Timetable Information}},
  booktitle =	{13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{1--14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-58-3},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{33},
  editor =	{Frigioni, Daniele and Stiller, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2013.1},
  URN =		{urn:nbn:de:0030-drops-42407},
  doi =		{10.4230/OASIcs.ATMOS.2013.1},
  annote =	{Keywords: timetable information, recoverable robustness, delay scenarios}
}
Document
Score-Informed Source Separation for Music Signals

Authors: Sebastian Ewert and Meinard Müller

Published in: Dagstuhl Follow-Ups, Volume 3, Multimodal Music Processing (2012)


Abstract
In recent years, the processing of audio recordings by exploiting additional musical knowledge has turned out to be a promising research direction. In particular, additional note information as specified by a musical score or a MIDI file has been employed to support various audio processing tasks such as source separation, audio parameterization, performance analysis, or instrument equalization. In this contribution, we provide an overview of approaches for score-informed source separation and illustrate their potential by discussing innovative applications and interfaces. Additionally, to illustrate some basic principles behind these approaches, we demonstrate how score information can be integrated into the well-known non-negative matrix factorization (NMF) framework. Finally, we compare this approach to advanced methods based on parametric models.

Cite as

Sebastian Ewert and Meinard Müller. Score-Informed Source Separation for Music Signals. In Multimodal Music Processing. Dagstuhl Follow-Ups, Volume 3, pp. 73-94, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)


Copy BibTex To Clipboard

@InCollection{ewert_et_al:DFU.Vol3.11041.73,
  author =	{Ewert, Sebastian and M\"{u}ller, Meinard},
  title =	{{Score-Informed Source Separation for Music Signals}},
  booktitle =	{Multimodal Music Processing},
  pages =	{73--94},
  series =	{Dagstuhl Follow-Ups},
  ISBN =	{978-3-939897-37-8},
  ISSN =	{1868-8977},
  year =	{2012},
  volume =	{3},
  editor =	{M\"{u}ller, Meinard and Goto, Masataka and Schedl, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DFU.Vol3.11041.73},
  URN =		{urn:nbn:de:0030-drops-34670},
  doi =		{10.4230/DFU.Vol3.11041.73},
  annote =	{Keywords: Audio processing, music signals, source separation, musical score, alignment, music synchronization, non-negative matrix factorization, parametric mod}
}
Document
Proof Complexity of Propositional Default Logic

Authors: Olaf Beyersdorff, Arne Meier, Sebastian Müller, Michael Thomas, and Heribert Vollmer

Published in: Dagstuhl Seminar Proceedings, Volume 10061, Circuits, Logic, and Games (2010)


Abstract
Default logic is one of the most popular and successful formalisms for non-monotonic reasoning. In 2002, Bonatti and Olivetti introduced several sequent calculi for credulous and skeptical reasoning in propositional default logic. In this paper we examine these calculi from a proof-complexity perspective. In particular, we show that the calculus for credulous reasoning obeys almost the same bounds on the proof size as Gentzen's system LK. Hence proving lower bounds for credulous reasoning will be as hard as proving lower bounds for LK. On the other hand, we show an exponential lower bound to the proof size in Bonatti and Olivetti's enhanced calculus for skeptical default reasoning.

Cite as

Olaf Beyersdorff, Arne Meier, Sebastian Müller, Michael Thomas, and Heribert Vollmer. Proof Complexity of Propositional Default Logic. In Circuits, Logic, and Games. Dagstuhl Seminar Proceedings, Volume 10061, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{beyersdorff_et_al:DagSemProc.10061.5,
  author =	{Beyersdorff, Olaf and Meier, Arne and M\"{u}ller, Sebastian and Thomas, Michael and Vollmer, Heribert},
  title =	{{Proof Complexity of Propositional Default Logic}},
  booktitle =	{Circuits, Logic, and Games},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10061},
  editor =	{Benjamin Rossman and Thomas Schwentick and Denis Th\'{e}rien and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10061.5},
  URN =		{urn:nbn:de:0030-drops-25261},
  doi =		{10.4230/DagSemProc.10061.5},
  annote =	{Keywords: Proof complexity, default logic, sequent calculus}
}
Document
Case Study ``Beatles Songs'' – What can be Learned from Unreliable Music Alignments?

Authors: Sebastian Ewert, Meinard Müller, Daniel Müllensiefen, Michael Clausen, and Geraint A. Wiggins

Published in: Dagstuhl Seminar Proceedings, Volume 9051, Knowledge representation for intelligent music processing (2009)


Abstract
As a result of massive digitization efforts and the world wide web, there is an exploding amount of available digital data describing and representing music at various semantic levels and in diverse formats. For example, in the case of the Beatles songs, there are numerous recordings including an increasing number of cover songs and arrangements as well as MIDI data and other symbolic music representations. The general goal of music synchronization is to align the multiple information sources related to a given piece of music. This becomes a difficult problem when the various representations reveal significant differences in structure and polyphony, while exhibiting various types of artifacts. In this paper, we address the issue of how music synchronization techniques are useful for automatically revealing critical passages with significant difference between the two versions to be aligned. Using the corpus of the Beatles songs as test bed, we analyze the kind of differences occurring in audio and MIDI versions available for the songs.

Cite as

Sebastian Ewert, Meinard Müller, Daniel Müllensiefen, Michael Clausen, and Geraint A. Wiggins. Case Study ``Beatles Songs'' – What can be Learned from Unreliable Music Alignments?. In Knowledge representation for intelligent music processing. Dagstuhl Seminar Proceedings, Volume 9051, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{ewert_et_al:DagSemProc.09051.3,
  author =	{Ewert, Sebastian and M\"{u}ller, Meinard and M\"{u}llensiefen, Daniel and Clausen, Michael and Wiggins, Geraint A.},
  title =	{{Case Study ``Beatles Songs'' – What can be Learned from Unreliable Music Alignments?}},
  booktitle =	{Knowledge representation for intelligent music processing},
  pages =	{1--16},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9051},
  editor =	{Eleanor Selfridge-Field and Frans Wiering and Geraint A. Wiggins},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09051.3},
  URN =		{urn:nbn:de:0030-drops-19640},
  doi =		{10.4230/DagSemProc.09051.3},
  annote =	{Keywords: MIDI, audio, music synchronization, multimodal, music collections, Beatles songs}
}
  • Refine by Author
  • 2 Ewert, Sebastian
  • 2 Müller, Meinard
  • 2 Müller-Hannemann, Matthias
  • 1 Beyersdorff, Olaf
  • 1 Clausen, Michael
  • Show More...

  • Refine by Classification
  • 1 Applied computing → Transportation
  • 1 Computer systems organization → Reconfigurable computing
  • 1 Mathematics of computing → Network flows
  • 1 Theory of computation → Automata over infinite objects
  • 1 Theory of computation → Automated reasoning
  • Show More...

  • Refine by Keyword
  • 2 music synchronization
  • 1 Audio processing
  • 1 BAPA
  • 1 Beatles songs
  • 1 Delay management
  • Show More...

  • Refine by Type
  • 7 document

  • Refine by Publication Year
  • 1 2009
  • 1 2010
  • 1 2012
  • 1 2013
  • 1 2019
  • 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