Orientation in a maze

Consideration is given to the problem of maze routing: compilation of a route that delivers us from an arbitrary point to a given one. A class of mazes subject to routing (namely, a class of mazes for which the problem of routing can be solved) is described.     

Recursive projection twin support vector machine via within-class variance minimization

In this paper, a novel binary classifier coined projection twin support vector machine (PTSVM) is proposed. The idea is to seek two projection directions, one for each class, such that the projected samples of one class are well separated from those of the other class in its respective subspace. In order to further boost performance, a recursive algorithm for PTSVM is proposed to generate more than one projection axis for each class. To overcome the singularity problem, principal component analysis (PCA) is utilized to transform the data in the original space into a low-dimensional subspace wherein the optimization problem of PTSVM is convex and can be solved efficiently. The experimental results on several UCI benchmark data sets and USPS digit database show the feasibility and effectiveness of the proposed method.     

Bayes Vector Quantizer for Class-Imbalance Problem

The class-imbalance problem is the problem of learning a classification rule from data that are skewed in favor of one class. On these datasets traditional learning techniques tend to overlook the less numerous class, at the advantage of the majority class. However, the minority class is often the most interesting one for the task at hand. For this reason, the class-imbalance problem has received increasing attention in the last few years. In the present paper we point the attention of the reader to a learning algorithm for the minimization of the average misclassification risk. In contrast to some popular class-imbalance learning methods, this method has its roots in statistical decision theory. A particular interesting characteristic is that when class distributions are unknown, the method can work by resorting to stochastic gradient algorithm. We study the behavior of this algorithm on imbalanced datasets, demonstrating that this principled approach allows to obtain better classification performances compared to the principal methods proposed in the literature.     

Analytical kinematics models and special geometries of a class of 4-DOF parallel mechanisms

The paper discusses forward and inverse kinematics of a class of four-degree-of-freedom (DOF), four-legged parallel mechanisms providing three rotational and one translational DOFs. A fully parametric analytical form solution to the inverse-position problem is provided. All working modes of the mechanism are shown and discussed. The equations of the forward-position problem are obtained under different leg arrangements, and a numerical example is provided. New special geometries in the class are proposed, including one suitable for keyhole surgery.     

MNP: A Class of NP Optimization Problems

A large class of NP optimization problems called MNP are studied.It is shown that Rmax(2)is in this class and some problems which are not likely in Rmax(2) are in this class.A new kind of reductions,SL-reductions,is defined to preserve approximability and nonapproximability,so it is a more general version of L-reductions and A-reductions.Then some complete problems of this class under SL-reductions are shown and it is proved that the max-clique problem is one of them.So all complete problems in this class are as difficult to approximate as the max-clique problem.     

An AC 1-complete model checking problem for intuitionistic logic

We show that the model checking problem for intuitionistic propositional logic with one variable is complete for logspace-uniform AC ¹. For superintuitionistic logics with one variable, we obtain NC ¹-completeness for the model checking problem.     

基于关系模型的UML类图一致性检验

UML类图是UML建模语言的核心元素之一,类图模型的正确性和一致性对于保证需求分析的正确性至关重要。论文研究了UML类图模型的语义一致性问题,提出了一种自动检验类图一致性的方法。该方法以扩展的关系逻辑为语义基础,把一致性问题归结为关系逻辑公式的可满足性问题。实践表明,该方法能够有效的检查UML类图模型的一致性,发现需求分析中的错误和漏洞,在一定程度上保证了类图模型的正确性。     

Top-<Emphasis Type="Italic">k</Emphasis> overlapping densest subgraphs

