Name
Title | ||
|---|---|---|
Empirical studies in the size of diagnosers and verifiers for diagnosability analysis. |
Abstract | ||
|---|---|---|
Diagnosability is an intrinsic property of the language generated by discrete event systems (DES) and the computational procedure to determine whether a language possesses or not this property is called diagnosability verification. For regular languages, diagnosability verification is carried out by building either diagnoser or verifier automata; the former is known to have worst-case exponential complexity whereas the latter has polynomial complexity in the size of state space of the automaton that generates the language. A question that has been asked for some time now is whether, in average, the state size of diagnosers is no longer exponential. This claim has been supported by the size of diagnoser automata usually obtained in practical and classroom examples, having, in some cases, state space size much smaller than that of verifiers. In an effort to clarify this matter, in this paper we carry out an experimental study on the average state size of diagnosers and verifiers by means of two experiments: an , in which ten sets of automata with moderate cardinality were generated and for these sets of automata, diagnosers and verifiers were built, being the exact average state size for these specific instances calculated; , which considers 1660 sets of different instance sizes and, for each one, sample sets of 10,000 automata are randomly generated with uniform distribution and we compute sets of diagnosers and verifiers for each set of randomly generated automata, which have been used to estimate an asymptotic model for the average state sizes of diagnosers and verifiers. |
Year | DOI | Venue |
|---|---|---|
2017 | https://doi.org/10.1007/s10626-017-0260-y | Discrete Event Dynamic Systems |
Keywords | Field | DocType |
Discrete-event systems,Automaton,Language diagnosability verification,Scientific computation | Discrete mathematics,Intrinsic and extrinsic properties (philosophy),Exponential function,Automaton,Uniform distribution (continuous),Cardinality,Theoretical computer science,Sampling (statistics),Regular language,State space,Mathematics | Journal |
Volume | Issue | ISSN |
27 | 4 | 0924-6703 |
Citations | PageRank | References |
1 | 0.35 | 9 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Leonardo B. Clavijo | 1 | 1 | 0.35 |
| JoãO C. Basilio | 2 | 151 | 15.63 |