Boolean functions with long prime implicants

In this short note we introduce a hierarchy of classes of Boolean functions, where each class is defined by the minimum allowed length of prime implicants of the functions in the class. We show that for a given DNF and a given class in the hierarchy, it is possible to test in polynomial time whether the DNF represents a function from the given class. For the first class in the hierarchy we moreover present a polynomial time algorithm which for a given input DNF outputs a shortest logically equivalent DNF, i.e. a shortest DNF representation of the underlying function. This class is therefore a new member of a relatively small family of classes for which the Boolean minimization problem can be solved in polynomial time. For the second class and higher classes in the hierarchy we show that the Boolean minimization problem can be approximated within a constant factor.     

Dynamic cluster generation for a fuzzy classifier with ellipsoidalregions

In this paper, we discuss a fuzzy classifier with ellipsoidal regions that dynamically generates clusters. First, for the data belonging to a class we define a fuzzy rule with an ellipsoidal region. Namely, using the training data for each class, we calculate the center and the covariance matrix of the ellipsoidal region for the class. Then we tune the fuzzy rules, i.e., the slopes of the membership functions, successively until there is no improvement in the recognition rate of the training data. Then if the number of the data belonging to a class that are misclassified into another class exceeds a prescribed number, we define a new cluster to which those data belong and the associated fuzzy rule. Then we tune the newly defined fuzzy rules in the similar way as stated above, fixing the already obtained fuzzy rules. We iterate generation of clusters and tuning of the newly generated fuzzy rules until the number of the data belonging to a class that are misclassified into another class does not exceed the prescribed number. We evaluate our method using thyroid data, Japanese Hiragana data of vehicle license plates, and blood cell data. By dynamic cluster generation, the generalization ability of the classifier is improved and the recognition rate of the fuzzy classifier for the test data is the best among the neural network classifiers and other fuzzy classifiers if there are no discrete input variables     

Nonlinear time-varying controllers for robust stabilization

In this paper we consider the problem of robust stabilizallon for a certain class of plants with unstructured, infinite-dimensional uncertainty. We demonstrate that for the problem of robustly stabilizing this class of plants, linear time-invariant controllers perform as well as nonlinear time-varying (NLTV) ones. Ihis, in particular, implies that adaptive control laws offer no advantage as far as the problem of robust stabilization of this class of plants is concerned. As a corollary we demonstrate that the small-gain theorem is both necessary and sufficient for a certain class of NLTV operators.     

Invariant-Free Clausal Temporal Resolution

Resolution is a well-known proof method for classical logics that is well suited for mechanization. The most fruitful approach in the literature on temporal logic, which was started with the seminal paper of M. Fisher, deals with Propositional Linear-time Temporal Logic (PLTL) and requires to generate invariants for performing resolution on eventualities. The methods and techniques developed in that approach have also been successfully adapted in order to obtain a clausal resolution method for Computation Tree Logic (CTL), but invariant handling seems to be a handicap for further extension to more general branching temporal logics. In this paper, we present a new approach to applying resolution to PLTL. The main novelty of our approach is that we do not generate invariants for performing resolution on eventualities. Hence, we say that the approach presented in this paper is invariant-free. Our method is based on the dual methods of tableaux and sequents for PLTL that we presented in a previous paper. Our resolution method involves translation into a clausal normal form that is a direct extension of classical CNF. We first show that any PLTL-formula can be transformed into this clausal normal form. Then, we present our temporal resolution method, called trs-resolution, that extends classical propositional resolution. Finally, we prove that trs-resolution is sound and complete. In fact, it finishes for any input formula deciding its satisfiability, hence it gives rise to a new decision procedure for PLTL.     

OODB延迟视图维护模型

针对面向对象数据库中视图的特点，提出了一个延迟视图维护的模型以及相关的更新算法，在视图更新时，要考虑导出它的类的改动，以有以此类为根的继承和类组成子层次结构中的所有类的改动，因此，为每个类添加一个修改列表，为依赖于它的视图保存修改信息。     

Current and future research directions in network optimization

In this paper, we discuss a number of current and future research directions in network optimization. First, we categorize current research efforts as primarily methodological or primarily applied and we carefully define the boundaries of each class. In addition, we survey the present capabilities of network algorithms. Next, we delineate objectives in each class. Finally, we list several network problems for each class that should, in our opinion, be investigated and we give pertinent background information.     

