Propagation via lazy clause generation

Finite domain propagation solvers effectively represent the possible values of variables by a set of choices which can be naturally modelled as Boolean variables. In this paper we describe how to mimic a finite domain propagation engine, by mapping propagators into clauses in a SAT solver. This immediately results in strong nogoods for finite domain propagation. But a naive static translation is impractical except in limited cases. We show how to convert propagators to lazy clause generators for a SAT solver. The resulting system introduces flexibility in modelling since variables are modelled dually in the propagation engine and the SAT solver, and we explore various approaches to the dual modelling. We show that the resulting system solves many finite domain problems significantly faster than other techniques. This paper is an extension of results first published in [29, 30].     

Solving RCPSP/max by lazy clause generation

We present a generic exact method for minimizing the project duration of the resource-constrained project scheduling problem with generalized precedence relations (Rcpsp/max). This is a very general scheduling model with applications areas such as project management and production planning. Our method uses lazy clause generation, i.e., a hybrid of finite domain and Boolean satisfiability solving, in order to apply no-good learning and conflict-driven search to the solution generation. Our experiments show the benefit of lazy clause generation for finding an optimal solution and proving its optimality in comparison to other state-of-the-art exact and non-exact methods. In comparison to other methods, our method is able to find better solutions faster on the Rcpsp/max benchmarks. Indeed, our method closes 573 open problem instances and generates better solutions in most of the remaining instances. Surprisingly, although ours is an exact method, it outperforms the published non-exact methods on these benchmarks in terms of the quality of solutions.     

情感子句预测与原因子句提取方法

为减少人工成本,提出在未给定情感标签情况下预测文本情感子句,同时提取原因子句的方法.使用CNN提取局部语义信息,使用带有注意力的Bi-LSTM提取句子上下文语义信息以及情感表达的关键部分信息,将这3类信息结合获取更好的句子特征来进行情感预测;通过注意力将预测的情感标签与句子特征结合,提取原因.实验结果表明,模型在情感子句预测和原因子句提取任务中均取得目前最好结果,在未给定文本情感标签的情况下,原因提取效果仍优于大部分传统模型.     

Automatic generation of colorful patterns with wallpaper symmetries from dynamics

A new algorithm is presented in this paper for the generation of colorful images with wallpaper symmetries by means of dynamical systems. Invariant functions are employed to construct density functions for the creation of colorful images.     

Symmetries, Group Actions, and Entanglement

We address several problems concerning the geometry of the space of Hermitian operators on a finite-dimensional Hilbert space, in particular the geometry of the space of density states and canonical group actions on it. For quantum composite systems we discuss and give examples of entanglement measures.     

Dataflow computing and eager and lazy evaluations

Eager and lazy evaluations in a dataflow model are proposed, Such evaluation enables nonstrict evaluation, structure data manipulation and nondeterminate computation. Several dataflow computation models are discussed from the viewpoint of their by-value and by-reference mechanisms, i. e., their token to data correspondence. It is shown that effective implementation is achieved by unifying both mechanisms. This implies the effective implementation of the lenient cons and lazy cons concept in list manipulation. Nonstrict list manipulation is shown to be useful for stream-oriented processing, and for nondeterminate computation combined with the nonstrict primitive operator, Arbiter. Several sample programs are included to show that concurrent processes and object-oriented programs can be intuitively described in functional language.     

GENPRO: automatic generation of Prolog clause files for knowledge-based systems in the biomedical sciences

With the increasing interest in using knowledge-based approaches for protein structure prediction and modelling, there is a requirement for general techniques to convert molecular biological data into structures that can be interpreted by artificial intelligence programming languages (e.g. Prolog). We describe here an interactive program that generates files in Prolog clausal form from the most commonly distributed protein structural data collections. The program is flexible and enables a variety of clause structures to be defined by the user through a general schema definition system. Our method can be extended to include other types of molecular biological database or those containing non-structural information, thus providing a uniform framework for handling the increasing volume of data available to knowledge-based systems in biomedicine.     

Nash equilibria: Complexity,symmetries, and approximation

