An improved upper bound for the length of preset distinguishing sequences of distinguished merging finite state machines

Official URL: http://dx.doi.org/10.1007/978-3-319-09465-6_34

In an earlier work, we have studied a special class of Finite State Machines (FSMs) called Distinguished Merging FSMs (DMFSMs) and showed that one can construct a Preset Distinguishing Sequence (PDS) for a DMFSM with n states, p input symbols, and r output symbols in time O(n^4 + pn^2) of length no longer than O(n^3). In this work, we improve the upper bound for the length of a PDS to (n-1)^2, and present an algorithm to construct such a PDS for a DMFSM in time O(n^4 + pn^2) or in time O(rn^3 + pn^2).