描述逻辑μALCQO 的语义及推理

循环术语集是描述逻辑长期以来的研究难点,其最基本的问题即语义及推理问题没有得到合理的解决.基于混合分级μ-演算将不动点构造算子引入到含有枚举构造算子的描述逻辑ALCQO 中,提出了一种允许包含循环术语集的描述逻辑μALCQO.给出了μALCQO 的语法、语义和不动点构造算子的性质,证明了μALCQO 的可满足性推理等价于混合分级μ-演算的可满足性推理.基于混合分级μ-演算可满足性推理算法,并利用完全强化自动机给出了μALCQO的可满足性推理算法,以及给出了推理算法正确性证明和复杂性定理.μALCQO为进一步给出同时含有不动点构造算子和枚举构造算子的表达能力强的描述逻辑推理算法提供了理论基础.     

有关时间自动机重置的若干问题的计算复杂性

自动机的重置序列也称为同步序列,具有以下特性：有限自动机通过运行重置序列w,可从任意一个未知的或无法观测到的状态q₀到达某个特定状态q_w.这仅依赖于w,而与开始运行w时的状态q₀无关.这一特性可用于部分可观察的复杂系统的自动恢复,而无需重启,甚至有时不能重启.基于此,重置问题自出现以来便得到关注和持续研究.最近几年,它被扩展到可以描述诸如分布式、嵌入式实时系统等复杂系统的无限状态模型上,比如时间自动机和寄存器自动机等.以时间自动机的重置问题的计算复杂性为研究对象,发现重置问题与可达性问题有着紧密的联系.主要贡献是：（1）利用时间自动机可达性问题的最新成果,完善完全的确定的时间自动机重置问题的计算复杂性结论;（2）对部分规约的确定的时间自动机,研究得出,即使在输入字母表大小减至2的情况下,其复杂性仍是PSPACE-完全的;特别地,在单时钟情况下是NLOGSPACE-完全的;（3）对完全的非确定的时间自动机,研究得出其D_i-可重置问题（i=1,2,3）是不可判定的,其重置问题与非确定的寄存器自动机重置问题在指数时间可以相互归约,通过证明指数时间归约相对高复杂性类具有封闭性,利用非确定的寄存器自动机的结论得出单时钟的时间自动机的重置问题是Ackermann-完全的、限界的重置问题是NEXPTIME-完全的.这些复杂性结论,说明关于时间自动机的重置问题大都是难解的,一方面,为时间系统的可重置性的检测和求解奠定坚实的理论基础,另一方面,为以后寻找具有高效算法的特殊结构的时间系统（即具有高效算法的问题子类）给予理论指导.     

关于二元延迟3步前馈逆有限自动机的结构

前馈逆有限自动机的结构是有限自动机可逆性理论中的基本问题.对延迟步数≥3的前馈逆结构的刻划,则是一个长期的未解决问题.研究了二元延迟3步前馈逆有限自动机的结构.对于自治有限自动机M_a的状态图为圈的二元延迟3步弱可逆半输入存储有限自动机C(M_af ),给出了其长3极小输出权分别为1,2,8三种情形下结构的一种刻画.由于C(M_af )延迟3步弱可逆当且仅当它是延迟3步弱逆,因此,得到了二元延迟3步前馈逆有限自动机结构的一种部分刻画.     

算子Fuzzy逻辑中的λ—蕴涵和λ—强蕴涵

在本文中,我们引进了算子模糊逻辑中的λ-蕴涵和λ-强蕴涵的概念,λ-逻辑结果和λ-弱逻辑结果的概念。证明了两子句的的λ-归结式是这两个子句的λ-逻辑结果,从而完成了λ-归结的完备性定理的证明。     

描述逻辑μALCIO的语义及推理

循环术语集是描述逻辑长期以来的研究难点,它的最基本的问题即语义及推理问题没有得到合理的解决.分析了描述逻辑循环术语集的研究现状和存在的问题,基于混合μ-演算将不动点构造算子引入到含有枚举构造算子的描述逻辑ALCIO中,提出了一种允许包含循环术语集的描述逻辑μALCIO.给出了μALCIO的语法和语义,证明了μALCIO的可满足性推理等价于混合μ-演算的可满足性推理,并利用树自动机理论给出了μALCIO的可满足性推理算法以及给出了推理算法正确性证明和复杂性定理.     

关于有ω-穷自动机的两个新的接受条件*

