n值乘积逻辑系统中的随机化研究

利用赋值集的随机化方法,在n值乘积逻辑中提出了公式的随机真度,证明了所有公式的随机真度之集在[0,1]中没有孤立点;给出了两公式间的D_πn-相似度与伪距离的概念,并建立了D_πn逻辑度量空间,证明了此空间没有孤立点。     

n值命题逻辑中公式的随机真度

给出了Lukasiewicz n值命题逻辑中公式的随机真度的概念,研究了其性质,利用随机真度定义了公式间的随机相似度,进而导出全体公式集上的一种伪距离。     

逻辑系统Hα中广义语义MP规则证明的改进

将修正的Kleene逻辑系统中语义MP规则推广后应用于H_α逻辑系统中,讨论了H_α逻辑系统中广义重言式理论的语义（[α]-MP）规则,语义（[α⁺]-MP）规则,使得对H_α系统中的广义语义MP规则有了更进一步的认识。另外,逻辑系统W中的广义语义MP规则也成为一个特例。     

Znm上的l-广义正形置换

给出了Zⁿ_m上l-广义正形置换的概念,讨论了l-广义正形置换的函数性质。对Zⁿ_m上l-广义正形置换的一阶广义Chrestenson谱特征进行了分析,并基于谱特征给出了一种Zⁿ_m上的l-广义正形置换的构造方法。     

逻辑系统Gn中理论的真度概念及其应用

首次在命题逻辑系统中引入理论的真度概念,使得真度的概念由公式的真度推广为公式集的真度,从而简化了发散度的概念;在逻辑系统G_n中讨论了理论Γ1、Γ2和Γ1∪Γ2的真度、相容度和发散度之间的关系。     

最优无向双环网络G（N；±1，±s）的构造

创造性地将直角坐标系引入无向双环网络的研究,通过直角坐标系,系统研究无向双环网络G（N;±1,±s）的仿真图形,提出最优无向双环网络BestG（N;±1,±s）（直径、平均直径均达到下界）的构造方法并研究步长s和其直径之间的关系。与传统L型瓦方法在无向双环网络研究中相比,该方法克服其不足,大大提升了无向双环网络的研究水平,相关研究在国内外文献中尚未见到。     

基于格值一阶逻辑LF（X）的自动推理算法

基于谓词逻辑的归结推理方法是目前理论上较为成熟、可以在计算机上实现的推理方法之一。针对格值一阶逻辑LF(X)中归结自动推理问题,以格值一阶逻辑LF(X)的α-归结原理为理论基础,通过对例子进行分析,提出了LF(X)中简单广义子句集的归结自动推理算法,并证明了该算法的可靠性和完备性。     

基于蕴涵算子族Lλ0λG的模糊推理三I约束算法

提出了基于蕴涵算子族Lλ0λG的模糊推理的思想,这将有助于提高推理结果的可靠性。针对蕴涵算子族Lλ0λG给出了模糊推理的FMP模型及FMT模型的三I约束算法。     

基于蕴涵算子族Lλ0λG的反向三I支持算法

提出了基于蕴涵算子族Lλ0λG的模糊推理的思想,这将有助于提高推理结果的可靠性。针对蕴涵算子族Lλ0λG给出了模糊推理的FMP模型及FMT模型的反向三I支持算法。     

基于蕴涵算子族Lλ0λG的反向α-三I支持算法

提出了基于蕴涵算子族Lλ0λG的模糊推理的思想,这将有助于提高推理结果的可靠性。针对蕴涵算子族Lλ0λG给出了模糊推理的FMP模型及FMT模型的反向α-三I支持算法。     

Embedding paths and cycles in 3-ary n-cubes with faulty nodes and links

The k-ary n-cube, denoted by , is one of the most important interconnection networks for parallel computing. In this paper, we consider the problem of embedding cycles and paths into faulty 3-ary n-cubes. Let F be a set of faulty nodes and/or edges, and n?2. We show that when |F|?2n-2, there exists a cycle of any length from 3 to in . We also prove that when |F|?2n-3, there exists a path of any length from 2n-1 to between two arbitrary nodes in . Since the k-ary n-cube is regular of degree 2n, the fault-tolerant degrees 2n-2 and 2n-3 are optimal.     

Embedding paths of variable lengths into hypercubes with conditional link-faults

