Search combinators

The ability to model search in a constraint solver can be an essential asset for solving combinatorial problems. However, existing infrastructure for defining search heuristics is often inadequate. Either modeling capabilities are extremely limited or users are faced with a general-purpose programming language whose features are not tailored towards writing search heuristics. As a result, major improvements in performance may remain unexplored. This article introduces search combinators, a lightweight and solver-independent method that bridges the gap between a conceptually simple modeling language for search (high-level, functional and naturally compositional) and an efficient implementation (low-level, imperative and highly non-modular). By allowing the user to define application-tailored search strategies from a small set of primitives, search combinators effectively provide a rich domain-specific language (DSL) for modeling search to the user. Remarkably, this DSL comes at a low implementation cost to the developer of a constraint solver. The article discusses two modular implementation approaches and shows, by empirical evaluation, that search combinators can be implemented without overhead compared to a native, direct implementation in a constraint solver.     

Hard combinators

Hard Interaction systems can be presented as graph relabeling with a handshake mechanism that provide local synchronization. We present a particular one with only four symbols and seven rules that can be used to simulate all the other hard interaction systems.     

Service combinators for Web computing

The World Wide Web is rich in content and services, but access to these resources must be obtained mostly through manual browsers. We would like to be able to write programs that reproduce human browsing behavior, including reactions to slow transmission-rates and failures on many simultaneous links. We thus introduce a concurrent model that directly incorporates the notions of failure and rate of communication, and then describe programming constructs based on this model     

Constructing language processors with algebra combinators

Modular Monadic Semantics (MMS) is a well-known mechanism for structuring modular denotational semantic definitions for programming languages. The principal attraction of MMS is that families of language constructs can be independently specified and later combined in a mix-and-match fashion to create a complete language semantics. This has proved useful for constructing formal, yet executable, semantics when prototyping languages. In this work we demonstrate that MMS has an additional software engineering benefit. In addition to composing semantics for various language constructs, we can use MMS to compose various differing semantics for the same language constructs. This capability allows us to compose and reuse orthogonal language tasks such as type checking and compilation. We describe algebra combinators, the principal vehicle for achieving this reuse, along with a series of applications of the technique for common language processing tasks.     

On the efficiency of categorical combinators as a rewriting system

Categorical combinators form a formal system similar to Curry's combinatory logic. The original system was developed by Curien, inspired by the equivalence of the theories of typed λ-calculus and Cartesian closed categories, as shown by Lambek and Scott. A new system for categorical combinators was introduced by the author. This system uses a more compact notation for the code and needs a smaller set of rewriting rules. The aim of this paper is to analyse these two different rewriting systems for categorical combinators as a basis for implementation of applicative languages, and compare them with the classical approach due to Turner, using combinatory logic.     

The BC-chain method for representing combinators in linear space

Turner’s combinator implementation (1979) of functional programs requires the memory space of size Ω(n ²) in the worst case for translating given lambda expressions of lengthn to combinator graphs. In this paper a new idea named the BC-chain method for transferring actual arguments to variables is presented. We show that the BC-chain method requires onlyO(n) space for the translation. The basic idea is to group together into a single entity a sequence of combinatorsB, B′, C andC′, for a variable, which appear consecutively along a path in the combinator graph. We formulate two reduction algorithms in the new representation. The first algorithm naively simulates the original normal order reduction, while the second algorithm simulates it in constant time per unit operation of the original reduction. Another reduction method is also suggested, and a technique for practical implementation is briefly mentioned.     

严肃遇到傻瓜

导语 “我是一个艺术家，既绘画，也玩黏土、玩偶、雕塑，甚至包装设计也做。虽分属不同领域，但它们都有一个关键点——包装。相信我，包装在当代的重要性已不亚于产品本身，甚至凌驾于它之上。香水就是个好例子，它只是有味道的液态水罢了，现代人之所以买它，很重要的一个原因是为其精美的包装或附送的礼品所诱惑。如今，甚至更有用黄金王冠作包装的香水……而我的工作，就是不用黄金，也能吸引你去购买。”     