Finding dense subgraphs is an important problem in graph mining and has many practical applications. At the same time, while large real-world networks are known to have many communities that are not well-separated, the majority of the existing work focuses on the problem of finding a single densest subgraph. Hence, it is natural to consider the question of finding the top-k densest subgraphs. One major challenge in addressing this question is how to handle overlaps: eliminating overlaps completely is one option, but this may lead to extracting subgraphs not as dense as it would be possible by allowing a limited amount of overlap. Furthermore, overlaps are desirable as in most real-world graphs there are vertices that belong to more than one community, and thus, to more than one densest subgraph. In this paper we study the problem of finding top-k overlapping densest subgraphs, and we present a new approach that improves over the existing techniques, both in theory and practice. First, we reformulate the problem definition in a way that we are able to obtain an algorithm with constant-factor approximation guarantee. Our approach relies on using techniques for solving the max-sum diversification problem, which however, we need to extend in order to make them applicable to our setting. Second, we evaluate our algorithm on a collection of benchmark datasets and show that it convincingly outperforms the previous methods, both in terms of quality and efficiency.     

The equivalence and inclusion problems for NTS languages

A context-free grammar is said to be NTS if the set of sentential forms it generates is unchanged when the rules are used both ways. We prove that this class of grammars has a decidable equivalence problem. Then we show that one can decide whether a given c.f. grammar is NTS or not. We prove that the class of NTS grammars has an undecidable inclusion problem.     

C＋＋中构造函数的三种调用问题解析

构造函数是一种用于创建对象的特殊成员函数,构造函数的调用顺序问题对类的定义至关重要,本文从简单类对象的创建、类组合（一个类的对象是另一个类的数据成员）和类继承三种情况下分析了构造函数的调用问题,一定程度上诠释了类定义中的这一关键因素,为更好掌握C＋＋的编程思想提供了理论依据和程序示例。     

An improved protein fold recognition with support vector machines

Predicting the three‐dimensional structure (fold) of a protein is a key problem in molecular biology. It is also interesting issue for statistical methods recognition. In this paper a multi‐class support vector machine (SVM) classifier is used on a real world data set. The SVM is a binary classifier, but protein fold recognition is a multi‐class problem. So several new approaches to deal with this issue are presented including a modification of the well‐known one‐versus‐one strategy. However, in this strategy the number of different binary classifiers that must be trained is quickly increasing with the number of classes. The methods proposed in this paper show how this problem can be overcome.     

Parallel computations and committee constructions

The paper reviewed the results bearing out the deep-seated relation between the parallel computations and learning procedures for the laminated neural networks one of whose formalizations is represented by the theory of committee constructions. Additionally, consideration was given to two combinatorial problems concerned with learning pattern recognition in the class of affine committees—the problem of verifying existence of a three-element affine separating committee and that of element-minimal affine separating committee. The first problem was shown to be N P-complete, whereas the second problem is N P-hard and does not belong to the Apx class.     

Exact Algorithms for Finding Longest Cycles in Claw-Free Graphs

The Hamiltonian Cycle problem is the problem of deciding whether an n-vertex graph G has a cycle passing through all vertices of G. This problem is a classic NP-complete problem. Finding an exact algorithm that solves it in ${\mathcal {O}}^{*}(\alpha^{n})$ time for some constant α<2 was a notorious open problem until very recently, when Björklund presented a randomized algorithm that uses ${\mathcal {O}}^{*}(1.657^{n})$ time and polynomial space. The Longest Cycle problem, in which the task is to find a cycle of maximum length, is a natural generalization of the Hamiltonian Cycle problem. For a claw-free graph G, finding a longest cycle is equivalent to finding a closed trail (i.e., a connected even subgraph, possibly consisting of a single vertex) that dominates the largest number of edges of some associated graph H. Using this translation we obtain two deterministic algorithms that solve the Longest Cycle problem, and consequently the Hamiltonian Cycle problem, for claw-free graphs: one algorithm that uses ${\mathcal {O}}^{*}(1.6818^{n})$ time and exponential space, and one algorithm that uses ${\mathcal {O}}^{*}(1.8878^{n})$ time and polynomial space.     

A rough margin-based one class support vector machine

