Semi-tensor product approach to controllability and stabilizability of finite automata

Using semi-tensor product of matrices, the controllability and stabilizability of finite automata are investigated. By expressing the states, inputs, and outputs in vector forms, the transition and output functions are represented in matrix forms.Based on this algebraic description, a necessary and sufficient condition is proposed for checking whether a state is controllable to another one. By this condition, an algorithm is established to find all the control sequences of an arbitrary length. Moreover, the stabilizability of finite automata is considered, and a necessary and sufficient condition is presented to examine whether some states can be stabilized. Finally, the study of illustrative examples verifies the correctness of the presented results/algorithms.

Minimization of Fuzzy Finite Generalized Automata

Some concepts in Fuzzy Generalized Automata （FGA） are established. Then an important new algorithm which would calculate the minimal FGA is given. The new algorithm is composed of two parts： the first is called E-reduction which contracts equivalent states, and the second is called RE-reduction which removes retrievable states. Finally an example is given to illuminate the algorithm of minimization.

An Evolution Strategy for the Induction of Fuzzy Finite-State Automata

This paper presents an evolution strategy to induce fuzzy finite-state automata from examples of fuzzy languages. The coding, fitness function of a generated automaton and corresponding mutation operators are given respectively. The application example given at last shows the effectiveness of the proposed evolution strategy for automata induction.

The Equivalent Conversion between Regular Grammar and Finite Automata

The equivalence exists between regular grammar and finite automata in accepting languages. Some complicated conversion algorithms have also been in existence. The simplified forms of the algorithms and their proofs are given. And the construction algorithm 5 of the equivalent conversion from finite automata to left linear grammar is presented as well as its correctness proof. Additionally, a relevant example is expounded.

1-Way Multihead Quantum Finite State Automata

1-way multihead quantum finite state automata (1QFA(k)) can be thought of modified version of 1-way quantum finite state automata (1QFA) and k-letter quantum finite state automata (k-letter QFA) respectively. It has been shown by Moore and Crutchfield as well as Konadacs and Watrous that 1QFA can’t accept all regular language. In this paper, we show different language recognizing capabilities of our model 1-way multihead QFAs. New results presented in this paper are the following ones: 1) We show that newly introduced 1-way 2-head quantum finite state automaton (1QFA(2)) structure can accept all unary regular languages. 2) A language which can’t be accepted by 1-way deterministic 2-head finite state automaton (1DFA((2)) can be accepted by 1QFA(2) with bounded error. 3) 1QFA(2) is more powerful than 1-way reversible 2-head finite state automaton (1RMFA(2)) with respect to recognition of language.

Brain as an Emergent Finite Automaton: A Theory and Three Theorems

This paper models a biological brain—excluding motivation (e.g., emotions)—as a Finite Automaton in Developmental Network (FA-in-DN), but such an FA emerges incrementally in DN. In artificial intelligence (AI), there are two major schools: symbolic and connectionist. Weng 2011 [1] proposed three major properties of the Developmental Network (DN) which bridged the two schools: 1) From any complex FA that demonstrates human knowledge through its sequence of the symbolic inputs-outputs, a Developmental Program (DP) incrementally develops an emergent FA itself inside through naturally emerging image patterns of the symbolic inputs-outputs of the FA. The DN learning from the FA is incremental, immediate and error-free;2) After learning the FA, if the DN freezes its learning but runs, it generalizes optimally for infinitely many inputs and actions based on the neuron’s inner-product distance, state equivalence, and the principle of maximum likelihood;3) After learning the FA, if the DN continues to learn and run, it “thinks” optimally in the sense of maximum likelihood conditioned on its limited computational resource and its limited past experience. This paper gives an overview of the FA-in-DN brain theory and presents the three major theorems and their proofs.

Transitivity and Chaoticity in 1-D Cellular Automata

Recent progress in symbolic dynamics of cellular automata (CA) shows that many CA exhibit rich and complicated Bernoulli-shift properties, such as positive topological entropy, topological transitivity and even mixing. Noticeably, some CA are only transitive, but not mixing on their subsystems. Yet, for one-dimensional CA, this paper proves that not only the shift transitivity guarantees the CA transitivity but also the CA with transitive non-trivial Bernoulli subshift of finite type have dense periodic points. It is concluded that, for one-dimensional CA, the transitivity implies chaos in the sense of Devaney on the non-trivial Bernoulli subshift of finite types.

