10 citations · 12 across the 3 of their papers we have counts for
7 papers
A Quadratic Lower Bound for Simulation
Jan Friso Groote, Jan Martens
We show that deciding simulation equivalence and simulation preorder have quadratic lower bounds assuming that the Strong Exponential Time Hypothesis holds. This is in line with th…
Computing minimal distinguishing Hennessy-Milner formulas is NP-hard, but variants are tractable
Jan Martens, Jan Friso Groote
We study the problem of computing minimal distinguishing formulas for non-bisimilar states in finite LTSs. We show that this is NP-hard if the size of the formula must be minimal.…
Deciding minimal distinguishing DFAs is NP-complete
Jan Martens
In this paper, we present a proof of the NP-completeness of computing the smallest Deterministic Finite Automaton (DFA) that distinguishes two given regular languages as DFAs. A di…
Lowerbounds for Bisimulation by Partition Refinement
Jan Friso Groote, Jan Martens, Erik. P. de Vink
We provide time lower bounds for sequential and parallel algorithms deciding bisimulation on labeled transition systems that use partition refinement. For sequential algorithms thi…
A linear parallel algorithm to compute bisimulation and relational coarsest partitions
Jan Martens, Jan Friso Groote, Lars van den Haak +2
The most efficient way to calculate strong bisimilarity is by calculation the relational coarsest partition on a transition system. We provide the first linear time algorithm to ca…
Term Rewriting on GPUs
Johri van Eerd, Jan Friso Groote, Pieter Hijma +2
We present a way to implement term rewriting on a GPU. We do this by letting the GPU repeatedly perform a massively parallel evaluation of all subterms. We find that if the term re…
Regular resynchronizability of origin transducers is undecidable
Denis Kuperberg, Jan Martens
We study the relation of containment up to unknown regular resynchronization between two-way non-deterministic transducers. We show that it constitutes a preorder, and that the cor…