We survey recent joint work with Christos Papadimitriou and Paul Goldberg on the computational complexity of Nash equilibria. We show that finding a Nash equilibrium in normal form games is computationally intractable, but in an unusual way. It does belong to the class NP; but Nash’s theorem, showing that a Nash equilibrium always exists, makes the possibility that it is also NP-complete rather unlikely. We show instead that the problem is as hard computationally as finding Brouwer fixed points, in a precise technical sense, giving rise to a new complexity class called PPAD. The existence of the Nash equilibrium was established via Brouwer’s fixed-point theorem; hence, we provide a computational converse to Nash’s theorem.To alleviate the negative implications of this result for the predictive power of the Nash equilibrium, it seems natural to study the complexity of approximate equilibria: an efficient approximation scheme would imply that players could in principle come arbitrarily close to a Nash equilibrium given enough time. We review recent work on computing approximate equilibria and conclude by studying how symmetries may affect the structure and approximation of Nash equilibria. Nash showed that every symmetric game has a symmetric equilibrium. We complement this theorem with a rich set of structural results for a broader, and more interesting class of games with symmetries, called anonymous games.     

Sequential consistency and the lazy caching algorithm

Summary. I introduce and discuss sequential consistency, a relaxed memory model, and define what it means for a protocol to implement sequential consistency. Then, I introduce the lazy caching protocol of Afek, Brown and Merrit [ABM93] and formalize it as a labeled transition system.     

Side-effect localization for lazy, purely functional languages via aspects

Many side-effecting programming activities, such as profiling and tracing, can be formulated as crosscutting concerns and be framed as side-effecting aspects in the aspect-oriented programming paradigm. The benefit gained from this separation of concerns is particularly evident in purely functional programming, as adding such aspects using techniques such as monadification will generally lead to crosscutting changes. This paper presents an approach to provide side-effecting aspects for lazy purely functional languages in a user transparent fashion. We propose a simple yet direct state manipulation construct for developing side-effecting aspects and devise a systematic monadification scheme to translate the woven code to monadic style purely functional code. Furthermore, we present a static and dynamic semantics of the aspect programs and reason about the correctness of our monadification scheme with respect to them.     

Fine-grained visualization pipelines and lazy functional languages

The pipeline model in visualization has evolved from a conceptual model of data processing into a widely used architecture for implementing visualization systems. In the process, a number of capabilities have been introduced, including streaming of data in chunks, distributed pipelines, and demand-driven processing. Visualization systems have invariably built on stateful programming technologies, and these capabilities have had to be implemented explicitly within the lower layers of a complex hierarchy of services. The good news for developers is that applications built on top of this hierarchy can access these capabilities without concern for how they are implemented. The bad news is that by freezing capabilities into low-level services expressive power and flexibility is lost. In this paper we express visualization systems in a programming language that more naturally supports this kind of processing model. Lazy functional languages support fine-grained demand-driven processing, a natural form of streaming, and pipeline-like function composition for assembling applications. The technology thus appears well suited to visualization applications. Using surface extraction algorithms as illustrative examples, and the lazy functional language Haskell, we argue the benefits of clear and concise expression combined with fine-grained, demand-driven computation. Just as visualization provides insight into data, functional abstraction provides new insight into visualization.     

关于非线性系统的对程性、可达性与可控性*

本文讨论对称及广义对称非线性系统的可达性与可控性。文中证明了如果广义对称系统在一点的邻域可控,那么系统在包含该点群作用轨道的一个开集上是可控的。利用广义对称性还给出了控制律的原则算法。对于对称系统,给出了可控性的充要条件。     

Maximum queue size and hashing with lazy deletion

We answer questions about the distribution of the maximum size of queues and data structures as a function of time. The concept of “maximum” occurs in many issues of resource allocation. We consider several models of growth, including general birth-and-death processes, the M/G/∞ model, and a non-Markovian process (data structure) for processing plane-sweep information in computational geometry, called “hashing with lazy deletion” (HwLD). It has been shown that HwLD is optimal in terms of expected time and dynamic space; our results show that it is also optimal in terms of expectedpreallocated space, up to a constant factor. We take two independent and complementary approaches: first, in Section 2, we use a variety of algebraic and analytical techniques to derive exact formulas for the distribution of the maximum queue size in stationary birth-and-death processes and in a nonstationary model related to file histories. The formulas allow numerical evaluation and some asymptotics. In our second approach, in Section 3, we consider the M/G/∞ model (which includes M/M/∞ as a special case) and use techniques from the analysis of algorithms to get optimal big-oh bounds on the expected maximum queue size and on the expected maximum amount of storage used by HwLD in excess of the optimal amount. The techniques appear extendible to other models, such as M/M/1.     

Maximum queue size and hashing with lazy deletion

