An argument for simple COMA

We present design details and some initial performance results of a novel scalable shared memory multiprocessor architecture. This architecture features the automatic data migration and replication capabilities of cache-only memory architecture (COMA) machines, without the accompanying hardware complexity. A software layer manages cache space allocation at a page-granularity — similarly to distributed virtual shared memory (DVSM) systems —leaving simpler hardware to maintain shared memory coherence at a cache line granularity.

By reducing the hardware complexity, the machine cost and development time are reduced. We call the resulting hybrid hardware and software multiprocessor architecture Simple COMA. Preliminary results indicate that the performance of Simple COMA is comparable to that of more complex contemporary all-hardware designs.     

A generalized setting for fixpoint theory

The mathematical semantics of programming languages is based largely on certain algebraic structures, usually complete lattices or complete partial orders. The usefulness of these structures is based on the existence of fixpoints of functions defined on the structures, and the fact that these classes of structures are closed under such operations as taking cross-products, disjoint unions or function spaces.This paper proposes more general versions of these structures which still retain the above desirable properties. Thus the techniques of mathematical semantics should become applicable in a wider context than heretofore.One important application is given, which in fact motivated the whole development. It is shown that in the generalized setting the existence of unique minimal solutions for recursive definitions of functions are guaranteed without having to resort to informal arguments of any sort.     

A compact fixpoint semantics for term rewriting systems

This work is motivated by the fact that a “compact” semantics for term rewriting systems, which is essential for the development of effective semantics-based program manipulation tools (e.g. automatic program analyzers and debuggers), does not exist. The big-step rewriting semantics that is most commonly considered in functional programming is the set of values/normal forms that the program is able to compute for any input expression. Such a big-step semantics is unnecessarily oversized, as it contains many “semantically useless” elements that can be retrieved from a smaller set of terms. Therefore, in this article, we present a compressed, goal-independent collecting fixpoint semantics that contains the smallest set of terms that are sufficient to describe, by semantic closure, all possible rewritings. We prove soundness and completeness under ascertained conditions. The compactness of the semantics makes it suitable for applications. Actually, our semantics can be finite whereas the big-step semantics is generally not, and even when both semantics are infinite, the fixpoint computation of our semantics produces fewer elements at each step. To support this claim we report several experiments performed with a prototypical implementation.     

A fixpoint semantics of Horn sentences based on substitution sets

The formal semantics of a given Horn sentence is usually defined as a set of ground atoms, which is really the minimal Herbrand interpretation of the Horn sentence, by both model-theoretic and fixpoint approaches. In the present paper, we propose another denotational semantics of a Horn sentence, denoting the set of substitutions with which atoms are derivable by unit deduction from the Horn sentence to get a direct correspondence between the semantics of the Horn sentence and the answer set concerned with its computation, and give denotational semantics even when the Horn sentence is unsatisfiable. In accordance with the unit deductions from a Horn sentence, we define a continuous function from a direct product of powersets of a substitution set to itself, and regard the least fixpoint of the function as the semantics, which can provide the answer set for computations of the Horn sentence.     

A simple and robust three-dimensional cracking-particle method without enrichment

A new robust and efficient approach for modeling discrete cracks in meshfree methods is described. The method is motivated by the cracking-particle method (Rabczuk T., Belytschko T., International Journal for Numerical Methods in Engineering, 2004) where the crack is modeled by a set of cracked segments. However, in contrast to the above mentioned paper, we do not introduce additional unknowns in the variational formulation to capture the displacement discontinuity. Instead, the crack is modeled by splitting particles located on opposite sides of the associated crack segments and we make use of the visibility method in order to describe the crack kinematics. We apply this method to several two- and three-dimensional problems in statics and dynamics and show through several numerical examples that the method does not show any “mesh” orientation bias.     

Document skew estimation without angle range restriction

The existing skew estimation techniques usually assume that the input image is of high resolution and that the detectable angle range is limited. We present a more generic solution for this task that overcomes these restrictions. Our method is based on determination of the first eigenvector of the data covariance matrix. The solution comprises image resolution reduction, connected component analysis, component classification using a fuzzy approach, and skew estimation. Experiments on a large set of various document images and performance comparison with two Hough transform-based methods show a good accuracy and robustness for our method. Received October 10, 1998 / Revised version September 9, 1999     

A continuity property for the filter associated to Hilbert-space valued systems

The purpose of this paper is to study the continuity with respect to the trajectory of the observation process for the filter associated to nonlinear filtering problems when both the signal and the observation processes evolve on real separable Hilbert spaces.     

Acceleration of the abstract fixpoint computation in numerical program analysis

Static analysis by abstract interpretation aims at automatically proving properties of computer programs, by computing invariants that over-approximate the program behaviors. These invariants are defined as the least fixpoint of a system of semantic equations and are most often computed using the Kleene iteration. This computation may not terminate so specific solutions were proposed to deal with this issue. Most of the proposed methods sacrifice the precision of the solution to guarantee the termination of the computation in a finite number of iterations. In this article, we define a new method which allows to obtain a precise fixpoint in a short time. The main idea is to use numerical methods designed for accelerating the convergence of numerical sequences. These methods were primarily designed to transform a convergent, real valued sequence into another sequence that converges faster to the same limit. In this article, we show how they can be integrated into the Kleene iteration in order to improve the fixpoint computation in the abstract interpretation framework. An interesting feature of our method is that it remains very close to the Kleene iteration and thus can be easily implemented in existing static analyzers. We describe a general framework and its application to two numerical abstract domains: the interval domain and the octagon domain. Experimental results show that the number of iterations and the time needed to compute the fixpoint undergo a significant reduction compared to the Kleene iteration, while its precision is preserved.     

