同步格值自动机的约简和最小化算法

引入了完备L-Fuzzy矩阵的概念,提出了取值于格半群上的输入字符和输出字符长度相同的模糊自动机的概念,即完备的同步格值自动机的概念,研究了它的主要性质;从行为矩阵出发,给出了完备的同步格值自动机状态等价和自动机等价的定义,从自动机的状态等价,研究了该自动机可约简的条件,并得到了该自动机的最小化算法。     

格值有限自动机等价判定算法

引入了完备L-Fuzzy矩阵的概念,给出了基于格半群的模糊有限自动机的形式化定义,即完备格值有限自动机,研究了它的主要性质;给出了完备格值有限自动机的行为矩阵,从行为矩阵出发,给出了自动机状态等价和自动机等价的定义。最后,得到了该类自动机等价的判定算法。     

加权有穷自动机的代数性质

在加权有穷自动机理论基础上,利用强同态的概念,证明两个加权有穷自动机在计算能力上是等价的,并在加权有穷自动机的状态集上建立一种等价关系,得到加权有穷自动机的商自动机,证明加权有穷自动机与其商自动机在计算能力上也是等价的。并通过引入加权有穷自动机的可交换性、分离性、(强)连通性及层的概念,讨论在(强)同态的条件下,两个加权有限状态机之间的可交换性、分离性、(强)连通性及层的关系。关键词：     

Bulking II: Classifications of cellular automata

This paper is the second part of a series of two papers dealing with bulking: a way to define quasi-order on cellular automata by comparing space-time diagrams up to rescaling. In the present paper, we introduce three notions of simulation between cellular automata and study the quasi-order structures induced by these simulation relations on the whole set of cellular automata. Various aspects of these quasi-orders are considered (induced equivalence relations, maximum elements, induced orders, etc.) providing several formal tools allowing to classify cellular automata.     

A general definition of stochastic automata

A new class of stochastic automata is defined. Its elements, called dependent automata, are characterized by a partition on the set of states such that the transition between the blocks is defined deterministicly. The definitions of isomorphism and equivalence are adapted. Some relations with other classes of stochastic automata and subclasses of dependent automata are defined.     

Algorithms for minimization of finite acyclic automata and pattern matching in terms

Two equivalence relations for finite acyclic automata are considered and minimization algorithms for these automata are described. From these algorithms we develop algorithms for deciding identity of terms, matching of subterms, and pattern matching in terms, which allow for commutativity and associativity of operations.Translated from Kibernetika, No. 3, pp. 11–16, May–June, 1991.     

Algebraic properties of complete residuated lattice valued tree automata

This paper investigates tree automata based on complete residuated lattice valued (referred to as L-valued) logic. First, we define the notions of L-valued set of pure subsystems and L-valued set of strong pure subsystems, as well as, their relation is considered. Also, L-valued n-tuple operator consist of n successors is defined, some of its properties are examined and its relation with pure subsystem is analyzed. Furthermore, we investigate some concepts such as L-valued set of (strong) homomorphisms, L-valued set of (strong) isomorphisms, and L-valued set of admissible relations. Moreover, we discuss bifuzzy topological characterization of L-valued tree automata. Finally, the relations of homomorphisms between the L-valued tree automata to continuous mappings and open mappings is examined.     

Axiomatising timed automata

Timed automata has been developed as a basic semantic model for real time systems. Its algorithmic aspects for automated analysis have been well studied. But so far there is still no satisfactory algebraic theory to allow the derivation of semantical equivalence of automata by purely syntactical manipulation. The aim of this paper is to provide such a theory. We present an inference system of timed bisimulation equivalence for timed automata based on a CCS-style regular language for describing timed automata. It consists of the standard monoid laws for bisimulation and a set of inference rules. The judgments of the proof system are conditional equations of the form where is a clock constraint and t,u are terms denoting timed automata. The inference system is shown to be sound and complete for timed bisimulation. The proof of the completeness result relies on the notion of symbolic timed bisimulation, adapted from the work on value–passing processes. Received: 10 May 2001 / 22 October 2001     

