有限布尔代数上的线性自动机

自动机理论是计算机科学理论的重要组成部分。论文研究了布尔代数上的线性自动机,证明了任意一个线性有限自动机是函数布尔代数上的一个内动机。定出了有限布尔代数上的一类可逆线性内动机,给出并证明了有限布尔代数上内动机图型为下向森林的充分必要条件,给出了树型内动机中每一层节点数的计算公式,进而证明了有限布尔代数上的非可逆内动机图型为恰等叉支下向树的充分必要条件。     

有限布尔环上的自动机

自动机理论作为计算机科学的基础理论，其研究直接地推动计算机科学技术的发展．本文研究了有限布尔环上的自动机，首次定出了有限布尔环上的一类下向树和一类有向圈，并证明了布尔环上的一类可逆内动机的图型与其仿射内动机的图型相同．     

布尔代数上的自动机

给出了内动机下向树中的每一层节点数的计算公式,定出了自动机的图形是圈-树形的充分必要条件。该方法在很多领域有着广泛的应用。     

环上线性有限自动机的可逆性的一些结果

本文证明了有单位元的有限交换环R上任何延迟t步(弱)可逆线性有限自动机皆有延迟t步线性(弱)逆的充分必要条件是环R满足条件: x(Ax=0→bx=0)→y(b=yA)我们还证明了对任何有单有限交换环R,R上输入、输出维数相同的延迟t步(弱)可逆线性有限自动机具有延迟t步线性(弱)逆.     

概率有限自动机的积和分解

给出几种概率有限自动机的积,讨论了他们之间的相互关系,并在文献[1]的基础上利用这些积给出匀概率有限自动机的分解,证明了一个匀概率有限自动机可以分解为一个随机编码源、一个伯努利过程和一些确定有限自动机的串联积。     

环境自动机的测试等价类

一、引言在自动机理论中常常对于标准的Moore自动机增加某些装置构成用于各种不同用途的自动机,它们常用于语言的识别器、算法设计和分析、人工智能、机器学习、机器人的环境等等。R.L.Rivest和R.E.Schapire在文[1]中,引用了An-gluin提出的学习自动机的模型,建立了测试等价类的概念,应用这个概念,成功地描述了机器人的环境和复杂环境下的学习问题。     

基于广义有限自动机的图像压缩方法

提出一种用确定性的广义有限自动机(GFA)对灰度图像进行压缩编码的方法.对一幅输入的数字化灰度图像,检测其中的自相似性,该图像可以被表示成一个广义有限自动机.解码算法可以非常高效的由确定的广义有限自动机复原图像,且结果图像没有很明显的方块效应.这种方法与传统的有限自动机方法相比具有状态数较少、压缩比高、压缩效果较好的优点.     

有限自动机代数及其算法

本文提出有限自动机代数及其算法,它对于用有限自动机识别句子是有意义的。     

有限（状态）自动机与泛系方法论

揭示有限自动机的核心机理，探讨这一通用模型中内部状态转移、外部输出所具有的特性，将泛系方法论的一些概括性原理和思想用在了有限自动机的研究之中。     

基于有限状态自动机的服务组合模型

分析了目前服务计算的研究现状和存在的问题，在D Berardi和A Wombacher的基础上提出了一种带条件的有限状态自动机模型cFSA（Finite State Automata with condition），并给出了基于cFSA的服务理论模型．在该服务理论模型的基础上提出了一种基于有限状态自动机的服务组合形式化模型，并给出了该模型的代数性质和实现方法．     

Automata Over Abstract Finite Quasigroups

This paper analyzes the structure of families of automata without output that are defined by recurrence relations on abstract finite quasigroups. The expediency of their use to design iterated hash functions with sufficiently high security is justified. It is shown how some families of reversible Mealy and Moore automata can be constructed based on such families of automata without output. The expediency of using the proposed families of Mealy and Moore automata as the basis to construct mathematical models for stream ciphers is substantiated.     

Automata over Finite T-Quasigroups

