An improved upper bound for the length of preset distinguishing sequences of distinguished merging finite state machines
Güniçen, Canan and İnan, Kemal and Türker, Uraz Cengiz and Yenigün, Hüsnü (2014) An improved upper bound for the length of preset distinguishing sequences of distinguished merging finite state machines. In: 29th International Symposium on Computer and Information Sciences (ISCIS 2014), Krakow, Poland
Full text not available from this repository.
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).
Repository Staff Only: item control page