On synchronized evolution of the network of automata

One of the tasks in machine learning is to build a device that predicts each next input symbol of a sequence as it takes one input symbol from the sequence. We studied new approaches to this task. We suggest that deterministic finite automata (DFA) are good building blocks for this device, together with genetic algorithms (GAs), which let these automata "evolve" to predict each next input symbol of the sequence. Moreover, we study how to combine these highly fit automata so that a network of them would compensate for each others' weaknesses and predict better than any single automaton. We studied the simplest approaches to combine automata: building trees of automata with special-purpose automata, which may be called switchboards. These switchboard automata are located on the internal nodes of the tree, take an input symbol from the input sequence just as other automata do, and predict which subtree will make a correct prediction on each next input symbol. GAs again play a crucial role in searching for switchboard automata. We studied various ways of growing trees of automata and tested them on sample input sequences, mainly note pitches, note durations and up/down notes of Bach's Fugue IX. The test results show that DFAs together with GAs seem to be very effective for this type of pattern learning task     

基于矩阵模型的有限自动机的综合

研究如何构造有限自动机，使得每一输入的内动部分的图形为给定的图形，即每一给定的图形为该有限自动机在某输入下的内动部分的图形；对给定的常量布尔方阵C，是否存在满足一定条件的有限自动机，使得该自动机总图的拟邻接矩阵为C，给出了判断的充要条件及构造算法；设计了时序电路模拟自动机，该时序电路实现给定的图形或拟邻接矩阵。     

儿科疾病及保健知识问答系统的构建

儿童健康及疾病诊疗是家庭及社会聚焦的热点,提供准确、有效的信息咨询也是家长和社会的迫切需求。该文以中文医学知识图谱和医学文本为数据来源,以儿科疾病和保健知识为切入点,对多知识来源的自动问答系统进行了研究。系统采用AC自动机(Aho-Corasick automaton)和正则表达式,融合句法结构及关键词特征,对用户输入问题与模板进行匹配,根据模板生成对应的Cypher语句对儿科医学知识图谱及医学文本进行查询和检索,并生成备选答案。采用融合数据来源权威性及匹配度的评分机制对产生的备选答案进行评分,根据评分向用户返回最终答案。系统在某三甲医院投入试用一个月后,根据用户评分反馈,满意度为85.43%。     

Efficient recognition of trace languages defined by repeat-until loops

A sequence of operations may be validly reordered, provided that only pairs of independent operations are commuted. Focusing on a program scheme, idealized as a local finite automaton, we consider the problem of checking whether a given string is a valid permutation of a word recognized by the automaton. Within the framework of trace theory, this is the membership problem for rational trace languages. Existing general algorithms, although time-polynomial, have unbounded degree related to some properties of the dependence graph. Here we present two original linear-time solutions. A straightforward algorithm is suitable for any finite automaton such that all the transitions starting from the same state are labelled by dependent symbols. The second approach is currently restricted to automata representing programs of nested repeat-until loops. Using integer compositions to represent loop iterations and under suitable conditions, the algorithm constructs the syntax tree of a possible word equivalent to the input string. The same procedures show that, under our hypotheses, the uniform version of the membership problem (which is NP-complete in the general case) is solvable in polynomial time.     

Diagnosis of timed automata: Theory and application to the DAMADICS actuator benchmark problem

This paper concerns the problem of fault diagnosis in discrete-event systems which are represented by timed automata. The diagnostic algorithm for timed automata detects and identifies faults in the system based on the investigation whether the measured input and output sequences are consistent with the timed automaton. This diagnostic approach can be applied spontaneously to the discrete-event system since no a priori information about the initial state of the system is required. It is shown in the paper how the timed automaton which represents the DAMADICS actuator can be obtained and how the diagnostic algorithm based on the timed automaton is applied to detect and identify actuator faults. A representative diagnostic result is presented and discussed to illustrate the effectiveness of the method.     

Finite automata theory with membership values in lattices

In this paper, we study finite automata with membership values in a lattice, which are called lattice-valued finite automata. The extended subset construction of lattice-valued finite automata is introduced, then the equivalences between lattice-valued finite automata, lattice-valued deterministic finite automata and lattice-valued finite automata with ε-moves are proved. A simple characterization of lattice-valued languages recognized by lattice-valued finite automata is given, then it is proved that the Kleene theorem holds in the frame of lattice-setting. A minimization algorithm of lattice-valued deterministic finite automata is presented. In particular, the role of the distributive law for the truth valued domain of finite automata is analyzed: the distributive law is not necessary to many constructions of lattice-valued finite automata, but it indeed provides some convenience in simply processing lattice-valued finite automata.     

Isomorphism between two BL-general fuzzy automata

