2012 •
Tight bound on the length of distinguishing sequences for non-observable nondeterministic Finite-State Machines with a polynomial number of inputs and outputs
Authors: Hwang, Ik Soon, Yevtushenko, Nina, Cavalli, Ana Rosa
Venue: Information Processing Letters
Type: Publication
Abstract: International audience; In this paper we show that the upper bound 2n - 2 on the length of input sequences that distinguish two sets of states is tight for a non-observable NFSM with n states and a polynomial number of inputs and outputs. For each n>=2, there exists a non-observable NFSM M with n states, a single input symbol, and n output symbols such that there are two sets of states in M which are not distinguishable by each input sequence of length 2n - 3 but can be distinguished by an input sequence of length 2n - 2.
Popularity: This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the
underlying citation network.
Influence: This indicator reflects the overall/total impact of an article in the research community at large, based on the
underlying citation network (diachronically).
Citation Count: This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in
the research community at large, based on the underlying citation network (diachronically).
Impulse: This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation
network.
We have placed cookies on your device to help make this website and the services we offer better. By using this site, you agree to the use of cookies. Learn more