The use of combinators in translating a purely functional language to low-level data-flow graphs

FCL is a higher-order functional programming language which consolidates and extends a number of desirable features of existing languages. This paper describes the salient features of FCL and an algorithm for translation to highly parallel data flow graphs. The translation algorithm is based on a set of extended “combinators”. The relationship between functional programming languages and demand-driven or data-driven data flow architectures is established.     

严格线性散播网络编码

针对线性广播和线性散播网络编码在保证节点或节点集解码空间维数方面的不足,提出了一类新的线性网络编码——严格线性散播网络编码.给出了严格线性散播的定义,并设计了相应的构造算法,此种网络编码增强了对网络中任意非源节点集的输入链路上的全局编码核的限制,但其构造所需的有限域的阶并不大于普通的线性散播.此外,还提出了多种转换矩阵的概念,并证明了普通线性散播到严格线性散播的转换矩阵的存在性.结合特殊的数据打包策略,论证了严格线性散播在异构网络中的应用优势:一方面,它能够利用单一网络编码会话实现异构网络中的多速率信息传输;另一方面,它能够为异构网络拓扑结构的扩展提供便利.     

Strict completion of Logic Programs

The paper presents a new approach to the problem of completeness of the SLDNF-resolution. We propose a different reference theory that we call strict completion. This new concept of completion (comp^*(P)) is based on a program transformation that given any program transforms it into a strict one (with the same computational behaviour) and the usual notion of program completion. We consider it a reasonable reference theory to discuss program semantics and completeness results. The standard 2-valued logic is used. The new comp^*(P) is always consistent and the completeness of all allowed programs and goals w.r.t. comp^*(P) is proved.     

Strict interpretations of deterministic pushdown acceptors

Three results are established. The first is that every nondeterministic strict interpretation of a deterministic pushdown acceptor (dpda) has an equivalent, deterministic, strict interpretation. The second is that ifM ₁ andM ₂ are two compatible strict interpretations of the dpdaM, then there exist deterministic strict interpretationsM andM such thatL(M ) =L(M ₁)L(M ₂) andL(M ) =L(M ₁)L(M ₂). The third states that there is no dpda whose strict interpretations yield all the deterministic context-free languages.This author was supported in part by the National Science Foundation under Grant MCS-77-22323.     

严格正实引理和严格界实引理的一般描述--非最小实现的情形

本文对于非最小实现的情形研究了严格正实引理和严格界实引理。采用H_∞范数给出了二者的一般描述。其结果可以使人们更清楚地了解严格正实系统和严格界实系统的结构。     

Strict Lyapunov functions for time-varying systems

Uniformly asymptotically stable periodic time-varying systems for which is known a Lyapunov function with a derivative along the trajectories non-positive and negative definite in the state variable on non-empty open intervals of the time are considered. For these systems, strict Lyapunov functions are constructed.     

Strict pattern matching under non-overlapping condition

Pattern matching (or string matching) is an essential task in computer science, especially in sequential pattern mining, since pattern matching methods can be used to calculate the support (or the number of occurrences) of a pattern and then to determine whether the pattern is frequent or not. A state-of-the-art sequential pattern mining with gap constraints (or flexible wildcards) uses the number of non-overlapping occurrences to denote the frequency of a pattern. Non-overlapping means that any two occurrences cannot use the same character of the sequence at the same position of the pattern. In this paper, we investigate strict pattern matching under the non-overlapping condition. We show that the problem is in P at first. Then we propose an algorithm, called NETLAP-Best, which uses Nettree structure. NETLAP-Best transforms the pattern matching problem into a Nettree and iterates to find the rightmost root-leaf path, to prune the useless nodes in the Nettree after removing the rightmost root-leaf path. We show that NETLAP-Best is a complete algorithm and analyse the time and space complexities of the algorithm. Extensive experimental results demonstrate the correctness and efficiency of NETLAP-Best.