Achieving of Fuzzy Automata for Processing Fuzzy Logic

At present, there has been an increasing interest in neuron-fuzzy systems, the combinations of artificial neural networks with fuzzy logic. In this paper, a definition of fuzzy finite state automata （FFA） is introduced and fuzzy knowledge equivalence representations between neural networks, fuzzy systems and models of automata are discussed. Once the network has been trained, we develop a method to extract a representation of the FFA encoded in the recurrent neural network that recognizes the training rules.

面向高铁信号系统工程测试的测试建模方法

高铁信号系统工程测试关注系统中各设备间的复杂行为关系和状态同步,工程测试的测试建模方法缺少复杂行为交互和同步机制,针对此问题,提出基于扩展有限状态机的高铁信号系统工程测试建模方法和测试用例生成方法.首先,分析高铁信号系统工程测试的特点,提出复杂事件交互和状态同步的测试建模需求,以有限状态机理论为基础,扩展出状态事件和层次性,满足信号系统工程测试中复杂行为关系和状态同步的建模需求,采用Z规格说明语言给出扩展有限状态机的形式化定义,定义扩展有限状态机的格局和同步机制;然后,提出将扩展有限状态机转化为时间自动机的算法,利用时间自动机的测试用例生成算法自动生成高铁信号系统工程测试的测试用例;最后,以高铁信号系统工程测试中的进路控制为例,建立扩展有限状态机模型并生成测试用例,通过变异分析对生成的测试用例进行评估.结果表明:测试用例在检测状态变异和事件表达式变异时的变异评分均为1,具有良好的覆盖度,能够满足高铁信号系统工程测试的需求.

Matrix expression and reachability analysis of finite automata

In this paper, we propose a matrix-based approach for finite automata and then study the reachability conditions. Both the deterministic and nondeterministic automata are expressed in matrix forms, and the necessary and sufficient conditions on reachability are given using semitensor product of matrices. Our results show that the matrix expression provides an effective computational way for the reachability analysis of finite automata.

Input-Trees of Finite Automata and Application to Cryptanalysis

In this papert weights of output set and of input set for finiteautomata are discussed. For a weakly invertible finite automaton, we proye thatfor states with minimal output weight, the distribution of input sets is uniform.Then for a kind of compound finite automata, we give weights of output set and ofinput set explicitly, and a characterization of their input-trees. For finite automatonpublic key cryptosystems, of which automata in public keys belong to such a kind ofcompound finite automata, we evaluate search amounts of exhaust search algorithmsin average case and in worse case for both encryption and signature, and successfulprobabilities of stochastic search algorithms for both encryption and signature. Inaddition, a result on mutual invertibility of finite automata is also given.

Semi-tensor product of matrices approach to reachability of finite automata with application to language recognition

This paper investigates the transition function and the reachability conditions of finite automata by using a semitensor product of matrices, which is a new powerful matrix analysis tool. The states and input symbols are first expressed in vector forms, then the transition function is described in an algebraic form. Using this algebraic representation, a sufficient and necessary condition of the reachability of any two states is proposed, based on which an algorithm is developed for discovering all the paths from one state to another. Furthermore, a mechanism is established to recognize the language acceptable by a finite automaton. Finally, illustrative examples show that the results/algorithms presented in this paper are suitable for both deterministic finite automata （DFA） and nondeterministic finite automata （NFA）.

6061铝合金半连铸圆坯组织瞬态数值模拟研究

本文建立了6061铝合金半连铸过程传热模型和元胞自动机-有限元(CAFE)耦合模型,采用边界跟踪法模拟了瞬态条件下不同铸造工艺对凝固组织演变的影响。经试验验证,该模型可模拟6061铝合金半连铸的凝固组织。用其预测不同铸造温度、速度和传热系数下的凝固组织。结果表明:铸造温度升高,等轴区宽度从219.1 mm降至187.4 mm,柱状晶和等轴晶均粗化;铸造速度增加,液穴深度增大,等轴晶区的宽度由222.1 mm降至202.4 mm,柱状晶尺寸增大,等轴晶细化;传热系数增大,铸坯边部温度梯度增大,柱状晶粗化,但中心熔体冷却速度增大,对等轴晶有一定细化效果。用半连铸方法生产6061铝合金铸锭,适当降低铸造温度,增大铸造速度和冷却水量有利于形成细小的凝固组织。