Nonlinear observer design for a general class of nonlinear systems with real parametric uncertainty

This paper is a geometric study of the local observer design for a general class of nonlinear systems with real parametric uncertainty. Explicitly, we study the observer design problem for a general class of nonlinear systems with real parametric uncertainty and with an input generator (exosystem). In this paper, we show that for the classical case, when the state equilibrium does not change with the parametric uncertainty, and when the plant output is purely a function of the state, there is no local asymptotic observer for the plant. Next, we show that in sharp contrast to this case, for the general case of problems where we allow the state equilibrium to change with the parametric uncertainty, there typically exist local exponential observers even when the plant output is purely a function of the state. We also present a characterization and construction procedure for local exponential observers for the general class of nonlinear systems with real parametric uncertainty under some stability assumptions. We also show that for the general class of nonlinear systems considered, under some stability assumptions, the existence of local exponential observers in the presence of inputs implies, and is implied by, the existence of local exponential observers in the absence of inputs. Finally, we generalize our results to a general class of nonlinear systems with input generator, and with exogenous disturbance.     

COG: local decomposition for rare class analysis

Given its importance, the problem of predicting rare classes in large-scale multi-labeled data sets has attracted great attention in the literature. However, rare class analysis remains a critical challenge, because there is no natural way developed for handling imbalanced class distributions. This paper thus fills this crucial void by developing a method for classification using local clustering (COG). Specifically, for a data set with an imbalanced class distribution, we perform clustering within each large class and produce sub-classes with relatively balanced sizes. Then, we apply traditional supervised learning algorithms, such as support vector machines (SVMs), for classification. Along this line, we explore key properties of local clustering for a better understanding of the effect of COG on rare class analysis. Also, we provide a systematic analysis of time and space complexity of the COG method. Indeed, the experimental results on various real-world data sets show that COG produces significantly higher prediction accuracies on rare classes than state-of-the-art methods and the COG scheme can greatly improve the computational performance of SVMs. Furthermore, we show that COG can also improve the performances of traditional supervised learning algorithms on data sets with balanced class distributions. Finally, as two case studies, we have applied COG for two real-world applications: credit card fraud detection and network intrusion detection.     

Synchronization of a class of nonlinear network flow systems

In this paper, we consider the synchronization of a class of nonlinear network flow systems. Motivated by air distribution problem in air conditioning and mechanical ventilation (ACMV) systems, we propose a class of coupled nonlinear multi‐agent systems that can model a wide class of network flow systems, including air flow in ACMV systems, water flow in irrigation systems, traffic flow in transportation systems, and so on. Then we consider the synchronization problem for the class of nonlinear multi‐agent systems and propose cooperative controllers for the system. Based on graph theory, we derive conditions on the initial values of the state and the control input such that synchronization can be achieved. An application to air ventilation is provided to demonstrate the effectiveness of the cooperative controllers. Copyright © 2015 John Wiley & Sons, Ltd.     

Channel sharing by multi-class rate adaptive streams: Performance region and optimization

We consider the problem of channel sharing by rate adaptive streams belonging to various classes. The performance metric per class is the mean bandwidth allocated to connections in the class possibly scaled by appropriate factors. We first provide a bandwidth adaptation policy that maximizes a linear combination of class performance metrics; then, we use this result to characterize the region where the class performance metrics lie under any bandwidth adaptation policy. Based on the results above we use stochastic approximation techniques to provide a policy that optimizes a combination of concave rewards associated with class performance metrics. Finally, we propose a modification of the optimal policy to account for the case where connection holding times are unknown, and study its performance through simulations.     

Simple and efficient local codes for distributed stable network construction