A simple alternative to the Barbalat lemma

This paper gives a simple proof of the property that if a signal is square integrable and has a bounded derivative, then the signal converges to zero asymptotically     

A reinforcement learning approach to improve the argument selection effectiveness in argumentation-based negotiation

Deciding what argument to utter during a negotiation is a key part of the strategy to reach an expected agreement. An agent, which is arguing during a negotiation, must decide what arguments are the best to persuade the opponent. In fact, in each negotiation step, the agent must select an argument from a set of candidate arguments by applying some selection policy. By following this policy, the agent observes some factors of the negotiation context (for instance, trust in the opponent and expected utility of the negotiated agreement). Usually, argument selection policies are defined statically. However, as the negotiation context varies from a negotiation to another, defining a static selection policy is not useful. Therefore, the agent should modify its selection policy in order to adapt it to the different negotiation contexts as the agent gains experience. In this paper, we present a reinforcement learning approach that allows the agent to improve the argument selection effectiveness by updating the argument selection policy. To carry out this goal, the argument selection mechanism is represented as a reinforcement learning model. We tested this approach in a multiagent system, in a stationary as well as in a dynamic environment. We obtained promising results in both.     

A new fixpoint semantics for general logic programs compared with the well-founded and the stable model semantics

We study a new fixpoint semantics for logic programs with negation. Our construction is intermediate between Van Gelder’s well-founded model and Gelfond and Lifschitz’s stable model semantics. We show first that the stable models of a logic programP are exactly the well-supported models ofP, i.e. the supported models with loop-free finite justifications. Then we associate to any logic programP a non-monotonic operator over the semilattice of justified interpretations, and we define in an abstract form its ordinal powers. We show that the fixpoints of this operator are the stable models ofP, and that its ordinal powers after some ordinala are extensions of the well-founded partial model ofP. In particular ifP has a well-founded model then that canonical model is also an ordinal power and the unique fixpoint of our operator. We show with examples of logic programs which have a unique stable model but no well-founded model that the converse is false. We relate also our work to Doyle’s truth maintenance system and some implementations of rule-based expert systems.     

一种不受初始权值向量影响的MCA学习算法

最小主元分析(Minor Component Analysis,MCA)类自适应总体最小二乘算法易受初始权值向量的影响而无法收敛。为解决这一问题,提出了一种不受初始权值向量影响的MCA学习算法,推导出了该算法的收敛条件与最终收敛域,并通过计算机仿真验证了该算法的正确性。     

基于量子遗传算法的非线性无约束优化方法

量子遗传算法(QGA)是量子计算和遗传算法相结合的产物,量子遗传算法将量子比特和量子旋转门表示引入到遗传算法中,具有比遗传算法更好的搜索效率和收敛性。非线性无约束优化是典型的工程应用问题,而复杂非线性函数的优化结果往往不能令人满意,如陷入局部最优等。利用量子遗传算法强大的搜索能力,可以很好的解决复杂非线性函数的无约束优化问题,实验表明量子遗传算法在该类问题中的有效性和可行性。     

A simple approach to solving the Diophantine equation

Based on the state-space concepts, a simple approach to finding all polynomial matrix solutions of the Diophantine equation is proposed. The procedure presented is very simple in comparison to earlier ones. Unlike earlier ones, it is not necessary to solve any equation. Only two constant matrices which could be selected at random are required. All solutions are expressed in an explicit formula form     

A new approach to Lipschitz continuity in state constrained optimal control

For a linear-quadratic state constrained optimal control problem, it is proved in [11] that under an independence condition for the active constraints, the optimal control is Lipschitz continuous. We now give a new proof of this result based on an analysis of the Euler discretization given in [9]. There we exploit the Lipschitz continuity of the control to estimate the error in the Euler discretization. Here we show that the theory developed for the Euler discretization can be used to derive the Lipschitz continuity of the optimal control.     

A simple approach to system modeling

This paper describes an approach to system modeling based on heuristic mean value analysis. The virtues of the approach are conceptual simplicity and computational efficiency. The approach can be applied to a large variety of systems, and can handle features such as resource constraints, tightly and loosely coupled multiprocessors, distributed processing, and certain types of CPU priorities. Extensive validation results are presented, including truly predictive situations. The paper is intended primarily as a tutorial on the method and its applications, rather than as an exposition of research results.     

A simple digital to resolver converter

A technique is described by which a digital representation of an angle is converted into a pair of ac voltages suitable for exciting a synchro or resolver, which may be used as the feedback element of a control system. The technique is quite economical of hardware, is capable of an arbitrary degree of accuracy, and is adaptable to almost any radix digital input signal. The simplicity and economy of the method depends on digitally generating two voltages that are functions of the digitally designated angle, but are not proportional to the sine and cosine per se. These functions are chosen in such a way that their ratio approximates the tangent of the designed angle with an arbitrarily small error. An example of the technique and some experimental results are given.     

A computer algorithm to determine the recognition site of restriction enzymes

A new algorithm is proposed to determine the type-II restriction endonucleases' recognition site knowing the digested DNA sequence and fragment lengths in an actual case. The algorithm is implemented for the Commodore 64 microcomputer.