We answer questions about the distribution of the maximum size of queues and data structures as a function of time. The concept of maximum occurs in many issues of resource allocation. We consider several models of growth, including general birth-and-death processes, the M/G/ model, and a non-Markovian process (data structure) for processing plane-sweep information in computational geometry, called hashing with lazy deletion (HwLD). It has been shown that HwLD is optimal in terms of expected time and dynamic space; our results show that it is also optimal in terms of expectedpreallocated space, up to a constant factor.We take two independent and complementary approaches: first, in Section 2, we use a variety of algebraic and analytical techniques to derive exact formulas for the distribution of the maximum queue size in stationary birth-and-death processes and in a nonstationary model related to file histories. The formulas allow numerical evaluation and some asymptotics. In our second approach, in Section 3, we consider the M/G/ model (which includes M/M/ as a special case) and use techniques from the analysis of algorithms to get optimal big-oh bounds on the expected maximum queue size and on the expected maximum amount of storage used by HwLD in excess of the optimal amount. The techniques appear extendible to other models, such as M/M/1.Research was also done while the author was at Princeton University, supported in part by a Procter Fellowship.Research was also done while the author was on sabbatical at INRIA in Rocquencourt, France, and at Ecole Normale Supérieure in Paris, France. Support was provided in part by National Science Foundation Research Grant DCR-84-03613, by an NSF Presidential Young Investigator Award with matching funds from an IBM Faculty Development Award and an AT&T research grant, by a Guggenheim Fellowship, and by the Office of Naval Research and the Defense Advanced Research Projects Agency under Contract N00014-83-K-0146 and ARPA Order 6320, Amendment 1.     

Fast video segment retrieval by Sort-Merge feature selection, boundary refinement, and lazy evaluation

We present a fast video retrieval system with three novel characteristics. First, it exploits the methods of machine learning to construct automatically a hierarchy of small subsets of features that are progressively more useful for indexing. These subsets are induced by a new heuristic method called Sort-Merge feature selection, which exploits a novel combination of Fastmap for dimensionality reduction and Mahalanobis distance for likelihood determination. Second, because these induced feature sets form a hierarchy with increasing classification accuracy, video segments can be segmented and categorized simultaneously in a coarse-fine manner that efficiently and progressively detects and refines their temporal boundaries. Third, the feature set hierarchy enables an efficient implementation of query systems by the approach of lazy evaluation, in which new queries are used to refine the retrieval index in real-time. We analyze the performance of these methods, and demonstrate them in the domain of a 75-min instructional video and a 30-min baseball video.     

Direct approach to almost disturbance and almost input-output decoupling

A direct solution to the almost input-output and disturbance decoupling problem is given. The approach is based on a new canonical form for linear systems—which is obtained in a fully constructive way—together with some elementary approximation results. The solution is given in the form of an explicit feedback law, parameterized by a scalar ε. By letting ε go to zero, the accuracy of the resulting approximate solution can be improved to any desired degree.     

The compositional approach to sequential consistency and lazy caching

Summary. The lazy caching protocol proposed by Afek, Brown and Merritt [ABM93], is explained and formally proven correct by means of compositional methods. The protocol is decomposed into four simple protocols, which are of interest on their own. A top level proof is given that is to a large extent independent of the particular model used for the more detailed proofs and allows for a number of generalizations of the original lazy caching protocol. Detailed proofs of safety and liveness properties are given using CSP and trace logic.     

Equivalence Classes,Symmetries and Solutions of Linear Third-order Differential Equations

 The subject of this article are third-order differential equations that may be linearized by a variable change. To this end, at first the equivalence classes of linear equations are completely described. Thereafter it is shown how they combine into symmetry classes that are determined by the various symmetry types. An algorithm is presented allowing it to transform linearizable equations by hyperexponential transformations into linear form from which solutions may be obtained more easily. Several examples are worked out in detail. Received February 18, 2002; revised May 10, 2002 Published online: October 24, 2002     

Symmetries and discriminability in feedforward networkarchitectures

This paper investigates the effects of introducing symmetries into feedforward neural networks in what are termed symmetry networks. This technique allows more efficient training for problems in which we require the output of a network to be invariant under a set of transformations of the input. The particular problem of graph recognition is considered. In this case the network is designed to deliver the same output for isomorphic graphs. This leads to the question of which inputs can be distinguished by such architectures. A theorem characterizing when two inputs can be distinguished by a symmetry network is given. As a consequence, a particular network design is shown to be able to distinguish nonisomorphic graphs if and only if the graph reconstruction conjecture holds.