Empirical studies in the size of diagnosers and verifiers for diagnosability analysis
Empirical studies in the size of diagnosers and verifiers for diagnosability analysis
复制标题
DOI：
10.1007/s10626-017-0260-y
复制
发表时间：
2017-08
期刊：
影响因子：
--
通讯作者：
Leonardo B. Clavijo;J. Basilio
中科院分区：
文献类型：
--
作者：
Leonardo B. Clavijo;J. Basilio
可诊断性是由离散事件系统（DES）生成的语言的一种内在属性，判断一种语言是否具有这种属性的计算过程称为可诊断性验证。对于正则语言，可诊断性验证是通过构建诊断自动机或验证自动机来进行的;前者已知具有最坏情况的指数复杂度，而后者具有生成语言的自动机的状态空间大小的多项式复杂度。一段时间以来，人们一直在问一个问题，即平均而言，诊断器的状态大小是否不再是指数级的。这一主张得到了支持的诊断自动机的大小通常在实际和课堂上的例子中获得，在某些情况下，状态空间的大小远小于验证。为了澄清这一问题，本文通过两个实验对诊断器和验证器的平均状态大小进行了实验研究：（i）穷举实验，生成了10组具有中等基数的自动机，并为这些自动机建立了诊断器和验证器，计算出这些特定实例的精确平均状态大小;（ii）抽样实验，考虑1660组不同大小的实例，每组10个样本，000自动机随机生成的均匀分布，我们计算组的诊断和验证的每一组随机生成的自动机，这已被用来估计一个渐近模型的平均状态大小的诊断和验证。
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:(i)anexhaustive experiment, 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;(ii)an experiment with sampling, 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.