In this work, we study protocols so that populations of distributed processes can construct networks. In order to highlight the basic principles of distributed network construction, we keep the model minimal in all respects. In particular, we assume finite-state processes that all begin from the same initial state and all execute the same protocol. Moreover, we assume pairwise interactions between the processes that are scheduled by a fair adversary. In order to allow processes to construct networks, we let them activate and deactivate their pairwise connections. When two processes interact, the protocol takes as input the states of the processes and the state of their connection and updates all of them. Initially all connections are inactive and the goal is for the processes, after interacting and activating/deactivating connections for a while, to end up with a desired stable network. We give protocols (optimal in some cases) and lower bounds for several basic network construction problems such as spanning line, spanning ring, spanning star, and regular network. The expected time to convergence of our protocols is analyzed under a uniform random scheduler. Finally, we prove several universality results by presenting generic protocols that are capable of simulating a Turing Machine (TM) and exploiting it in order to construct a large class of networks. We additionally show how to partition the population into k supernodes, each being a line of \(\log k\) nodes, for the largest such k. This amount of local memory is sufficient for the supernodes to obtain unique names and exploit their names and their memory to realize nontrivial constructions.     

Linear-time filtering algorithms for the disjunctive constraint and a quadratic filtering algorithm for the cumulative not-first not-last

We present new filtering algorithms for Disjunctive and Cumulative constraints, each of which improves the complexity of the state-of-the-art algorithms by a factor of log n. We show how to perform Time-Tabling and Detectable Precedences in linear time on the Disjunctive constraint. Furthermore, we present a linear-time Overload Checking for the Disjunctive and Cumulative constraints. Finally, we show how the rule of Not-first/Not-last can be enforced in quadratic time for the Cumulative constraint. These algorithms rely on the union find data structure, from which we take advantage to introduce a new data structure that we call it time line. This data structure provides constant time operations that were previously implemented in logarithmic time by the Θ-tree data structure. Experiments show that these new algorithms are competitive even for a small number of tasks and outperform existing algorithms as the number of tasks increases. We also show that the time line can be used to solve specific scheduling problems.     

MTP: discovering high quality partitions in real world graphs

Given a real world graph, how can we find a large subgraph whose partition quality is much better than the original? How can we use a partition of that subgraph to discover a high quality global partition? Although graph partitioning especially with balanced sizes has received attentions in various applications, it is known NP-hard, and also known that there is no good cut at a large scale for real graphs. In this paper, we propose a novel approach for graph partitioning. Our first focus is on finding a large subgraph with high quality partitions, in terms of conductance. Despite the difficulty of the task for the whole graph, we observe that there is a large connected subgraph whose partition quality is much better than the original. Our proposed method MTP finds such a subgraph by removing “hub” nodes with large degrees, and taking the remaining giant connected component. Further, we extend MTP to gb MTP (Global Balanced MTP) for discovering a global balanced partition. gb MTP attaches the excluded nodes in MTP to the partition found by MTP in a greedy way. In experiments, we demonstrate that MTP finds a subgraph of a large size with low conductance graph partitions, compared with competing methods. We also show that the competitors cannot find connected subgraphs while our method does, by construction. This improvement in partition quality for the subgraph is especially noticeable for large scale cuts—for a balanced partition, down to 14 % of the original conductance with the subgraph size 70 % of the total. As a result, the found subgraph has clear partitions at almost all scales compared with the original. Moreover, gb MTP generally discovers global balanced partitions whose conductance are lower than those found by METIS, the state-of-the-art graph partitioning method.     

Nonlinear observer design for a general class of discrete-time nonlinear systems with real parametric uncertainty

This paper is a geometric study of the local observer design for a general class of discrete-time nonlinear systems with real parametric uncertainty. Explicitly, we study the observer design problem for a general class of discrete-time nonlinear systems with real parametric uncertainty and with an input generator (exosystem). In this paper, we show that for the classical case, when the state equilibrium does not change with the parametric uncertainty, and when the plant output is purely a function of the state, there is no local asymptotic observer for the plant. Next, we show that in sharp contrast to this case, for the general case of problems where we allow the state equilibrium to change with the parametric uncertainty, there typically exist local exponential observers even when the plant output is purely a function of the state. We also present a characterization and construction procedure for local exponential observers for the general class of discrete-time nonlinear systems with real parametric uncertainty under some stability assumptions. We also show that for the general class of discrete-time nonlinear systems considered, under some stability assumptions, the existence of local exponential observers in the presence of inputs implies, and is implied by the existence of local exponential observers in the absence of inputs. Finally, we generalize our results to a general class of discrete-time nonlinear systems with input generator, and with exogenous disturbance.     

