2
$\begingroup$

Suppose $L$ is a labelled transition system (LTS). Suppose that the function $maxIn(L)$ (LTS $\rightarrow$ integer) returns the number of incoming transitions to the state of $L$ that has the most incoming transitions of all states of $L$. So, for example, if $L$ is a tree with the root as its only initial state then $maxIn(L) = 1$.

Now suppose that $traceEq(L)$ denotes the set of LTS that are trace equivalent to $L$. So if $L1, L2 \in traceEq(L)$ and $L1 \neq L2$ then $L1$ and $L2$ are not topologically isomorphic but have the same set of traces as $L$. Note that $L \in traceEq(L)$.

Given an LTS $L$ is there any algorithmic way of determining the value of $min_{L' \in traceEq(L)} maxIn(L')$ ? The case of interest is where all the members of $traceEq(L)$ are finite, so that a cycle in $L$ cannot be unwound and represented by an infinite sequence of states.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.