In this note first we develop the notion of general fuzzy automata (GFA) to a new one which is called “BL-general fuzzy automata” and for simplicity, we write BL-GFA, instead of BL-general fuzzy automata. Then we focus on derivation, active state set, membership assignment, output mappings, and concept of belonging to an output label according to the entrance input strings \( X \, (X \in \Upsigma^{ * } ) \) for BL-general fuzzy automata. Therefore, we define the concepts of run map and behavior of BL-GFA. After that we present the morphism with threshold \( \tfrac{{\tau_{1} }}{{\tau_{2} }} \) between two BL-general fuzzy automata. Moreover we give some examples, to clarify these notions. Finally, we prove some theorems. In particular, we show that the isomorphic BL-general fuzzy automata have the same behavior.     

Template languages for fault monitoring of timed discrete eventprocesses

This paper introduces a new framework for modeling discrete event processes. This framework, called condition templates, allows the modeling of processes in which both single-instance and multiple-instance behaviors are exhibited concurrently. A single-instance behavior corresponds to a trace from a single finite-state process, and a multiple-instance behavior corresponds to the timed interleavings of an unspecified number of identical processes operating at the same time. The template framework allows the modeling of correct operation for systems consisting of concurrent mixtures of both single and multiple-instance behaviors. This representation can then be used in online fault monitoring for confirming the correct operation of a system. We compare the class of timed languages representable by template models with classes of timed languages from timed automata models. It is shown that templates are able to model timed languages corresponding to single and multiple-instance behaviors and combinations thereof. Templates can thus represent languages that could not be represented or monitored using timed automata alone     

State Observation and Diagnosis of Discrete-Event Systems Described by Stochastic Automata

The problems ofstate observation and diagnosis are solved for discrete–eventsystems, which are described by stochastic automata. As manysystems are not observable in the sense that it is possible toreconstruct the state unambiguously, the observation problemis set up as the problem of determining the smallest possibleset of states that are compatible with the measured input andoutput sequences. The diagnostic problem is shown to be, in principle,an observation problem. Conditions for the observability anddiagnosability of stochastic automata are presented. The resultsare illustrated by examples.     

UML顺序图与状态图的一致性检查

用户可使用UML从不同角度对系统进行建模,但不同视图间存在信息冗余,可能导致视图不一致问题。该文针对具有多种逻辑语义的顺序图提出分析方法,为复杂层次结构的状态图引入有限状态自动机,利用自动机分解算法得到自动机树。制定新的顺序图和状态图一致性检查准则和Promela代码结构,用模型检验工具SPIN进行顺序图及其相关状态图的一致性检验。     

Cooperating systems of four-dimensional finite automata

M. Blum and C. Hewitt first proposed two-dimensional automata as a computational model of two-dimensional pattern processing in 1967, and investigated their pattern recognition abilities. Since then, many researchers in this field have investigated many properties of automata on a two- or three-dimensional tape. However, the question of whether processing four-dimensional digital patterns is much more difficult than processing two- or three-dimensional ones is of great interest from both theoretical and practical standpoints. Thus, the study of four-dimensional automata as a computational model of four-dimensional pattern processing has been meaningful. This article introduces a cooperating system of four-dimensional finite automata as one model of four-dimensional automata. A cooperating system of four-dimensional finite automata consists of a finite number of four-dimensional finite automata and a four-dimensional input tape, where these finite automata work independently (in parallel). The finite automata whose input heads scan the same cell of the input tape can communicate with each other, i.e., every finite automaton is allowed to know the internal states of other finite automata on the cell it is scanning at the moment. In this article we mainly investigate the accepting powers of a cooperating system of seven-way four-dimensional finite automata. The seven-way four-dimensional finite automaton is a four-dimensional finite automaton whose input head can move east, west, south, north, up, down, or in the future, but not in the past, on a four-dimensional input tape.     

Determinization of fuzzy automata with membership values in complete residuated lattices

In this paper we introduce a new method for determinization of fuzzy finite automata with membership values in complete residuated lattices. In comparison with the previous methods, developed by Bělohlávek [R. Bělohlávek, Determinism and fuzzy automata, Information Sciences 143 (2002), 205-209] and Li and Pedrycz [Y.M. Li, W. Pedrycz, Fuzzy finite automata and fuzzy regular expressions with membership values in lattice ordered monoids, Fuzzy Sets and Systems 156 (2005), 68-92], our method always gives a smaller automaton, and in some cases, when the previous methods result in infinite automata, our method can result in a finite one. We also show that determinization of fuzzy automata is closely related to fuzzy right congruences on a free monoid and fuzzy automata associated with them, and in particular, to the concept of the Nerode’s fuzzy right congruence of a fuzzy automaton, which we introduce and study here.     

MINIMAL VALID AUTOMATA OF SAMPLE SEQUENCES FOR DISCRETE EVENT SYSTEMS

