一种基于Mealy自动机的策略监控模型

策略监控是完善策略管理系统、提高系统可靠性,并为第三方审计提供依据的有效途径之一。对策略整个生命周期中的状态进行了划分,引入Mealy自动机,对整个状态转换过程进行了建模,明确了监控对象及分析依据,从而实现了对策略状态的宏观监控,即通过合法性判定算法对策略进行的操作进行判定。最后,通过对自动机模型及判定算法的程序实现与性能测试可以看出,该算法能够及时有效地对事件数据进行处理响应。     

Probabilistic asynchronous automata

Asynchronous automata were introduced by W. Zielonka as an algebraic model of distributed systems, showing that the class of trace languages recognizable by automata over free partially commutative monoids coincides with the class of trace languages recognizable by deterministic asynchronous automata. In this paper we extend the notion of asynchronous automata to the probabilistic case. Our main result is a nontrivial generalization to Zielonka's theorem: we prove that the sets of behaviors of probabilistic automata and of probabilistic asynchronous automata coincide in the case of concurrent alphabets with acyclic dependency graphs. This research has been supported by European Projects EBRA Nos. 3148 (DEMON), 3166 (ASMICS), and 6317 (ASMICS2), by MURST 40%, and by the CNR Project “Modelli di Computazione Parallela.”     

Compositional synthesis of asynchronous automata

Asynchronous automata are a model of communication processes with a control structure distributed on a set P of processes, global initializations and global accepting conditions. The well-known theorem of Zielonka states that they recognize exactly the class of regular Mazurkiewicz trace languages. The corresponding synthesis problem is, given a global specification A of any regular trace language L, to build an asynchronous automaton that recognizes L, automatically. Yet, all such existing constructions are quite involved and yield an explosion of the number of states in each process, which is exponential in both the sizes of A and P. In this paper, we introduce the particular case of distributed asynchronous automata, which require that the initializations and the accepting conditions are distributed as well. We present an original technique based on simple compositions/decompositions of these distributed asynchronous automata that results in the construction of smaller non-deterministic asynchronous automata: now, the number of states in each process is only polynomial in the size of A, but is still exponential in the size of P.     

Representations of commutative asynchronous automata

Ito (1976, 1978) [14], [17] provided representations of strongly connected automata by group-matrix type automata. This shows the close connection between strongly connected automata with their automorphism groups. In this paper we deal with commutative asynchronous automata. In particular, we introduce and study normal commutative asynchronous automata and cyclic commutative asynchronous automata. Some properties on endomorphism monoids of these automata are given. Also, the representations of normal commutative asynchronous automata and cyclic commutative asynchronous automata are provided by S-automata and regular S-automata, respectively. The cartesian composition $\mathbf{A}°\mathbf{B}$ of a strongly connected automaton A and a cyclic commutative asynchronous automaton B is studied. It is shown that the endomorphism monoid $E(\mathbf{A}°\mathbf{B})$ of automaton $\mathbf{A}°\mathbf{B}$ is a Clifford monoid. Finally, a representation of $\mathbf{A}°\mathbf{B}$ is provided by regular Clifford monoid matrix-type automaton. This generalizes and extends the representations of strongly connected automata given by Ito (1976) [14].     

Pushdown automata on arrays

This paper deals with some properties of pushdown automata (PDAs) on two-dimensional arrays. In particular, it is shown that there exists a deterministic array-bounded PDA which can traverse any simply connected pattern and halt when the traversal is complete.     

Deterministic asynchronous automata for infinite traces

This paper shows the equivalence between the family of recognizable languages over infinite traces and the family of languages which are recognized by deterministic asynchronous cellular Muller automata. We thus give a proper generalization of McNaughton's Theorem from infinite words to infinite traces. Thereby we solve one of the main open problems in this field. As a special case we obtain that every closed (w.r.t. the independence relation) word language is accepted by someI-diamond deterministic Muller automaton.This research has been supported by the ESPRIT Basic Research Action No. 6317 ASMICS 2.     

Construction universality in purely asynchronous cellular automata

Universality in cellular automata (CAs), first studied by von Neumann, has attracted much research efforts over the years, especially for CA employing synchronous timing. This paper proposes a computation- and construction-universal CA with a von Neumann neighborhood that is updated in a purely asynchronous way, rather than by the conventional but less efficient way of simulating synchronous CAs on asynchronous CAs. The proposed asynchronous CA is capable of implementing self-reproducing machines. Our model employs strongly symmetric cells with 15 states.