On the complexity of existence of homing sequences for nondeterministic finite state machines

N. G. Kushik; V. V. Kulyamin; N. V. Evtushenko

doi:10.1134/S0361768814060140

On the complexity of existence of homing sequences for nondeterministic finite state machines

N. G. Kushik
, V. V. Kulyamin
, N. V. Evtushenko

Tomsk State University
Ivannikov Institute for System Programming of the RAS

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

8 Citations (Scopus)

Abstract

The paper discusses complexity of the problem of checking existence of a homing sequence for an observable complete finite state machines (FSMs). The minimum length of such a sequence for FSMs of certain class is known to be exponential in the number of the FSM states. It is shown that the problem of checking the existence of such a sequence belongs to class PSPACE.

Original language	English
Pages (from-to)	333-336
Number of pages	4
Journal	Programming and Computer Software
Volume	40
Issue number	6
DOIs	https://doi.org/10.1134/S0361768814060140
Publication status	Published - 1 Jan 2014
Externally published	Yes

Access to Document

10.1134/S0361768814060140

Cite this

@article{2b4090f2eec5456eb89d7550b83c24ee,

title = "On the complexity of existence of homing sequences for nondeterministic finite state machines",

abstract = "The paper discusses complexity of the problem of checking existence of a homing sequence for an observable complete finite state machines (FSMs). The minimum length of such a sequence for FSMs of certain class is known to be exponential in the number of the FSM states. It is shown that the problem of checking the existence of such a sequence belongs to class PSPACE.",

author = "Kushik, \{N. G.\} and Kulyamin, \{V. V.\} and Evtushenko, \{N. V.\}",

note = "Publisher Copyright: {\textcopyright} 2014, Pleiades Publishing, Ltd.",

year = "2014",

month = jan,

day = "1",

doi = "10.1134/S0361768814060140",

language = "English",

volume = "40",

pages = "333--336",

journal = "Programming and Computer Software",

issn = "0361-7688",

publisher = "Pleiades Publishing",

number = "6",

}

TY - JOUR

T1 - On the complexity of existence of homing sequences for nondeterministic finite state machines

AU - Kushik, N. G.

AU - Kulyamin, V. V.

AU - Evtushenko, N. V.

PY - 2014/1/1

Y1 - 2014/1/1

N2 - The paper discusses complexity of the problem of checking existence of a homing sequence for an observable complete finite state machines (FSMs). The minimum length of such a sequence for FSMs of certain class is known to be exponential in the number of the FSM states. It is shown that the problem of checking the existence of such a sequence belongs to class PSPACE.

AB - The paper discusses complexity of the problem of checking existence of a homing sequence for an observable complete finite state machines (FSMs). The minimum length of such a sequence for FSMs of certain class is known to be exponential in the number of the FSM states. It is shown that the problem of checking the existence of such a sequence belongs to class PSPACE.

U2 - 10.1134/S0361768814060140

DO - 10.1134/S0361768814060140

M3 - Article

AN - SCOPUS:84920191785

SN - 0361-7688

VL - 40

SP - 333

EP - 336

JO - Programming and Computer Software

JF - Programming and Computer Software

IS - 6

ER -

On the complexity of existence of homing sequences for nondeterministic finite state machines

Abstract

Access to Document

Fingerprint

Cite this