DNA计算原理、现状及展望

综述了DNA计算原理和特点,接着介绍了DNA计算的研究现状,指出了目前DNA计算的主要研究方向和DNA计算需要解决问题,最后对DNA计算的发展前景进行了展望.     

程序复杂性度量的一种新方法

通过分析传统的程序复杂性度量方法的不足之处,首先提出了一种基于程序分解机制的路径复杂性度量方法,然后给出了计算路径复杂度的算法,最后给出了实例。新的度量方法指出了一个程序需要的完全测试路径数目。     

The hub number of a graph

A hub set in a graph G is a set U⊆V(G) such that any two vertices outside U are connected by a path whose internal vertices lie in U. We prove that h(G)?hc(G)?γc(G)?h(G)+1, where h(G), hc(G), and γc(G), respectively, are the minimum sizes of a hub set in G, a hub set inducing a connected subgraph, and a connected dominating set. Furthermore, all graphs with γc(G)>hc(G)?4 are obtained by substituting graphs into three consecutive vertices of a cycle; this yields a polynomial-time algorithm to check whether hc(G)=γc(G).     

Complexity analysis of a decentralised graph colouring algorithm

Colouring a graph with its chromatic number of colours is known to be NP-hard. Identifying an algorithm in which decisions are made locally with no information about the graph's global structure is particularly challenging. In this article we analyse the complexity of a decentralised colouring algorithm that has recently been proposed for channel selection in wireless computer networks.     

Expected parallel time and sequential space complexity of graph and digraph problems

This paper determines upper bounds on the expected time complexity for a variety of parallel algorithms for undirected and directed random graph problems. For connectivity, biconnectivity, transitive closure, minimum spanning trees, and all pairs minimum cost paths, we prove the expected time to beO(log logn) for the CRCW PRAM (this parallel RAM machine allows resolution of write conflicts) andO(logn · log logn) for the CREW PRAM (which allows simultaneous reads but not simultaneous writes). We also show that the problem of graph isomorphism has expected parallel timeO(log logn) for the CRCW PRAM andO(logn) for the CREW PRAM. Most of these results follow because of upper bounds on the mean depth of a graph, derived in this paper, for more general graphs than was known before.For undirected connectivity especially, we present a new probabilistic algorithm which runs on a randomized input and has an expected running time ofO(log logn) on the CRCW PRAM, withO(n) expected number of processors only.Our results also improve known upper bounds on the expected space required for sequential graph algorithms. For example, we show that the problems of finding connected components, transitive closure, minimum spanning trees, and minimum cost paths have expected sequential spaceO(logn · log logn) on a deterministic Turing Machine. We use a simulation of the CRCW PRAM to get these expected sequential space bounds.This research was supported by National Science Foundation Grant DCR-85-03251 and Office of Naval Research Contract N00014-80-C-0647.This research was partially supported by the National Science Foundation Grants MCS-83-00630, DCR-8503497, by the Greek Ministry of Research and Technology, and by the ESPRIT Basic Research Actions Project ALCOM.     

Combining self-healing and proofreading in self-assembly

Molecular self-assembly is a promising approach to bottom-up fabrication of complex structures. A major impediment to the practical use of self-assembly to create complex structures is the high rate of error under existing experimental conditions. Recent theoretical work on algorithmic self-assembly has shown that under a realistic model of tile addition and detachment, error correcting tile sets are possible that can recover from the attachment of incorrect tiles during the assembly process. An orthogonal type of error correction was recently considered as well: whether damage to a completed structure can be repaired. It was shown that such self-healing tile sets are possible. However, these tile sets are not robust to the incorporation of incorrect tiles. It remained an open question whether it is possible to create tile sets that can simultaneously resist wholesale removal of tiles and the incorporation of incorrect ones. Here we present a method for converting a tile set producing a pattern on the quarter plane into a tile set that makes the same pattern (at a larger scale) but is able to withstand both of these types of errors.

P systems with local graph productions

