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

Résultats de recherche: Contribution à un journal › Article › Revue par des pairs

Résumé

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.

langue originale	Anglais
Pages (de - à)	333-336
Nombre de pages	4
journal	Programming and Computer Software
Volume	40
Numéro de publication	6
Les DOIs	https://doi.org/10.1134/S0361768814060140
état	Publié - 1 janv. 2014
Modification externe	Oui

Accès au document

10.1134/S0361768814060140

Contient cette citation

@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",

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

Résumé

Accès au document

Empreinte digitale

Contient cette citation