This paper investigates families of automata without outputs and also families of reversible Mealy and Moore automata specified by recurrence relations over finite T-quasigroups. Based on the decomposition of an Abelian group into the direct sum of primary cyclic groups, a unified approach is proposed to the hardware and software synthesis of such automata. Estimates are found for the time and space complexities of computations executed by these automata during one clock cycle.     

Multihead Two-Way Probabilistic Finite Automata

We present properties of multihead two-way probabilistic finite automata that parallel those of their deterministic and nondeterministic counterparts. We define multihead probabilistic finite automata withlogspace constructible transition probabilities, and we describe a technique to simulate these automata by standard logspace probabilistic Turing machines. Next, we represent logspace probabilistic complexity classes as proper hierarchies based on corresponding multihead two-way probabilistic finite automata, and we show their (deterministic logspace) reducibility to the second levels of these hierarchies. We obtain a simple formula for the maximum inherent bandwidth of the configuration transition matrices associated with thek-head probabilistic finite automata processing a length-n input string. (The inherent bandwidth of the configuration transition matrices associated with an automaton processing a length-n input string is the smallest bandwidth we can get by changing the enumeration order of the automaton’s configurations.) Partially based on this relation, we find an apparently easier logspace complete problem forPL (the class of languages recognized by logspace unbounded-error probabilistic Turing machines), and we discuss possibilities for a space-efficient deterministic simulation of probabilistic automata. This research was supported by the National Science Foundation under Grant No. CDA 8822724 while the author was at the University of Rochester. An extended abstract of this paper appeared in Proceedings, Second Latin American Symposium, LATIN ’95: Theoretical Informatics, Valparaiso, Chile, April 1995.     

Learning Fallible Deterministic Finite Automata

We consider the problem of learning from a fallible expert that answers all queries about a concept, but often gives incorrect answers. The expert can also be thought of as a truth table describing the concept which has been partially corrupted. In order to learn the underlying concept with arbitrarily high precision, we would like to use its structure in order to correct most of the incorrect answers. We assume that the expert's errors are uniformly and independently distributed, occur with any fixed probability strictly smaller than 1/2, and are persistent. In particular, we present a polynomial time algorithm using membership queries for correcting and learning fallible Deterministic Finite Automata under the uniform distribution.     

弱可逆有限自动机的分解

有限自动机公开钥密码体制的提出进一步激励了有限自动机可逆性的研究．在有限自动机公开钥密码体制中首次提出了自动机化合的概念．易知,两个弱可逆有限自动机的化合仍然是一个弱可逆有限自动机并且它的延迟步数不大于前两个有限自动机延迟步数之和．然而,另一方面,如何将一个弱可逆有限自动机分解为两个弱可逆有限自动机的化合却是一个非常困难的问题．该文主要考虑了一类n元严格延迟τ步弱可逆有限自动机M的延迟步数的分解问题．给出了一类特殊的n元弱可逆有限自动机分解的条件和结果．首先证明了如果对M中的每个状态s有T（s,τ）枝等,则M可分解为τ个延迟1步弱可逆有限自动机的化合．然后证明了M可分解为一个τ—m步弱可逆有限自动机和m阶延迟元的充要条件是对M中的每个状态s有T（s,m）枝等．     

Mizumoto格值有限自动机及其最小化

提出取值为格半群的Mizumoto格值有限自动机的概念,得到基于模糊字符串的Mizumoto格值有限自动机的扩张模型,并详细讨论了其性质。同时建立了扩张Mizumoto格值有限自动机与标准扩张Mizumoto格值有限自动机的等价性,在此基础上给出了其最小化算法。     

Checking Finite Traces Using Alternating Automata

Alternating automata have been commonly used as a basis for static verification of reactive systems. In this paper we show how alternating automata can be used in runtime verification. We present three algorithms to check at runtime whether a reactive program satisfies a temporal specification, expressed by a linear-time temporal logic formula. The three methods start from the same alternating automaton but traverse the automaton in different ways: depth-first, breadth-first, and backwards, respectively. We then show how an extension of these algorithms, that collects statistical data while verifying the execution trace, can be used for a more detailed analysis of the runtime behavior. All three methods have been implemented and experimental results are presented.