BIP! Finder - Tight bound on the length of distinguishing sequences for non-observable nondeterministic Finite-State Machines with a polynomial number of inputs and outputs

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, Iksoon; Yevtushenko, Nina V.; Cavalli, Ana

Venue: Information Processing Letters

Type: Publication

Abstract: In this paper we show that the upper bound 2^n-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 2^n-3 but can be distinguished by an input sequence of length 2^n-2.

Impact:

8.9717095E-10 3.4618566E-9 4 2

/ Attention: 0 10

Topics: Combinatorics Discrete mathematics

DOI: 10.1016/j.ipl.2011.12.012

External links: Crossref OpenAIRE

BibTex PDF

Topic-specific impact indicators

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.