Weak equivalence of automata

A generalization of Moore's theorem of weak equivalence of automata is derived. The weak equivalence problem and the existence problems of homing and diagnosing input-output sequences in an automaton are shown to be polynomially complete.Translated from Kibernetika, No. 5, pp. 85–89, September–October, 1990.     

Regular prefix relations

We define a class ofn-ary relations on strings called the regular prefix relations, and give four alternative characterizations of this class:

1. the relations recognized by a new type of automaton, the prefix automata,
2. the relations recognized by tree automata specialized to relations on strings,
3. the relations between strings definable in the second order theory ofk successors,
4. the smallest class containing the regular sets and the prefix relation, and closed under the Boolean operations, Cartesian product, projection, explicit transformation, and concatenation with Cartesian products of regular sets.

We give concrete examples of regular prefix relations, and a pumping argument for prefix automata. An application of these results to the study of inductive inference of regular sets is described.     

I-Fuzzy equivalence relations and I-fuzzy partitions

A T-fuzzy equivalence relation is a fuzzy binary relation on a set X which is reflexive, symmetric and T-transitive for a t-norm T. Recently, Mesiar et al. [R. Mesiar, B. Reusch, H. Thiele, Fuzzy equivalence relations and fuzzy partitions, J. Multi-Valued Logic Soft Comput. 12 (2006) 167-181] have generalised the t-norm T to any general conjunctor C and investigated the minimal assumptions required on such operations, called duality fitting conjunctors, such that the fuzzification of the equivalence relation admits any value from the unit interval and also the one-one correspondence between the fuzzy equivalence relations and fuzzy partitions is preserved. In this work, we conduct a similar study by employing a related form of C-transitivity, viz., I-transitivity, where I is an implicator. We show that although every I-fuzzy equivalence relation can be shown to be a C-fuzzy equivalence relation, there exist C-fuzzy equivalence relations that are not I-fuzzy equivalence relations and hence these concepts are not equivalent. Most importantly, we show that the class of duality fitting implicators I is much richer than the residuals of the duality fitting conjunctors in the study of Mesiar et al. We also show that the I-fuzzy partitions have a “constant-wise” structure.     

主动自动机学习中的等价查询算法优化

模型学习是一种获取黑盒软件系统行为模型的有效方法,可分为主动学习和被动学习.主动学习是基于字母表构造测试用例,通过与黑盒系统主动交互,可在多项式时间内得到目标系统的最小完备自动机,其中等价查询仍是开发和应用主动自动机学习工具的障碍之一.通过探讨反例对于学习算法的影响,定义假设的比较规则,提出测试用例构造的两个原则,同时依据原则对Wp-method等价查询算法改进,产生更优的假设,有效降低查询的数量,并基于LearnLib开源工具,分别以3类自动机为实验对象验证原则和改进算法的有效性.     

Robustness of fuzzy reasoning via logically equivalence measure

In this paper, we discuss robustness of fuzzy reasoning. After proposing the definition of perturbation of fuzzy sets based on some logic-oriented equivalence measure, we present robustness results for various fuzzy logic connectives, fuzzy implication operators, inference rules and fuzzy reasoning machines, and discuss the relations between the robustness of fuzzy reasoning and that of fuzzy conjunction and implication operators. The robustness results are presented in terms of δ-equalities of fuzzy sets based on some logic-oriented equivalence measure, and the maximum of δ (which ensures the corresponding δ-equality holds) is derived.     

On the expressive power of behavioral profiles

