On computing indistinguishable states of nondeterministic finite automata with partially observable transitions

In this paper we consider the computation of indistinguishable state pairs of nondeterministic finite automata where some transitions of the automata are observable whereas other transitions are not observable. Two states are indistinguishable if they are reached from the initial state of their corresponding automaton by sequences of transitions that are observationally identical. We review a known algorithm for computing indistinguishable state pairs of automata. We demonstrate for a specific parameterized example that this algorithm is in Θ(|X|⁴·|Σ|) where X is the state set and Σ the event set of the input automaton. We define a product on nondeterministic finite automata which can be used for computing indistinguishable state pairs of automata. When the input automaton is deterministic (respectively, nondeterministic) with respect to its observable transitions, computation of indistinguishable state pairs by use of the product is in O(|X|²·|Σ| + |X|³) (resp., O(|X|⁴·|Σ|)).