We propose a rough margin-based one class support vector machine (Rough one class SVM) by introducing the rough set theory into the one class SVM, to deal with the over-fitting problem. We first construct rough lower margin, rough upper margin, and rough boundary and then maximize the rough margin rather than the margin in the one class SVM. Thus, more points are adaptively considered in constructing the separating hyper-plane than those used in the conventional one class SVM. Moreover, different points staying at the different positions are proposed to give different penalties. Specifically, the samples staying at the lower margin are given the larger penalties than those in the boundary of the rough margin. Therefore, the new classifier can avoid the over-fitting problem to a certain extent and yields great generalization performance. Experimental results on one artificial dataset and eight benchmark datasets demonstrate the feasibility and validity of our proposed algorithm.     

Semidefinite Relaxation and New Conditions for Sign-Definiteness of the Quadratic Form under Quadratic Constraints

Use of the semidefinite relaxation in the problem of sign-definiteness of the quadratic form under quadratic constraints enables one to establish from the duality conditions an S-procedure. However, the S-procedure giving the necessary and sufficient conditions for signdefiniteness of the relaxed problem provides only the sufficient conditions for sign-definiteness for the original problem for the case of two and more quadratic constraints. This property is called the deficiency of S-procedure. A method was proposed enabling one in some cases to establish the conditional sign-definiteness in the case where the S-procedure provides a negative result. This method give the necessary and sufficient conditions for sign-definiteness in the two-dimensional case. An example was given.     

一类混合动态系统(HDS)的时间最优路由调度*

本文研究服务过程为连续动态过程的单服务台型混合动态系统（ＨＤＳ）的时间最短路由调度问题。通过定义事件函数和估计服务时间，本文证明在一定条件下，可将此类动态调度问题化为静态调度问题加以求解。     

Adaptive search for one defective in the additive group testing model

In contrast to the problem of finding all defective elements in group testing, we consider the problem of finding one defective in a set D of defective elements of cardinality d. We consider adaptive search algorithms only. A similar problem for the classical and threshold models was solved in [1]. In the present paper we consider the additive testing model. We obtain an optimal answer in the problem of adaptive search of one defective element in this model.     

Output Regulation for a Class of Infinite Dimensional Systems with an Unknown Exosystem

This paper is about solving the output regulation problem for a class of infinite dimensional systems with an unknown exosystem. First, under the unit relative degree assumption, the infinite dimensional system is decomposed into a cascaded one composed of a one‐dimensional system and an infinite dimensional system. Then, the problem is solved by combining an adaptive internal model and an adaptive control. The presented results are illustrated via a periodic tracking problem of a heat equation.     

基于融合的多类支持向量机

支持向量机可以处理2类问题,通过“一对一”和“一对多”方式能将2类支持向量机扩展为多类支持向量机。提出一种基于两类支持向量机融合的多类支持向量机构成方法。对分类器融合采用极大值法、极小值法、乘积法、均值法、中值法、投票法和各种决策模板融合方法。在日本女性表情数据库JAFFE上应用该方法进行人脸表情识别,结果证明了其有效性。     

Analytical solution of the optimal slew problem for an axisymmetric spacecraft in the class of conical motions

The traditional problem is discussed of an optimal spacecraft slew in terms of minimum energy costs. The spacecraft is considered as a rigid body with one symmetry axis under arbitrary boundary conditions for the angular position and angular velocity of the spacecraft in the quaternion formulation. Using substitutions of variables, the original problem is simplified (in terms of dynamic Euler equations) to the optimal slew problem for a rigid body with a spherical mass distribution. The simplified problem contains one additional scalar differential equation. A new analytical solution is presented for this problem in the class of conical motions, leading to constraints on the initial and final values of the angular velocity vector. In addition, the optimal slew problem is modified in the class of conical motions to derive an analytical solution under arbitrary boundary conditions for the angular position and angular velocity of the spacecraft. A numerical example is given for the conical motion of the spacecraft, as well as examples showing the closeness of the solutions of the traditional and modified optimal slew problems for an axisymmetric spacecraft.