至今被公开的ω-有穷自动机的接受条件有6个即C₁—C₆，寻找新的接受条件和研究ω-有穷自动机关于新接受条件接受ω-语言的能力是ω-有穷自动机理论中的一个重要课题．本文定义了ω-有穷自动机的两个新的接受条件Z₁和Z₂，并且研究了：(1)ω-U—NFA关于Z_i(i=1,2)接受 ω-语言的能力，得到了 N     

一种时间复杂度最优的精确串匹配算法

现有的串匹配算法通常以模式长度作为滑动窗口大小.在窗口移动后,往往会丢弃掉一些已扫描正文的信息.提出了LDM(linear DAWG matching)串匹配算法,该算法将正文分为[n/m]个相互重叠、大小为2m-1的扫描窗口.在每个扫描窗口内,算法批量地尝试m个可能位置,首先使用反向后缀自动机从窗口中间位置向前扫描模式前缀;若成功,则再使用正向有限状态自动机从中间位置向后扫描剩余的模式后缀.分析证明,LDM算法的最差、最好、平均时间复杂度分别达到了理论最好结果:O(n),O(n/m),O(n(1og_σm)/m).实际性能测试也验证了平均时间复杂度最优这一理论结果.而且,对于在较大字母表下查找短模式的情况,LDM算法速度在被测试算法中最快.总之,LDM算法不但适合进行离线模式匹配,而且还特别适合需要进行在线高速匹配的应用.     

一种基于彩色编码技术的基序发现算法

从DNA序列中发现基序是生物计算中的一个重要问题,序列条数K=20包含基序用例的序列条数k=16的(l,d)-(K-k)问题(记作(l,d)-(20-16)问题)是目前生物学家十分关注的基序发现问题.针对该问题提出了一种基于彩色编码技术的SDA(sample-driven algorithm)搜索算法--彩色编码基序搜索算法(color coding motif finding algorithm,简称CCMF算法).它利用彩色编码技术将该问题转化为(l,d)-(16-16)问题,再采用分治算法和分支定界法来求解.在解决将(l,d)-(20-16)问题转化为(l,d)-(16-16)问题时,CCMF算法利用彩色编码技术将4 845个组合降低到403个着色,这将极大地提高算法的整体运行效率.使用模拟数据和生物数据进行测试的结果表明,CCMF算法能够快速发现所有(l,d)-(20-16)问题的基序模型和基序用例,具有优于其他算法的综合性能评价,能够用于真实的基序发现问题.同时,通过修改着色方案,CCMF算法可以用于求解一般的(l,d)-(K-k)问题,其中,k＜K.     

APTL公式的可满足性检查工具

交替投影时序逻辑（Alternating Projection Temporal Logic,简称APTL）公式简单易懂,表达能力强;不仅可以描述经典时序逻辑LTL可以描述的性质,而且可以描述与区间相关的顺序和循环性质以及开放系统和多智能体系统中与博弈相关的性质.在验证系统是否满足所给的APTL公式所描述的性质之前需要检查公式的可满足性.本文根据检查APTL公式的可满足性的方法^[1],开发实现了工具APTL2BCG.具体细节如下：首先,利用公式P的范式构造P的标记范式图（Labeled Normal Form Graph,简称LNFG）;然后,将LNFG转化为广义的基于并发博弈结构的交替Büchi自动机（Generalized alternating Büchi automaton over Concurrent Game structure,简称GBCG）;最后,将GBCG转化为基于并发博弈结构的交替Büchi自动机（alternating Büchi automaton over Concurrent Game structure,简称BCG）并且化为最简形式并检查公式P的可满足性.     

基于Unsharp量子逻辑的自动机和文法理论

初步建立了具有某种分配律的扩展格序效应代数和格序QMV代数这两种unsharp量子结构上的自动机与文法理论的基本框架。引入了ε-值正则文法的概念,证明了任意ε-值自动机识别的语言等价于某种ε-值正则文法所生成的语言;反之,任意[ε]-值正则文法所生成的语言等价于某种ε-值自动机识别的语言。讨论了ε-值正则语言在和、连接及反转运算下的封闭性质。     

Automata theory based on quantum logic: some characterizations

