1 Search Results for "Deifel, Hans-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}
}
  • Refine by Author
  • 1 Deifel, Hans-Peter
  • 1 Milius, Stefan
  • 1 Wißmann, Thorsten

  • 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 Partition refinement
  • 1 Transition systems

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 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