Minimal valid automata (MVA) refer to valid automata models that fit a given input‐output sequence sample from a Mealy machine model. They are minimal in the sense that the number of states in these automata is minimal. Critical to system identification problems of discrete event systems, MVA can be considered as a special case of the minimization problem for incompletely specified sequential machine (ISSM). While the minimization of ISSM in general is an NP‐complete problem, various approaches have been proposed to alleviate computational requirement by taking special structural properties of the ISSM at hand. In essence, MVA is to find the minimal realization of an ISSM where each state only has one subsequent state transition defined. This paper presents an algorithm that divides the minimization process into two phases: first to give a reduced machine for the equivalent sequential machine, and then to minimize the reduced machine into minimal realization solutions. An example with comprehensive coverage on how the associated minimal valid automata are derived is also included.     

Hierarchies based on the number of cooperating systems of three-dimensional finite automata

The question of whether processing three-dimensional digital patterns is much more difficult than two-dimensional ones is of great interest from both theoretical and practical standpoints. Recently, owing to advances in many application areas, such as computer vision, robotics, and so forth, it has become increasingly apparent that the study of three-dimensional pattern processing is of crucial importance. Thus, the study of three-dimensional automata as a computational model of three-dimensional pattern processing has become meaningful. This article introduces a cooperating system of three-dimensional finite automata as one model of three-dimensional automata. A cooperating system of three-dimensional finite automata consists of a finite number of three-dimensional finite automata and a three-dimensional input tape where these finite automata work independently (in parallel). Those finite automata whose input heads scan the same cell of the input tape can communicate with each other, i.e., every finite automaton is allowed to know the internal states of other finite automata on the cell it is scanning at the moment. In this article, we continue the study of cooperating systems of three-dimensional finite automata, and mainly investigate hierarchies based on the number of their cooperating systems.     

ACTAS : A System Design for Associative and Commutative Tree Automata Theory

ACTAS is an integrated system for manipulating associative and commutative tree automata (AC-tree automata for short), that has various functions such as for Boolean operations of AC-tree automata, computing rewrite descendants, and solving emptiness and membership problems. In order to deal with high-complexity problems in reasonable time, over- and under-approximation algorithms are also equipped. Such functionality enables us automated verification of safety property in infinite state models, that is helpful in the domain of, e.g. network security, in particular, for security problems of cryptographic protocols allowing an equational property. In runtime of model construction, a tool support for analysis of state space expansion is provided. The intermediate status of the computation is displayed in numerical data table, and also the line graphs are generated. Besides, a graphical user interface of the system provides us a user-friendly environment for handy use.     

Mamdani模糊系统I/O关系的表示及隶属函数优化

探讨一类高效率Mamdani模糊系统隶属函数优化方法.首先通过严密的理论分析将MISO(多输入单输出)_Mamdani模糊系统的输入/输出函数表示成系统隶属函数的局部线性表达式;论证了这个表达式中系统隶属函数项的系数仅由该点所对应的2p个隶属函数值,按大小排成的序列决定.以此为基础,提出了根据输入/输出样本集误差对系统隶属函数进行优化的新方法.该方法近似地将隶属函数优化问题转换成一组线性规划问题进行求解.本文提供的仿真结果也进一步证实了该方法的有效性.     

Fuzzy automata with fuzzy relief

This paper shows a definition of a fuzzy automaton, which has the state, input, and output sets as fuzzy sets. The state transition function is defined as moving on a fuzzy relief with fuzzy peak-states and boundaries between different membership functions. After the definition of fuzzy automaton with fuzzy relief, the paper deals with a generalization, simulation and realization of such a fuzzy automaton. The paper links the defined fuzzy automaton to an existing fuzzy JK memory cell and to well-known fuzzy automata defined on the basis of crisp sets     

支持扩展虚拟同步的组通信算法形式描述与验证

组通信系统是为方便开发容错的分布式应用系统而提出的一种通信中间件．虚拟同步是组通信系统中的一个重要概念．其本质是限制向所有组成员递交组成员资格变化信息和应用消息的次序．为支持网络可划分的情况，引入了扩展虚拟同步模型．针对扩展虚拟同步模型的特点，提出了一种基于客户／服务器模式的组通信系统架构，并以I／O自动机的形式给出系统内部各模块的服务和算法．最后以继承建模的方式逐步给出该算法的自动机模型，并用形式化的方法验证其正确性．     

赋权型自动机的不同模型研究

自动机理论是理论计算机科学的基础理论之一,在很多领域自动机有着广泛的应用,有穷状态自动机是正则语言的识别机器,通常分为确定型与非确定型两种模型,其识别语言的能力是等价的。赋权自动机是另一类重要的自动机模型,自动机的每条转移规则和状态可以赋以某一代数结构上的某一数值,从而可以计算输入字符串的权值。任何有穷状态自动机都可以视为一特殊赋权自动机,因此赋权自动机功能更强大,应用更为广泛。