Questions tagged [lts-simulations]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
4
votes
1answer
89 views

Design a sampling process to select an element with probability proportional to its appear probability in a simulation

We are given a black box $A$ that can do a simulation. Each time running box A gives a sample $S \in 2^X$ where $X$ is a finite ground set. Let $\Pr[x]$ be the probability that $x \in X$ appears in ...
4
votes
1answer
125 views

Is there an algorithm for minimizing an NFA with respect to bisimilarity rather than language equivalence?

DFA minimization is the problem of transforming a given automaton to an equivalent one with the minimum number of states. Equivalence is taken to be language equivalence. Milner introduced the notion ...
1
vote
0answers
64 views

Why are simulations defined as relations and not as functions?

I am interested in simulations between labelled transition systems (LTS). LTS are basically relational systems, in particular they can be viewed as structures for a purely binary relational signature ...