New Bounds on the Size of Optimal Meshes

The theory of optimal size meshes gives a method for analyzing the output size (number of simplices) of a Delaunay refinement mesh in terms of the integral of a sizing function over the input domain. The input points define a maximal such sizing function called the feature size. This paper presents a way to bound the feature size integral in terms of an easy to compute property of a suitable ordering of the point set. The key idea is to consider the pacing of an ordered point set, a measure of the rate of change in the feature size as points are added one at a time. In previous work, Miller et al. showed that if an ordered point set has pacing ?, then the number of vertices in an optimal mesh will be O(?^dn), where d is the input dimension. We give a new analysis of this integral showing that the output size is only θ(n+nlog?). The new analysis tightens bounds from several previous results and provides matching lower bounds. Moreover, it precisely characterizes inputs that yield outputs of size O(n).     

Ontological query answering under expressive Entity-Relationship schemata

The Entity-Relationship (ER) model is a fundamental tool for database design, recently extended and employed in knowledge representation and reasoning due to its expressiveness and comprehensibility. We address the problem of answering conjunctive queries under constraints representing schemata expressed in an extended version of the Entity-Relationship model. This extended model, called ER⁺, comprises is-a constraints among entities and relationships, plus functional and mandatory participation constraints. In particular, it allows for arbitrary permutations of the roles in is-a among relationships. A key notion that ensures high tractability in ER⁺ schemata is separability, i.e., the absence of interaction between the functional participation constraints and the other constructs of ER⁺. We provide a precise syntactic characterization of separable ER⁺ schemata by means of a necessary and sufficient condition. We present a complete complexity analysis of the conjunctive query answering problem under separable ER⁺ schemata, and also under several sublanguages of ER⁺. We show that the addition of so-called negative constraints does not increase the complexity of query answering. With such constraints, our model properly generalizes the most widely adopted tractable ontology languages, including those in the DL-Lite family.     

Fast wrapper feature subset selection in high-dimensional datasets by means of filter re-ranking

This paper deals with the problem of supervised wrapper-based feature subset selection in datasets with a very large number of attributes. Recently the literature has contained numerous references to the use of hybrid selection algorithms: based on a filter ranking, they perform an incremental wrapper selection over that ranking. Though working fine, these methods still have their problems: (1) depending on the complexity of the wrapper search method, the number of wrapper evaluations can still be too large; and (2) they rely on a univariate ranking that does not take into account interaction between the variables already included in the selected subset and the remaining ones.Here we propose a new approach whose main goal is to drastically reduce the number of wrapper evaluations while maintaining good performance (e.g. accuracy and size of the obtained subset). To do this we propose an algorithm that iteratively alternates between filter ranking construction and wrapper feature subset selection (FSS). Thus, the FSS only uses the first block of ranked attributes and the ranking method uses the current selected subset in order to build a new ranking where this knowledge is considered. The algorithm terminates when no new attribute is selected in the last call to the FSS algorithm. The main advantage of this approach is that only a few blocks of variables are analyzed, and so the number of wrapper evaluations decreases drastically.The proposed method is tested over eleven high-dimensional datasets (2400-46,000 variables) using different classifiers. The results show an impressive reduction in the number of wrapper evaluations without degrading the quality of the obtained subset.     

基于响应面的变复杂度气动分析模型

结合变复杂度和响应面近似建模方法，采用CFD和工程估算气动分析方法，构建了基于响应面校准的变复杂度气动分析模型。以冲压发动机导弹为例，采用拉丁超方取样技术，选取6个CFD计算状态，建立了差值和比值校准响应面，并比较校准后的气动性能与CFD分析。结果显示，基于差值校准响应面的变复杂度方法具有较好的逼近能力和计算效率，适合于飞行器多学科设计优化过程的气动分析。     

复杂适应系统理论与计算机作战模拟

该文介绍了CAS理论的基本思想，对以往的作战模拟手段存在的缺欠和应用CAS理论于作战模拟的优势进行了分析，并对应用CAS理论的计算机平台进行了讨论。以此为基础，建立仿真模型。针对这一模型，说明CAS理论在军事仿真中的其他应用。     

Identification and adaptive control: Towards a complexity-based general theory

Two recent developments will be surveyed here which are pointing the way towards an input–output theory of - adaptive feedback: The solution of problems involving; (1) feedback performance (exact) optimization under large plant uncertainty on the one hand (the two-disc problem of ); and (2) optimally fast identification in on the other. Taken together, these are yielding adaptive algorithms for slowly varying data in - . At a conceptual level, these results motivate a general input-output theory linking identification, adaptation, and control learning. In such a theory, the definition of adaptation is based on system performance under uncertainty, and is independent of internal structure, presence or absence of variable parameters, or even feedback.     

Efficient algorithms for single- and two-layer linear placement of parallel graphs

This paper outlines an algorithm for optimum linear ordering (OLO) of a weighted parallel graph with O(n log k) worst-case time complexity, and O(n + k log(n/k) log k) expected-case time complexity, where n is the total number of nodes and k is the number of chains in the parallel graph. Next, the two-layer OLO problem is considered, where the goal is to place the nodes linearly in two routing layers minimizing the total wire length. The two-layer problem is shown to subsume the maxcut problem and a befitting heuristic algorithm is proposed. Experimental results on randomly generated samples show that the heuristic algorithm runs very fast and outputs optimum solutions in more than 90% instances.     

State-variable planning under structural restrictions: algorithms and complexity

Computationally tractable planning problems reported in the literature so far have almost exclusively been defined by syntactical restrictions. To better exploit the inherent structure in problems, it is probably necessary to study also structural restrictions on the underlying state-transition graph. The exponential size of this graph, though, makes such restrictions costly to test. Hence, we propose an intermediate approach, using a state-variable model for planning and defining restrictions on the separate state-transition graphs for each state variable. We identify such restrictions which can tractably be tested and we present a planning algorithm which is correct and runs in polynomial time under these restrictions. The algorithm has been implemented and it outperforms Graphplan on a number of test instances. In addition, we present an exhaustive map of the complexity results for planning under all combinations of four previously studied syntactical restrictions and our five new structural restrictions. This complexity map considers both the optimal and non-optimal plan generation problem.     

基于XML的VHDL文档生成器的设计与实现

目前在硬件设计领域，硬件描述语言设计信息的交流还没有一个很好的途径。针对这一问题，提出了生成基于XML的VHDL语言源程序文档的设想，并给出了实现实例。     

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

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