Downward pattern refinement for timed automata

Directed model checking is a well-established approach for detecting error states in concurrent systems. A popular variant to find shortest error traces is to apply the A\(^*\) search algorithm with distance heuristics that never overestimate the real error distance. An important class of such distance heuristics is the class of pattern database heuristics. Pattern database heuristics are built on abstractions of the system under consideration. In this paper, we propose downward pattern refinement, a systematic approach for the construction of pattern database heuristics for concurrent systems of timed automata. First, we propose a general framework for pattern databases in the context of timed automata and show that desirable theoretical properties hold for the resulting pattern database. Afterward, we formally define a concept to measure the accuracy of abstractions. Based on this concept, we propose an algorithm for computing succinct abstractions that are still accurate to produce informed pattern databases. We evaluate our approach on large and complex industrial problems. The experiments show the practical potential of the resulting pattern database heuristic.     

Extending SMT solvers with support for finite domain <Literal>alldifferent</Literal> constraint

In this paper we consider integration of SMT solvers with the filtering algorithms for the finite domain alldifferent constraint. Such integration makes SMT solvers suitable for solving constraint satisfaction problems with the alldifferent constraint involved. First, we present a novel algorithm for explaining inconsistencies and propagations in the alldifferent constraint. We compare it to Katsirelos’ algorithm and flow-based algorithms that are commonly used for that purpose. Then we describe our DPLL(T)-compliant SMT theory solver for constraint satisfaction problems that include alldifferent constraints. We also provide an experimental evaluation of our approach.     

Contraction-Free Linear Depth Sequent Calculi for Intuitionistic Propositional Logic with the Subformula Property and Minimal Depth Counter-Models

In this paper we present LSJ, a contraction-free sequent calculus for Intuitionistic propositional logic whose proofs are linearly bounded in the length of the formula to be proved and satisfy the subformula property. We also introduce a sequent calculus RJ for intuitionistic unprovability with the same properties of LSJ. We show that from a refutation of RJ of a sequent σ we can extract a Kripke counter-model for σ. Finally, we provide a procedure that given a sequent σ returns either a proof of σ in LSJ or a refutation in RJ such that the extracted counter-model is of minimal depth.     

The Complexity of the Descriptiveness of Boolean Circuits over Different Sets of Gates

Any Boolean function can be defined by a Boolean circuit, provided we may use sufficiently strong functions in its gates. On the other hand, what Boolean functions can be defined depends on these gate functions: Each set B of gate functions defines the class of Boolean functions that can be defined by circuits over B. Although these classes have been known since the 1920s, their computational complexity was never investigated.In this paper we will study how difficult it is to decide for a Boolean function f and a class B, whether f is in B.Moreover, we will provide such a decision algorithm with additional information: How difficult is it to decide whether or not f is in B, provided we already know a circuit for f, but with gates from another class A? Given such a circuit, we know that f is in A. Is the problem harder if we do not have a concrete representation for f, but still know that it is from A? For nearly all possible combinations, we show that this is not the case, and that the problem is either in P or coNP-complete.     

一种增强的κ-means聚类算法

本文针对κ-modes算法在类的表示方面存在的不足，提出用摘要信息来表示一个类，并给出了一种适用于混合属性的距离定义，得到增强的κ-means算法--κ-summary算法 。理论分析和实验结果表明，κ-sumnlary算法较κ-modes算法和κ-prototypes算法具有更好的精度。     

Nonlocal PDEs on Graphs: From Tug-of-War Games to Unified Interpolation on Images and Point Clouds

In this paper, we introduce a new general class of partial difference operators on graphs, which interpolate between the nonlocal \(\infty \)-Laplacian, the Laplacian, and a family of discrete gradient operators. In this context, we investigate an associated Dirichlet problem for this general class of operators and prove the existence and uniqueness of respective solutions. We show that a certain partial difference equation based on this class of operators recovers many variants of a stochastic game known as ‘Tug-of-War’ and extends them to a nonlocal setting. Furthermore, we discuss a connection with certain nonlocal partial differential equations. Finally, we propose to use this class of operators as general framework to solve many interpolation problems in a unified manner as arising, e.g., in image and point cloud processing.