2 Search Results for "Gro�mann, Peter"

Document
DOI: 10.4230/LIPIcs.FSCD.2021.28
Coalgebra Encoding for Efficient Minimization

Authors: Hans-Peter Deifel, Stefan Milius, and Thorsten Wißmann

Published in: LIPIcs, Volume 195, 6th International Conference on Formal Structures for Computation and Deduction (FSCD 2021)

Abstract
Recently, we have developed an efficient generic partition refinement algorithm, which computes behavioural equivalence on a state-based system given as an encoded coalgebra, and implemented it in the tool CoPaR. Here we extend this to a fully fledged minimization algorithm and tool by integrating two new aspects: (1) the computation of the transition structure on the minimized state set, and (2) the computation of the reachable part of the given system. In our generic coalgebraic setting these two aspects turn out to be surprisingly non-trivial requiring us to extend the previous theory. In particular, we identify a sufficient condition on encodings of coalgebras, and we show how to augment the existing interface, which encapsulates computations that are specific for the coalgebraic type functor, to make the above extensions possible. Both extensions have linear run time.
Cite as

Hans-Peter Deifel, Stefan Milius, and Thorsten Wißmann. Coalgebra Encoding for Efficient Minimization. In 6th International Conference on Formal Structures for Computation and Deduction (FSCD 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 195, pp. 28:1-28:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{deifel_et_al:LIPIcs.FSCD.2021.28,
  author =	{Deifel, Hans-Peter and Milius, Stefan and Wi{\ss}mann, Thorsten},
  title =	{{Coalgebra Encoding for Efficient Minimization}},
  booktitle =	{6th International Conference on Formal Structures for Computation and Deduction (FSCD 2021)},
  pages =	{28:1--28:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-191-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{195},
  editor =	{Kobayashi, Naoki},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2021.28},
  URN =		{urn:nbn:de:0030-drops-142664},
  doi =		{10.4230/LIPIcs.FSCD.2021.28},
  annote =	{Keywords: Coalgebra, Partition refinement, Transition systems, Minimization}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2016.3
Integrating Passengers' Routes in Periodic Timetabling: A SAT approach

Authors: Philine Gattermann, Peter Großmann, Karl Nachtigall, and Anita Schöbel

Published in: OASIcs, Volume 54, 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)

Abstract
The periodic event scheduling problem (PESP) is a well studied problem known as intrinsically hard. Its main application is for designing periodic timetables in public transportation. To this end, the passengers' paths are required as input data. This is a drawback since the final paths which are used by the passengers depend on the timetable to be designed. Including the passengers' routing in the PESP hence improves the quality of the resulting timetables. However, this makes PESP even harder. Formulating the PESP as satisfiability problem and using SAT solvers for its solution has been shown to be a highly promising approach. The goal of this paper is to exploit if SAT solvers can also be used for the problem of integrated timetabling and passenger routing. In our model of the integrated problem we distribute origin-destination (OD) pairs temporally through the network by using time-slices in order to make the resulting model more realistic. We present a formulation of this integrated problem as integer program which we are able to transform to a satisfiability problem. We tested the latter formulation within numerical experiments, which are performed on Germany's long-distance passenger railway network. The computation's analysis in which we compare the integrated approach with the traditional one with fixed passengers' weights, show promising results for future scientific investigations.
Cite as

Philine Gattermann, Peter Großmann, Karl Nachtigall, and Anita Schöbel. Integrating Passengers' Routes in Periodic Timetabling: A SAT approach. In 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016). Open Access Series in Informatics (OASIcs), Volume 54, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{gattermann_et_al:OASIcs.ATMOS.2016.3,
  author =	{Gattermann, Philine and Gro{\ss}mann, Peter and Nachtigall, Karl and Sch\"{o}bel, Anita},
  title =	{{Integrating Passengers' Routes in Periodic Timetabling: A SAT approach}},
  booktitle =	{16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)},
  pages =	{3:1--3:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-021-7},
  ISSN =	{2190-6807},
  year =	{2016},
  volume =	{54},
  editor =	{Goerigk, Marc and Werneck, Renato F.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2016.3},
  URN =		{urn:nbn:de:0030-drops-65279},
  doi =		{10.4230/OASIcs.ATMOS.2016.3},
  annote =	{Keywords: PESP, Timetabling, Public Transport, Passengers' Routes, SAT}
}
  • Refine by Author
  • 1 Deifel, Hans-Peter
  • 1 Gattermann, Philine
  • 1 Großmann, Peter
  • 1 Milius, Stefan
  • 1 Nachtigall, Karl
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Logic and verification
  • 1 Theory of computation → Models of computation

  • Refine by Keyword
  • 1 Coalgebra
  • 1 Minimization
  • 1 PESP
  • 1 Partition refinement
  • 1 Passengers' Routes
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2016
  • 1 2021

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