Behavioral profiles have been proposed as a behavioral abstraction of dynamic systems, specifically in the context of business process modeling. A behavioral profile can be seen as a complete graph over a set of task labels, where each edge is annotated with one relation from a given set of binary behavioral relations. Since their introduction, behavioral profiles were argued to provide a convenient way for comparing pairs of process models with respect to their behavior or computing behavioral similarity between process models. Still, as of today, there is little understanding of the expressive power of behavioral profiles. Via counter-examples, several authors have shown that behavioral profiles over various sets of behavioral relations cannot distinguish certain systems up to trace equivalence, even for restricted classes of systems represented as safe workflow nets. This paper studies the expressive power of behavioral profiles from two angles. Firstly, the paper investigates the expressive power of behavioral profiles and systems captured as acyclic workflow nets. It is shown that for unlabeled acyclic workflow net systems, behavioral profiles over a simple set of behavioral relations are expressive up to configuration equivalence. When systems are labeled, this result does not hold for any of several previously proposed sets of behavioral relations. Secondly, the paper compares the expressive power of behavioral profiles and regular languages. It is shown that for any set of behavioral relations, behavioral profiles are strictly less expressive than regular languages, entailing that behavioral profiles cannot be used to decide trace equivalence of finite automata and thus Petri nets.     

两类具有输出字符功能的模糊自动机的关系

在文中,对文献8中介绍的具有输出字符功能的模糊自动机和模糊有限状态自动机的定义作了修改,并对它们进行了系统的研究,揭示了此两类自动机和取分配格的代数性质的紧密联系;得到了此两类自动机在:(1)强等价;(2)等价;(3)弱等价条件下的许多重要结论。     

格值交替树自动机

交替（树）自动机因其本身关于取补运算的简洁性及其与非确定型（树）自动机的等价性,成为自动机与模型检测领域研究的一个新方向.在格值交替自动机与经典交替树自动机概念的基础上,引入格值交替树自动机的概念,并研究了格值交替树自动机的代数封闭性和表达能力.首先,证明了对格值交替树自动机的转移函数取对偶运算,终止权重取补之后所得自动机与原自动机接受语言互补这一结论.其次,证明了格值交替树自动机关于交、并运算的封闭性.最后,讨论了格值交替树自动机和格值树自动机、格值非确定型自动机的表达能力;证明了格值交替树自动机与格值树自动机的等价性,并给出了二者相互转化的算法及其复杂度分析;同时,提供了用格值非确定型自动机来模拟格值交替树自动机的方法.     

Design of effective automaton-reduction algorithms for some equivalence relations

The design of fast minimization algorithms of finite automata is considered for two equivalence relations. The design is carried out in formal terms utilizing the properties of the functions used for minimization.Translated from Kibernetika, No. 6, pp. 54–61, November–December, 1989.     

The problem of equivalent transformations for homogeneous multitape automata

A complete system of equivalent transformations is constructed for homogeneous multitape automata. Decidability of the equivalence problem is established.     

On the power of parallel communicating Watson–Crick automata systems

Parallel communicating Watson–Crick automata systems were introduced in [E. Czeizler, E. Czeizler, Parallel communicating Watson–Crick automata systems, in: Z. Ésik, Z. Fülöp (Eds.), Proc. Automata and Formal Languages, Dobogókő, Hungary, 2005, pp. 83–96] as possible models of DNA computations. This combination of Watson–Crick automata and parallel communicating systems comes as a natural extension due to the new developments in DNA manipulation techniques. It is already known, see [D. Kuske, P. Weigel, The Role of the Complementarity Relation in Watson–Crick Automata and Sticker Systems, DLT 2004, Lecture Notes in Computer Science, Vol. 3340, Auckland, New Zealand, 2004, pp. 272–283], that for Watson–Crick finite automata, the complementarity relation plays no active role. However, this is not the case when considering parallel communicating Watson–Crick automata systems. In this paper we prove that non-injective complementarity relations increase the accepting power of these systems. We also prove that although Watson–Crick automata are equivalent to two-head finite automata, this equivalence is not preserved when comparing parallel communicating Watson–Crick automata systems and multi-head finite automata.