P systems (membrane systems) of various types so far mainly have been considered as computing devices working on multisets or strings. In this paper we investigate P systems with local graph productions generating weakly connected directed graphs. At least when equipped with a priority relation on the rules, such P systems can generate any recursively enumerable language of weakly connected directed graphs with only one membrane. Rudolf Freund, Ph.D.: He holds a master and doctor degree in computer science and a master degree in mathematics and physics. Since 1995 he is Associate Professor at the Vienna University of Technology in Austria. His research interests include array and graph grammars, regulated rewriting, infinite words, syntactic pattern recognition, neural networks, and especially models and systems for biological computing. In these fields, he is author or co-author of more than ninety scientific papers. Marion Oswald, Ph.D.: She received her master and doctor degree in computer science from the Vienna University of Technology, Austria, in 2001 and 2003, respectively. Her research interests include but are not limited to artificial life as well as models and systems for biological computing, in which fields she is author or co-author of more than fifteen scientific papers.     

Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard

Let G=(V,E) be an undirected graph and C a subset of vertices. If the sets B_r(v)∩C, vV (respectively, vVC), are all nonempty and different, where B_r(v) denotes the set of all points within distance r from v, we call C an r-identifying code (respectively, an r-locating-dominating code). We prove that, given a graph G and an integer k, the decision problem of the existence of an r-identifying code, or of an r-locating-dominating code, of size at most k in G, is NP-complete for any r.     

A model for assessing the layout structural complexity of manufacturing systems

The layout of a manufacturing facility/system not only shapes its material flow pattern and influence transportation and operation cost, but also affects logistics and parts/machine assignment decisions. The layout of manufacturing systems determines its structural complexity by virtue of its design configuration characteristics. This paper introduces a new model and indices for assessing the structural complexity of manufacturing systems layout in the physical domain. Six complexity indices, based on the physical structural characteristics of the layout, have been introduced and formulated. They are layout density, path, cycle, decision points, redundancy distribution and magnitude indices. An overall Layout Complexity Index (LCI) which combines all indices is developed using a novel method based on radar plots which is insensitive to the order of plotting the individual indices. The use of the developed LCI is demonstrated using six typical types of manufacturing systems layouts and relevant guidelines are presented. The developed model and complexity indices help design system layouts for least complexity and compare layout alternatives that meet the specifications, at early design stages. It supports making trade-off decisions regarding manufacturing systems flexibility and complexity and their associated costs.     

On existence of reporter strands in DNA-based graph structures

Through self-assembly of branched junction molecules many different DNA structures (graphs) can be assembled. We show that every multigraph can be assembled by DNA such that there is a single strand that traces each edge in the graph at least once. This strand corresponds to a boundary component of a two-dimensional orientable surface that has the given graph as a deformation retract. This boundary component traverses every edge at least once, and it defines a circular path in the graph that “preserves the graph structure” and traverses each edge.     

On labeling in graph visualization

When visualizing graphs, it is essential to communicate the meaning of each graph object via text or graphical labels. Automatic placement of labels in a graph is an NP-Hard problem, for which efficient heuristic solutions have been recently developed. In this paper, we describe a general framework for modeling, drawing, editing, and automatic placement of labels respecting user constraints. In addition, we present the interface and the basic engine of the Graph Editor Toolkit - a family of portable graph visualization libraries designed for integration into graphical user interface application programs. This toolkit produces a high quality automated placement of labels in a graph using our framework. A brief survey of automatic label placement algorithms is also presented. Finally we describe extensions to certain existing automatic label placement algorithms, allowing their integration into this visualization tool.     

A dynamical systems approach to weighted graph matching

Graph matching is a fundamental problem that arises frequently in the areas of distributed control, computer vision, and facility allocation. In this paper, we consider the optimal graph matching problem for weighted graphs, which is computationally challenging due the combinatorial nature of the set of permutations. Contrary to optimization-based relaxations to this problem, in this paper we develop a novel relaxation by constructing dynamical systems on the manifold of orthogonal matrices. In particular, since permutation matrices are orthogonal matrices with nonnegative elements, we define two gradient flows in the space of orthogonal matrices. The first minimizes the cost of weighted graph matching over orthogonal matrices, whereas the second minimizes the distance of an orthogonal matrix from the finite set of all permutations. The combination of the two dynamical systems converges to a permutation matrix, which provides a suboptimal solution to the weighted graph matching problem. Finally, our approach is shown to be promising by illustrating it on nontrivial problems.     

A simple graph theoretic characterization of reachability for positive linear systems

