Back to Search
Start Over
Tight bound on the length of distinguishing sequences for non-observable nondeterministic Finite-State Machines with a polynomial number of inputs and outputs
- Source :
- Information processing letters. 2012. Vol. 112, № 7. P. 298-301, Information Processing Letters, Information Processing Letters, Elsevier, 2012, 112 (7), pp.298-301. ⟨10.1016/j.ipl.2011.12.012⟩
- Publication Year :
- 2012
-
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.
- Subjects :
- Existential quantification
Non-observable machine
Distinguishing sequence
02 engineering and technology
Upper and lower bounds
недетерминированные конечные автоматы
программное обеспечение
Theoretical Computer Science
Combinatorics
[INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI]
0202 electrical engineering, electronic engineering, information engineering
Polynomial number
Mathematics
Discrete mathematics
Sequence
Finite-state machine
Software engineering
020207 software engineering
Observable
16. Peace & justice
Computer Science Applications
Nondeterministic algorithm
Symbol (programming)
Signal Processing
020201 artificial intelligence & image processing
Nondeterministic finite-state machine
Information Systems
Subjects
Details
- Language :
- Russian
- ISSN :
- 00200190
- Database :
- OpenAIRE
- Journal :
- Information processing letters. 2012. Vol. 112, № 7. P. 298-301, Information Processing Letters, Information Processing Letters, Elsevier, 2012, 112 (7), pp.298-301. ⟨10.1016/j.ipl.2011.12.012⟩
- Accession number :
- edsair.doi.dedup.....dfa090b63d9a4fb8b791019c9f85becb