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.


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.