保持拓扑结构的低维嵌入

引入了拓扑邻域、拓扑结构和规则拓扑结构的概念.对拓扑邻域进行了理论分析,说明其是自适应的,随着维数的不断升高,趋于平凡拓扑邻域.为了寻求具有规则拓扑结构的低维数据集,构造了数据结构规则性的度量,提出了保持数据集拓扑结构不变的降维方法.该方法是节省参数的,降维结果是近似规则的.结果表明,它能更好的揭示数据集的结构.     

How to find Steiner minimal trees in euclideand-space

This paper has two purposes. The first is to present a new way to find a Steiner minimum tree (SMT) connectingN sites ind-space,d >- 2. We present (in Appendix 1) a computer code for this purpose. This is the only procedure known to the author for finding Steiner minimal trees ind-space ford > 2, and also the first one which fits naturally into the framework of backtracking and branch-and-bound. Finding SMTs of up toN = 12 general sites ind-space (for anyd) now appears feasible.We tabulate Steiner minimal trees for many point sets, including the vertices of most of the regular and Archimedeand-polytopes with <- 16 vertices. As a consequence of these tables, the Gilbert-Pollak conjecture is shown to be false in dimensions 3–9. (The conjecture remains open in other dimensions; it is probably false in all dimensionsd withd 3, but it is probably true whend = 2.)The second purpose is to present some new theoretical results regarding the asymptotic computational complexity of finding SMTs to precision .We show that in two-dimensions, Steiner minimum trees may be found exactly in exponential time O(C ^N ) on a real RAM. (All previous provable time bounds were superexponential.) If the tree is only wanted to precision , then there is an (N/)^O(N)-time algorithm, which is subexponential if 1/ grows only polynomially withN. Also, therectilinear Steiner minimal tree ofN points in the plane may be found inN ^O(N) time.J. S. Provan devised an O(N ⁶/⁴)-time algorithm for finding the SMT of a convexN-point set in the plane. (Also the rectilinear SMT of such a set may be found in O(N ⁶) time.) One therefore suspects that this problem may be solved exactly in polynomial time. We show that this suspicion is in fact true—if a certain conjecture about the size of Steiner sensitivity diagrams is correct.All of these algorithms are for a real RAM model of computation allowing infinite precision arithmetic. They make no probabilistic or other assumptions about the input; the time bounds are valid in the worst case; and all our algorithms may be implemented with a polynomial amount of space. Only algorithms yielding theexact optimum SMT, or trees with lengths (1 + ) × optimum, where is arbitrarily small, are considered here.     

Approximate regular expression pattern matching with concave gap penalties

Given a sequenceA of lengthM and a regular expressionR of lengthP, an approximate regular expression pattern-matching algorithm computes the score of the optimal alignment betweenA and one of the sequencesB exactly matched byR. An alignment between sequencesA=a₁a₂ ... a_M andB=b₁b₂... b_N is a list of ordered pairs, (i₁,j₁), (i₂j₂), ..., (i_t,j_tt) such that i_k < i_k+1 and j_k < j_k+1. In this case the alignmentaligns symbols a_ik and b_jk, and leaves blocks of unaligned symbols, orgaps, between them. A scoring schemeS associates costs for each aligned symbol pair and each gap. The alignment's score is the sum of the associated costs, and an optimal alignment is one of minimal score. There are a variety of schemes for scoring alignments. In a concave gap penalty scoring schemeS={, w}, a function (a, b) gives the score of each aligned pair of symbolsa andb, and aconcave function w(k) gives the score of a gap of lengthk. A function w is concave if and only if it has the property that, for allk > 1, w(k + 1) –w(k) w(k) –w(k –1). In this paper we present an O(MP(logM + log² P)) algorithm for approximate regular expression matching for an arbitrary and any concavew. This work was supported in part by the National Institute of Health under Grant RO1 LM04960.     

作业流的结构化定义方法

作业流，也称作业网络，是相互关联的作业形成的一个偏序集。由于作业间存在着顺序、分支、循环、并行、同步、异步等依赖关系，因此作业流可能非常复杂。如果没有一个良好的定义准则，那么生成的作业流将结构混乱，不利于查错、解析，也不利于可视化显示。该文归纳了作业间的依赖关系，提出了作业流的结构化定义方法。这种方法简单地表达了作业间的多种依赖关系，它也能表达作业流间的层次和嵌套关系。     

由有穷自动机构造正则表达式的新算法

本文借助图论的理论，通过识别回路和不包含回路的由起始状态到终止状态的路径的方法，提出一种构造给定有穷自动机对应的正则表达式的新算法，并给出具体实例。     

Exact formulations and algorithm for the train timetabling problem with dynamic demand

In this paper we study the design and optimization of train timetabling adapted to a dynamic demand environment. This problem arises in rapid train services which are common in most important cities. We present three formulations for the problem, with the aim of minimizing passenger average waiting time. The most intuitive model would consider binary variables representing train departure times but it yields to non-linear objective function. Instead, we introduce flow variables, which allow a linear representation of the objective function. We provide incremental improvements on these formulations, which allows us to evaluate and compare the benefits and disadvantages of each modification. We present a branch-and-cut algorithm applicable to all formulations. Through extensive computational experiments on several instances derived from real data provided by the Madrid Metropolitan Railway, we show the advantages of designing a timetable adapted to the demand pattern, as opposed to a regular timetable. We also perform an extensive computational comparison of all linear formulations in terms of size, solution quality and running time.     

Obtaining shorter regular expressions from finite-state automata

We consider the use of state elimination to construct shorter regular expressions from finite-state automata (FAs). Although state elimination is an intuitive method for computing regular expressions from FAs, the resulting regular expressions are often very long and complicated. We examine the minimization of FAs to obtain shorter expressions first. Then, we introduce vertical chopping based on bridge states and horizontal chopping based on the structural properties of given FAs. We prove that we should not eliminate bridge states until we eliminate all non-bridge states to obtain shorter regular expressions. In addition, we suggest heuristics for state elimination that leads to shorter regular expressions based on vertical chopping and horizontal chopping.     

A lower bound on the size of ε-free NFA corresponding to a regular expression

Hromkovic? et al. showed how to transform a regular expression of size n into an ε-free nondeterministic finite automaton (which defines the same language as the expression) with O(n) states and O(nlog²(n)) transitions. They also established a lower bound on the number of transitions. We improve the lower bound to .     

On filter theory of residuated lattices

The aim of this paper is to develop the filter theory of general residuated lattices. First, we extend some particular types of filters and fuzzy filters in BL-algebras and MTL-algebras naturally to general residuated lattices, and further enumerate some relative results obtained in BL-algebras or MTL-algebras, which still hold in general residuated lattices. Next, we introduce the concepts of regular filters and fuzzy regular filters to general residuated lattices, which are two new types of filters and fuzzy filters, and derive some of their characterizations. Finally, we discuss the relations between (fuzzy) regular filters and several other special (fuzzy) filters, and also characterize some special classes of residuated lattices by filters or fuzzy filters.     

Mkscan—An interactive scanner generator

Mkscan is a tool for generating and editing scanners. It has been designed with ease of use in mind. The tol is interactive and uses a full screen interface. No attempt is made to provide an all-purpose tool that can generate a recognizer for any regular language. Instead, mkscan has been tailored to suit the lexical structure of common programming languages and command languages. Using mkscan, a scanner for Pascal can be created in under ten minutes–including the time taken to type the list of keywords.