Constructing Finite Automata with Invertibility bytransformation Method

Ra, Rb transformations were successfully applied to establish invertibility theory for linear and quasi-linear finite automata over finite fields. In aprevious paper, the authors generalized R., Rb transformations to deal with nonlinear memory finite automata, and gave sufficient conditions for weak inverse andfor weakly invertible memory finite automata and inversion processes concerned;methods by transformation to generate a kind of nonlinear memory finite automatasatisfying one of these sufficient conditions were also given. This paper extends theconcepts, methods and results to general finite automata, in which states consist offinite input history, finite output history and finite 'inner state' history.

Algebraic criteria for finite automata understanding of regular language

1 Introduction and main contributions Finite automata are dynamical systems with discrete inputs and outputs, which belong to the domain of logical systems and have a wide range of applications. In engineering, due to the excellent hardware qualities of simple structure, low power consumption and low electromagnetic noise, etc., finite automata are used in avionics and nuclear engineering, where the environment is bad and require strict safety. In science, finite automata serve as one of the main molding tools for discrete event dynamic systems (DEDS)(others are Petri nets, Markov chains and queuing networks, etc.). Studying DEDS is one of the major ways to study the cyber physical systems (CPS) which is the core content of Industry 4.0.

On Some Properties of Graph of Prefix Code

We investigate decomposition of codes and finite languages. A prime decomposition is a decomposition of a code or languages into a concatenation of nontrivial prime codes or languages. A code is prime if it cannot be decomposed into at least two nontrivial codes as the same for the languages. In the paper, a linear time algorithm is designed, which finds the prime decomposition. If codes or finite languages are presented as given by its minimal deterministic automaton, then from the point of view of abstract algebra and graph theory, this automaton has special properties. The study was conducted using system for computational Discrete Algebra GAP. .

A necessary condition on invertibility of finite automata

This paper gives a necessary condition for a kind of weakly invertible, invertible, weak inverse or inverse finite automata by linear RaRb transformation sequence. For such finite automata the existence of terminating RaRb transformation sequence is also established.

Increasing Ranks of Linear Finite Automata and Complexity of FA Public Key Cryptosystem

The encryption algorithm of finite automata (FA) public key cryptosystem is implemented by a weakly invertible finite automata (WIFA) which is composed of a nonlinear WIFA with delay 0 and a linear WIFA with delay τ. In this paper, we proved that such an automaton bears the same properties as the linear WIFA and the increasing ranks of the latter are key factors to affecting the former. A probabilistic algorithm is given to realize a ciphertext attack, and its complexity is analysed through the increasing ranks of the linear WIFA. The size of the parameters for safe linear WIFA is estimated.

基于电抗器基础设施中态势感知的应用

关键基础设施是相互依存的,很容易出现级联故障,为了有效应对全国范围内的事件,需要创建一个共同操作图,以维持态势感知。为此提出一个适用于全国规模态势感知应用的关键基础设施模型和分析方法,该模型使用有向图结合有限状态转换器呈现关键基础设施系统的依赖关系和运行状态,开发一种利用图中心性度量的分析方法,用于量化破坏的系统特定和基础设施范围影响,同时还创建一种基于熵的分析方法,用于估计当前数据不可用情况下基础设施系统的运行状态。利用所提出的方法实际案例进行建模,并使用风暴期间观察到的系统故障数据集进行评估。结果表明,所提出的建模和分析方法适用于实时态势感知应用。

Compatible-invariant subset analysis of deterministic finite automata via semi-tensor product of matrices approach

The compatible-invariant subset of deterministic finite automata（ DFA） is investigated to solve the problem of subset stabilization under the frameworks of semi-tensor product（ STP） of matrices. The concepts of compatibleinvariant subset and largest compatible-invariant subset are introduced inductively for Moore-type DFA,and a necessary condition for the existence of largest compatible-invariant subset is given. Meanwhile,by using the STP of matrices,a compatible feasible event matrix is defined with respect to the largest compatible-invariant subset.Based on the concept of compatible feasible event matrix,an algorithm to calculate the largest compatible-invariant subset contained in a given subset is proposed. Finally,an illustrative example is given to validate the results.