Yenigün, Hüsnü and Yevtushenko, Nina and Kushik, Natali (2017) The complexity of checking the existence and derivation of adaptive synchronizing experiments for deterministic FSMs. Information Processing Letters, 127 . pp. 49-53. ISSN 0020-0190 (Print) 1872-6119 (Online)
Full text not available from this repository. (Request a copy)
Official URL: http://dx.doi.org/10.1016/j.ipl.2017.07.001
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.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | Adaptive sequences; Deterministic finite state machines; Formal methods; Synchronizing experiments |
| Subjects: | Q Science > QA Mathematics > QA075 Electronic computers. Computer science |
| Divisions: | Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng. Faculty of Engineering and Natural Sciences |
| Depositing User: | Hüsnü Yenigün |
| Date Deposited: | 20 Aug 2017 20:30 |
| Last Modified: | 20 Aug 2017 20:30 |
| URI: | https://research.sabanciuniv.edu/id/eprint/32767 |
Actions (login required)
- View Item