Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
New Channel Access Approach for the IEEE 802.15.4 Devices in 2.4 GHz ISM Band Read chapter Read first chapter

2014 | OriginalPaper | Chapter

An Improved Upper Bound for the Length of Preset Distinguishing Sequences of Distinguished Merging Finite State Machines

Authors : Canan Güniçen, Kemal İnan, Uraz Cengiz Türker, Hüsnü Yenigün

Published in: Information Sciences and Systems 2014

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In an earlier work, we have studied a special class of FiniteState 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)\).

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter On-Demand Prefetching Heuristic Policies: A Performance Evaluation
next chapter Time Parallel Simulation for Dynamic Fault Trees
Literature
1.
A.V. Aho, R. Sethi, J.D. Ullman, Compilers: Principles, Techniques, and Tools (Addison-Wesley, Reading, 1986)
2.
M. Barnett, W. Grieskamp, L. Nachmanson, W. Schulte, N. Tillmann, M. Veanes, Towards a tool environment for model-based testing with AsmL. in Formal Approaches to Testing, volume 2931 of Lecture Notes in Computer Science, pp. 252–266, Montreal, Canada, 2003. Springer-Verlag
3.
R.V. Binder, Testing Object-Oriented Systems: Models, Patterns, and Tools (Addison-Wesley, Reading, 1999)
4.
E.G. Cartaxo, P.D.L. Machado, F.G.O. Neto, On the use of a similarity function for test case selection in the context of model-based testing. Softw. Test. Verif. Reliab. 21(2), 75–100 (2011)CrossRef
5.
T.S. Chow, Testing software design modeled by finite-state machines. IEEE Trans. Softw. Eng. 4(3), 178–187 (1978)CrossRefMATH
6.
A.D. Friedman, P.R. Menon, Fault Detection in Digital Circuits, Computer Applications in Electrical Engineering Series (Prentice-Hall, Englewood Cliffs, 1971)
7.
E. Gelenbe, Regular expressions and checking experiments. Technical Report AD0666696, Polytechnic Institute of Brooklyn NY Microwave Research Institue, September 1967. Defense Technical Information Center
8.
G. Gönenç, A method for the design of fault detection experiments. IEEE Trans. Comput. 19(6), 551–558 (1970)CrossRefMATH
9.
W. Grieskamp, N. Kicillof, K. Stobie, V.A. Braberman, Model-based quality assurance of protocol documentation: tools and methodology. Softw. Test. Verif. Reliab. 21(1), 55–71 (2011)CrossRef
10.
C. Gunicen, K. Inan, U.C. Turker, H. Yenigun, The relation between preset distinguishing sequences and synchronizing sequences. Formal Aspects of Computing (2014)
11.
F.C. Hennie, Fault-detecting experiments for sequential circuits. in: Proceedings of Fifth Annual Symposium on Switching Circuit Theory and Logical Design, pp. 95–110, Princeton, New Jersey, November 1964
12.
R.M. Hierons, G.V. Jourdan, H. Ural, H. Yenigun, Using adaptive distinguishing sequences in checking sequence constructions, in R.L. Wainwright and H. Haddad, editors, SAC, pp. 682–687. ACM, Mar 2008
13.
R.M. Hierons, G.V. Jourdan, H. Ural, H. Yenigun, Checking sequence construction using adaptive and preset distinguishing sequences, in D.V. Hung and P. Krishnan, editors, SEFM, pp. 157–166. IEEE Computer Society, 2009
14.
G.J. Holzmann, Design and Validation of Computer Protocols (Prentice Hall, Englewood Cliffs, 1991)
15.
Z. Kohavi, Switching and Finite State Automata Theory (McGraw-Hill, NY, 1978)
16.
D. Lee, M. Yannakakis, Testing finite-state machines: State identification and verification. IEEE Trans. Comput. 43(3), 306–320 (1994)CrossRefMathSciNet
17.
D. Lee, M. Yannakakis, Principles and methods of testing finite-state machines—a survey. Proc. the IEEE 84(8), 1089–1123 (1996)CrossRef
18.
A. Petrenko, N. Yevtushenko, Testing from partial deterministic FSM specifications. IEEE Trans. Comput. 54(9), 1154–1165 (2005)CrossRef
19.
Metadata
Title
An Improved Upper Bound for the Length of Preset Distinguishing Sequences of Distinguished Merging Finite State Machines
Authors
Canan Güniçen
Kemal İnan
Uraz Cengiz Türker
Hüsnü Yenigün
Copyright Year
2014
Book
Information Sciences and Systems 2014

Print ISBN: 978-3-319-09464-9

Electronic ISBN: 978-3-319-09465-6

Copyright Year: 2014

DOI
https://doi.org/10.1007/978-3-319-09465-6_34

Premium Partner

    Image Credits