In this paper we consider discrete-time linear positive systems, that is systems defined by a pair (A,B) of non-negative matrices. We study the reachability of such systems which in this case amounts to the freedom of steering the state in the positive orthant by using non-negative control sequences. This problem was solved recently [Canonical forms for positive discrete-time linear control systems, Linear Algebra Appl., 310 (2000) 49]. However we derive here necessary and sufficient conditions for reachability in a simpler and more compact form. These conditions are expressed in terms of particular paths in the graph which is naturally associated with the system.     

Lexical systems: graph models of natural language lexicons

We introduce a new type of lexical structure called lexical system, an interoperable model that can feed both monolingual and multilingual language resources. We begin with a formal characterization of lexical systems as simple directed graphs, solely made up of nodes corresponding to lexical entities and links. To illustrate our approach, we present data borrowed from a lexical system that has been generated from the French DiCo database. We later explain how the compilation of the original dictionary-like database into a net-like one has been made possible. Finally, we discuss the potential of the proposed lexical structure for designing multilingual lexical resources.

Complexity and computability of solutions to linear programming systems

Through key examples and constructs, exact and approximate, complexity, computability, and solution of linear programming systems are reexamined in the light of Khachian's new notion of (approximate) solution. Algorithms, basic theorems, and alternate representations are reviewed. It is shown that the Klee-Minty example hasnever been exponential for (exact) adjacent extreme point algorithms and that the Balinski-Gomory (exact) algorithm continues to be polynomial in cases where (approximate) ellipsoidal centered-cutoff algorithms (Levin, Shor, Khachian, Gacs-Lovasz) are exponential. By model approximation, both the Klee-Minty and the new J. Clausen examples are shown to be trivial (explicitly solvable) interval programming problems. A new notion of computable (approximate) solution is proposed together with ana priori regularization for linear programming systems. New polyhedral constraint contraction algorithms are proposed for approximate solution and the relevance of interval programming for good starts or exact solution is brought forth. It is concluded from all this that the imposed problem ignorance of past complexity research is deleterious to research progress on computability or efficiency of computation.This research was partly supported by Project NR047-071, ONR Contract N00014-80-C-0242, and Project NR047-021, ONR Contract N00014-75-C-0569, with the Center for Cybernetic Studies, The University of Texas at Austin.     

一种软件复杂性度量系统的设计与实现

本文结合软件复杂性度量的多种算法,对我们研制开发的一个软件复杂性度量系统,进行了详细介绍,并将系统与已有的各种度量工具进行了分析比较。     

Generalized median graph computation by means of graph embedding in vector spaces

The median graph has been presented as a useful tool to represent a set of graphs. Nevertheless its computation is very complex and the existing algorithms are restricted to use limited amount of data. In this paper we propose a new approach for the computation of the median graph based on graph embedding. Graphs are embedded into a vector space and the median is computed in the vector domain. We have designed a procedure based on the weighted mean of a pair of graphs to go from the vector domain back to the graph domain in order to obtain a final approximation of the median graph. Experiments on three different databases containing large graphs show that we succeed to compute good approximations of the median graph. We have also applied the median graph to perform some basic classification tasks achieving reasonable good results. These experiments on real data open the door to the application of the median graph to a number of more complex machine learning algorithms where a representative of a set of graphs is needed.     

A framework for the verification of infinite-state graph transformation systems

We propose a technique for the analysis of infinite-state graph transformation systems, based on the construction of finite structures approximating their behaviour. Following a classical approach, one can construct a chain of finite under-approximations (k-truncations) of the Winskel style unfolding of a graph grammar. More interestingly, also a chain of finite over-approximations (k-coverings) of the unfolding can be constructed. The fact that k-truncations and k-coverings approximate the unfolding with arbitrary accuracy is formalised by showing that both chains converge (in a categorical sense) to the full unfolding. We discuss how the finite over- and under-approximations can be used to check properties of systems modelled by graph transformation systems, illustrating this with some small examples. We also describe the Augur tool, which provides a partial implementation of the proposed constructions, and has been used for the verification of larger case studies.     

时间复杂度的几种计算方法

算法的时间复杂度是反映算法优劣的重要指标,是《数据结构》的重要理论基础,是学习和教学过程中贯穿始终的主要线索。但是由于概念的抽象和计算方法的繁琐,使算法时间复杂度成为最难理解和掌握的问题之一。在总结教学经验的基础上,该文提出几种常用的时间复杂度计算方法,使对该知识点的教学和学习变得系统和简单。