Faults in a network may take various forms such as hardware failures while a node or a link stops functioning, software errors, or even missing of transmitted packets. In this paper, we study the link-fault-tolerant capability of an n-dimensional hypercube (n-cube for short) with respect to path embedding of variable lengths in the range from the shortest to the longest. Let F be a set consisting of faulty links in a wounded n-cube Q_n, in which every node is still incident to at least two fault-free links. Then we show that Q_n-F has a path of any odd (resp. even) length in the range from the distance to 2ⁿ-1 (resp. 2ⁿ-2) between two arbitrary nodes even if |F|=2n-5. In order to tackle this problem, we also investigate the fault diameter of an n-cube with hybrid node and link faults.     

Embedding a long fault-free cycle in a crossed cube with more faulty nodes

The crossed cube is an important variant of the most popular hypercube network for parallel computing. In this paper, we consider the problem of embedding a long fault-free cycle in a crossed cube with more faulty nodes. We prove that for n?5 and f?2n−7, a fault-free cycle of length at least n²−f−(n−5) can be embedded in an n-dimensional crossed cube with f faulty nodes. Our work extends some previously known results in the sense of the maximum number of faulty nodes tolerable in a crossed cube.     

Efficient unicast in bijective connection networks with the restricted faulty node set

The connectivity is an important criteria to measure the fault-tolerant performance of a graph. However, the connectivity based on the condition of the set of arbitrary faulty nodes is generally lower. In this paper, in order to heighten this measure, we introduce the restricted connectivity into bijective connection networks. First, we prove that the probability that all the neighbors of an arbitrary node becomes faulty in any n-dimensional bijective connection network X_n is very low when n becomes sufficient large. Then, we give a constructive proof that under the condition that each node of an n-dimensional bijective connection network X_n has at least one fault-free neighbor, its restricted connectivity is 2n − 2, about half of the connectivity of X_n. Finally, by our constructive proof, we give an O(n) algorithm to get a reliable path of length at most n + 3⌈log₂∣F∣⌉ + 1 between any two fault-free nodes in an n-dimensional bijective connection network. In particular, since the family of BC networks contains hypercubes, crossed cubes, Möbius cubes, etc., our algorithm is appropriate for these cubes.     

故障Torus网络中的空闲子网搜索方案研究*

为了提高多处理机系统的抗故障能力,对现有的子网搜索算法进行改进,提出了一种新的基于故障节点模式的空闲子网搜索方案。以具有故障节点的二维Torus网络为例,详细阐述了方案的具体内容,并给出了相关的算法。该方案是基于集合操作的,能够显著缩小搜索范围并缩短比较时间。实例证明该方法具有可行性。     

Hamiltonian connectivity of the WK-recursive network with faulty nodes

A graph G is said to be Hamiltonian-connected if there is a Hamiltonian path between every two distinct nodes of G. Let F denote the set of faulty nodes of G. Then, G is |F|-node Hamiltonian-connected if G-F is Hamiltonian-connected. We use K(d,t) to denote a WK-recursive network of level t, each of whose basic modules is a d-node complete graph. Compared with other networks, it is rather difficult to construct a Hamiltonian path between two arbitrary nodes in a faulty WK-recursive network. In this paper, we show that K(d,t) is (d-4)-node Hamiltonian-connected. Since the connectivity of K(d,t) is d-1, the result is optimal in the worst case.     

Embedding of special classes of circulant networks,hypercubes and generalized Petersen graphs

Hypercubes are a very popular model for parallel computation because of their regularity and the relatively small number of interprocessor connections. In this paper, we present an algorithm for embedding special class of circulant networks into their optimal hypercubes with dilation 2 and prove its correctness. Also, we embed special class of circulant networks into special class of generalized Petersen graphs with dilation 2 and vice versa.     

Embedding ofk-ary Complete Trees into Hypercubes with Uniform Load

The main result of this paper is an algorithm for embeddingk-ary complete trees into hypercubes with uniform load and asymptotically optimal dilation. The algorithm is fully scalable—the dimension of the hypercube can be chosen independent of the arity and height of the tree. The embedding enables to emulate optimally both Divide&Conquer computations onk-ary complete trees where only one level of nodes is active at a time and general computations based onk-ary complete trees where all tree nodes are active simultaneously. As a special case, we get an algorithm for embedding thek-ary complete tree of given height into its optimal hypercube with load 1 and asymptotically optimal dilation.     

A modified ant colony system for finding the expected shortest path in networks with variable arc lengths and probabilistic nodes

The problem of finding the expected shortest path in stochastic networks, where the presence of each node is probabilistic and the arc lengths are random variables, have numerous applications, especially in communication networks. The problem being NP-hard we use an ant colony system (ACS) to propose a metaheuristic algorithm for finding the expected shortest path. A new local heuristic is formulated for the proposed algorithm to consider the probabilistic nodes. The arc lengths are randomly generated based on the arc length distribution functions. Examples are worked out to illustrate the applicability of the proposed approach.