The complexity of checking the existence and derivation of adaptive synchronizing experiments for deterministic FSMs

Hüsnü Yenigün; Nina Yevtushenko; Natalia Kushik

doi:10.1016/j.ipl.2017.07.001

The complexity of checking the existence and derivation of adaptive synchronizing experiments for deterministic FSMs

Hüsnü Yenigün
, Nina Yevtushenko
, Natalia Kushik

Research output: Contribution to journal › Article › peer-review

Abstract

In this paper, we address the problem of setting a deterministic Finite State Machine (FSM) to a designated initial state. Differently from other papers, we propose to use adaptive synchronizing sequences (test cases) for this purpose and show that for weakly-connected deterministic complete reduced FSMs the problem of checking the existence of an adaptive synchronizing sequence is in P. For partial deterministic reduced FSMs the problem is PSPACE-complete.

Original language	English
Pages (from-to)	49-53
Number of pages	5
Journal	Information Processing Letters
Volume	127
DOIs	https://doi.org/10.1016/j.ipl.2017.07.001
Publication status	Published - 1 Nov 2017
Externally published	Yes

Keywords

Adaptive sequences
Deterministic finite state machines
Formal methods
Synchronizing experiments

Access to Document

10.1016/j.ipl.2017.07.001

Cite this

@article{856ec77eb8a04f0a90bb52ad426571e6,

title = "The complexity of checking the existence and derivation of adaptive synchronizing experiments for deterministic FSMs",

abstract = "In this paper, we address the problem of setting a deterministic Finite State Machine (FSM) to a designated initial state. Differently from other papers, we propose to use adaptive synchronizing sequences (test cases) for this purpose and show that for weakly-connected deterministic complete reduced FSMs the problem of checking the existence of an adaptive synchronizing sequence is in P. For partial deterministic reduced FSMs the problem is PSPACE-complete.",

keywords = "Adaptive sequences, Deterministic finite state machines, Formal methods, Synchronizing experiments",

author = "H{\"u}sn{\"u} Yenig{\"u}n and Nina Yevtushenko and Natalia Kushik",

note = "Publisher Copyright: {\textcopyright} 2017 Elsevier B.V.",

year = "2017",

month = nov,

day = "1",

doi = "10.1016/j.ipl.2017.07.001",

language = "English",

volume = "127",

pages = "49--53",

journal = "Information Processing Letters",

issn = "0020-0190",

}

TY - JOUR

T1 - The complexity of checking the existence and derivation of adaptive synchronizing experiments for deterministic FSMs

AU - Yenigün, Hüsnü

AU - Yevtushenko, Nina

AU - Kushik, Natalia

PY - 2017/11/1

Y1 - 2017/11/1

N2 - In this paper, we address the problem of setting a deterministic Finite State Machine (FSM) to a designated initial state. Differently from other papers, we propose to use adaptive synchronizing sequences (test cases) for this purpose and show that for weakly-connected deterministic complete reduced FSMs the problem of checking the existence of an adaptive synchronizing sequence is in P. For partial deterministic reduced FSMs the problem is PSPACE-complete.

AB - In this paper, we address the problem of setting a deterministic Finite State Machine (FSM) to a designated initial state. Differently from other papers, we propose to use adaptive synchronizing sequences (test cases) for this purpose and show that for weakly-connected deterministic complete reduced FSMs the problem of checking the existence of an adaptive synchronizing sequence is in P. For partial deterministic reduced FSMs the problem is PSPACE-complete.

KW - Adaptive sequences

KW - Deterministic finite state machines

KW - Formal methods

KW - Synchronizing experiments

UR - https://www.scopus.com/pages/publications/85023638863

U2 - 10.1016/j.ipl.2017.07.001

DO - 10.1016/j.ipl.2017.07.001

M3 - Article

AN - SCOPUS:85023638863

SN - 0020-0190

VL - 127

SP - 49

EP - 53

JO - Information Processing Letters

JF - Information Processing Letters

ER -

The complexity of checking the existence and derivation of adaptive synchronizing experiments for deterministic FSMs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this