Search Results

Documents authored by Jansen, David N.

Document
DOI: 10.4230/LIPIcs.CONCUR.2025.18
A State-Based O(m log n) Partitioning Algorithm for Branching Bisimilarity

Authors: Jan Friso Groote and David N. Jansen

Published in: LIPIcs, Volume 348, 36th International Conference on Concurrency Theory (CONCUR 2025)

Abstract
We present a new O(mlog n) algorithm to calculate branching bisimulation equivalence, which is the finest commonly used behavioural equivalence on labelled transition systems that takes the internal action τ into account. This algorithm combines the simpler data structure of an earlier algorithm for Kripke structures (without action labels) with the memory-efficiency of a later algorithm partitioning sets of labelled transitions. It employs a particularly elegant four-way split of blocks of states, which refines a block under two splitters and isolates all new bottom states, simultaneously. Benchmark results show that this new algorithm outperforms the best known algorithm for branching bisimulation both in time and space.
Cite as

Jan Friso Groote and David N. Jansen. A State-Based O(m log n) Partitioning Algorithm for Branching Bisimilarity. In 36th International Conference on Concurrency Theory (CONCUR 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 348, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{groote_et_al:LIPIcs.CONCUR.2025.18,
  author =	{Groote, Jan Friso and Jansen, David N.},
  title =	{{A State-Based O(m log n) Partitioning Algorithm for Branching Bisimilarity}},
  booktitle =	{36th International Conference on Concurrency Theory (CONCUR 2025)},
  pages =	{18:1--18:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-389-8},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{348},
  editor =	{Bouyer, Patricia and van de Pol, Jaco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2025.18},
  URN =		{urn:nbn:de:0030-drops-239688},
  doi =		{10.4230/LIPIcs.CONCUR.2025.18},
  annote =	{Keywords: Algorithm, Branching bisimulation, Partition refinement of states}
}
Document
DOI: 10.4230/LIPIcs.CONCUR.2020.8
A Near-Linear-Time Algorithm for Weak Bisimilarity on Markov Chains

Authors: David N. Jansen, Jan Friso Groote, Ferry Timmers, and Pengfei Yang

Published in: LIPIcs, Volume 171, 31st International Conference on Concurrency Theory (CONCUR 2020)

Abstract
This article improves the time bound for calculating the weak/branching bisimulation minimisation quotient on state-labelled discrete-time Markov chains from O(m n) to an expected-time O(m log⁴ n), where n is the number of states and m the number of transitions. For these results we assume that the set of state labels AP is small (|AP| ∈ O(m/n log⁴ n)). It follows the ideas of Groote et al. (ACM ToCL 2017) in combination with an efficient algorithm to handle decremental strongly connected components (Bernstein et al., STOC 2019).
Cite as

David N. Jansen, Jan Friso Groote, Ferry Timmers, and Pengfei Yang. A Near-Linear-Time Algorithm for Weak Bisimilarity on Markov Chains. In 31st International Conference on Concurrency Theory (CONCUR 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 171, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.CONCUR.2020.8,
  author =	{Jansen, David N. and Groote, Jan Friso and Timmers, Ferry and Yang, Pengfei},
  title =	{{A Near-Linear-Time Algorithm for Weak Bisimilarity on Markov Chains}},
  booktitle =	{31st International Conference on Concurrency Theory (CONCUR 2020)},
  pages =	{8:1--8:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-160-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{171},
  editor =	{Konnov, Igor and Kov\'{a}cs, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2020.8},
  URN =		{urn:nbn:de:0030-drops-128209},
  doi =		{10.4230/LIPIcs.CONCUR.2020.8},
  annote =	{Keywords: Behavioural Equivalence, weak Bisimulation, Markov Chain}
}
Document
DOI: 10.4230/DagSemProc.07101.3
07101 Working Group Report – Performance Measures Other Than Time

Authors: Lucia Cloth, Pepijn Crouzen, Matthias Fruth, Tingting Han, David N. Jansen, Mark Kattenbelt, Gerard J. M. Smit, and Lijun Zhang

Published in: Dagstuhl Seminar Proceedings, Volume 7101, Quantitative Aspects of Embedded Systems (2007)

Abstract
This presentation shows a few possible performance measures that might be interesting and possible evaluation methods.
Cite as

Lucia Cloth, Pepijn Crouzen, Matthias Fruth, Tingting Han, David N. Jansen, Mark Kattenbelt, Gerard J. M. Smit, and Lijun Zhang. 07101 Working Group Report – Performance Measures Other Than Time. In Quantitative Aspects of Embedded Systems. Dagstuhl Seminar Proceedings, Volume 7101, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{cloth_et_al:DagSemProc.07101.3,
  author =	{Cloth, Lucia and Crouzen, Pepijn and Fruth, Matthias and Han, Tingting and Jansen, David N. and Kattenbelt, Mark and Smit, Gerard J. M. and Zhang, Lijun},
  title =	{{07101 Working Group Report – Performance Measures Other Than Time}},
  booktitle =	{Quantitative Aspects of Embedded Systems},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7101},
  editor =	{Boudewijn Haverkort and Joost-Pieter Katoen and Lothar Thiele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07101.3},
  URN =		{urn:nbn:de:0030-drops-11396},
  doi =		{10.4230/DagSemProc.07101.3},
  annote =	{Keywords: }
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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