Automata theory based on quantum logic (abbr. l-valued automata theory) may be viewed as a logical approach of quantum computation. In this paper, we characterize some fundamental properties of l-valued automata theory, and discover that some properties of the truth-value lattices of the underlying logic are equivalent to certain properties of automata. More specifically (i) the transition relations of l-valued automata are extended to describe the transitions enabled by strings of input symbols, and particularly, these extensions depend on the distributivity of the truth-value lattices (Proposition 3.1); (ii) some properties of the l-valued successor and source operators and l-valued subautomata are demonstrated to be equivalent to a property of the truth-value lattices which is exactly equivalent to the distributive law (Proposition 4.3 and Corollary 4.4). This is a new characterization of Boolean algebras in the framework of l-valued automata theory; (iii) we verify that the intersection of two l-valued subautomata is still an l-valued subautomaton if and only if the multiplication (&) is distributive over the union in the truth-value lattices (Proposition 4.5), which is strictly weaker than the usual distributivity; (iv) we show that some topological characterizations in terms of the l-valued successor and source operators also rely on the distributivity of truth-value lattices (Theorem 5.6). Finally, we address some related topics for further study.     

Automata theory based on complete residuated lattice-valued logic

This paper establishes a fundamental framework of automata theory based on complete residuated lattice-valued logic. First it deals with how to extend the transition relation of states and par-ticularly presents a characterization of residuated lattice by fuzzy automata (called (?) valued automata). After that fuzzy subautomata (called (?) valued subautomata), successor and source operators are pro-posed and their basic properties as well as the equivalent relation among them are discussed, from which it follows that the two fuzzy operators are exactly fuzzy closure operators. Finally an L bifuzzy topological characterization of Q valued automata is presented, so a more generalized fuzzy automata theory is built.     

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.     

格值交替树自动机

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

The Representation of Numbers in Quantum Mechanics

Abstract. Earlier work on modular arithmetic of k-ary representations of length L of the natural numbers in quantum mechanics is extended here to k-ary representations of all natural numbers, and to integers and rational numbers. Since the length L is indeterminate, representations of states and operators using creation and annihilation operators for bosons and fermions are defined. Emphasis is on definitions and properties of operators corresponding to the basic operations whose properties are given by the axioms for each type of number. The importance of the requirement of efficient implementability for physical models of the axioms is emphasized. Based on this, successor operations for each value of j corresponding to +k ^j-1 are defined. It follows from the efficient implementability of these successors, which is the case for all computers, that implementation of the addition and multiplication operators, which are defined in terms of polynomially many iterations of the successors, should be efficient. This is not the case for definitions based on just the successor for j=1 . This is the only successor defined in the usual axioms of arithmetic.     

Fuzzy grammar theory based on lattices

In this paper, on the basis of breadth-first and depth-first ways, we establish a fundamental framework of fuzzy grammars based on lattices, which provides a necessary tool for the analysis of fuzzy automata. The relationship among finite automata with membership values in lattices (l-VFAs), lattice-valued regular grammars (l-RGs) and lattice-valued deterministic regular grammars (l-DRGs) is investigated. It is demonstrated that, based on each semantic way, l-VFAs and l-RGs are equivalent in the sense that they accept or generate the same classes of fuzzy languages. Furthermore, it is proved that l-VFAs,?l-valued deterministic finite automata, l-RGs and l-DRGs are equivalent based on depth-first way. For any l-RG,?the language based on breadth-first way coincides with the language based on depth-first way if and only if the truth-valued domain l is a distributive lattice.     

Notes on automata theory based on quantum logic

The main results are as follows: (1) it deals with a number of basic operations (concatenation, Kleene closure, homomorphism, complement); (2) due to a condition imposed on the implication operator for discussing some basic issues in orthomodular lattice-valued automata, this condition is investigated in detail, and it is discovered that all the relatively reasonable five implication operators in quantum logic do not satisfy this condition, and that one of the five implications satisfies such a condition iff the truth-value lattice is indeed a Boolean algebra; (3) it deals further with orthomodular lattice-valued successor and source operators; (4) an example is provided, implying that some negative results obtained in the literature may still hold in some typical orthomodular lattice-valued automata.     

The relationships among several types of fuzzy automata

We discuss the relationships among several types of fuzzy automata in which all fuzzy sets are defined by membership functions whose codomains are a lattice-ordered monoid L. These automata include nondeterministic L-valued finite automata with Λ-move, nondeterministic L-valued finite automata, deterministic L-valued finite automata, and L-valued finite-state automata. We consider all that come with fuzzy initial states and fuzzy final states or with crisp initial states or crisp final states. Some comparative results concerning the power of fuzzy automata used in the existing literature to recognize fuzzy languages are given systematically.