Fast Theta-Subsumption with Constraint Satisfaction Algorithms

Relational learning and Inductive Logic Programming (ILP) commonly use as covering test the -subsumption test defined by Plotkin. Based on a reformulation of -subsumption as a binary constraint satisfaction problem, this paper describes a novel -subsumption algorithm named Django,¹ which combines well-known CSP procedures and -subsumption-specific data structures. Django is validated using the stochastic complexity framework developed in CSPs, and imported in ILP by Giordana et Saitta. Principled and extensive experiments within this framework show that Django improves on earlier -subsumption algorithms by several orders of magnitude, and that different procedures are better at different regions of the stochastic complexity landscape. These experiments allow for building a control layer over Django, termed Meta-Django, which determines the best procedures to use depending on the order parameters of the -subsumption problem instance. The performance gains and good scalability of Django and Meta-Django are finally demonstrated on a real-world ILP task (emulating the search for frequent clauses in the mutagenesis domain) though the smaller size of the problems results in smaller gain factors (ranging from 2.5 to 30).     

On Quantum-Like Probabilistic Structure of Mental Information

We describe methodology of cognitive experiments (based on interference of probabilities for mental observables) which could verify quantum-like structure of mental information, namely, interference of probabilities for incompatible observables. In principle, such experiments can be performed in psychology, cognitive, and social sciences. In fact, the general contextual probability theory predicts not only quantum-like trigonometric (cos ) interference of probabilities, but also hyperbolic (cosh ) interference of probabilities (as well as hyper-trigonometric). In principle, statistical data obtained in experiments with cognitive systems can produce hyperbolic (cosh ) interference of probabilities. We introduce a wave function of (e.g., human) population. In general, we should not reject the possibility that cognitive functioning is neither quantum nor classical. We discuss the structure of state spaces for cognitive systems.     

Statistical Properties of a Time-Series-Complexity Measure Applied to Stock Returns

We review a complexity measure () and its statistical properties, then apply it to four stock returns. Theta is a ratio of two correlation integral estimates, one taken before and one after shuffling the series to investigate. For random processes 1 while approaches zero for data with low complexity. Sixteen artificially generated series with different dynamical characteristics – each represented by three sample sizes – were employed to investigate 's statistical properties. Its distribution approaches normality as the sample size is increased. When applied to stock returns, those computed at every price change proved less complex than lower frequency one- and five-minute returns, implying that information is being lost by increasingly less frequent sampling.     

Visibility,occlusion, and the aspect graph

This chapter studies the ways in which the topology of the image of a polyhedron changes with changing viewpoint. We catalog the ways that the topological appearance, or aspect, can change. This enables us to find maximal regions of viewpoints of the same aspect. We use these techniques to construct the viewpoint space partition (VSP), a partition of viewpoint space into maximal regions of constant aspect, and its dual, the aspect graph. Here, we present tight bounds on the maximum size of the VSP and the aspect graph and give algorithms for their construction, first in the convex case and then in the general case. In particular, we give bounds on the maximum size of (n ²) and (n ⁶) under an orthographic projection viewing model and of (n ³) and (n ⁹) under a perspective viewing model. The algorithms make use of a new representation of the appearance of polyhedra from all viewpoints, called the aspect representation or asp. We believe that this representation is one of the significant contributions of this paper.This work was supported in part by the NSF under grants DCR-8520870 and IRI-8802436.     

A predicate transformer for the progress property ‘to-always’

The temporal property to-always has been proposed for specifying progress properties of concurrent programs. Although the to-always properties are a subset of the leads-to properties for a given program, to-always has more convenient proof rules and in some cases more accurately describes the desired system behavior. In this paper, we give a predicate transformerwta, derive some of its properties, and use it to define to-always. Proof rules for to-always are derived from the properties ofwta. We conclude by briefly describing two application areas, nondeterministic data flow networks and self-stabilizing systems where to-always properties are useful.     

On improving the accuracy of the Hough transform

The subject of this paper is very high precision parameter estimation using the Hough transform. We identify various problems that adversely affect the accuracy of the Hough transform and propose a new, high accuracy method that consists of smoothing the Hough arrayH(, ) prior to finding its peak location and interpolating about this peak to find a final sub-bucket peak. We also investigate the effect of the quantizations and ofH(, ) on the final accuracy. We consider in detail the case of finding the parameters of a straight line. Using extensive simulation and a number of experiments on calibrated targets, we compare the accuracy of the method with results from the standard Hough transform method of taking the quantized peak coordinates, with results from taking the centroid about the peak, and with results from least squares fitting. The largest set of simulations cover a range of line lengths and Gaussian zero-mean noise distributions. This noise model is ideally suited to the least squares method, and yet the results from the method compare favorably. Compared to the centroid or to standard Hough estimates, the results are significantly better—for the standard Hough estimates by a factor of 3 to 10. In addition, the simulations show that as and are increased (i.e., made coarser), the sub-bucket interpolation maintains a high level of accuracy. Experiments using real images are also described, and in these the new method has errors smaller by a factor of 3 or more compared to the standard Hough estimates.     

Optimal algorithms for symmetry detection in two and three dimensions

Exact algorithms for detecting all rotational and involutional symmetries in point sets, polygons and polyhedra are described. The time complexities of the algorithms are shown to be (n) for polygons and (n logn) for two- and three-dimensional point sets. (n logn) time is also required for general polyhedra, but for polyhedra with connected, planar surface graphs (n) time can be achieved. All algorithms are optimal in time complexity, within constants.     

Formula databases for high-performance resolution/paramodulation systems

Over the past 25 years, researchers have written numerous deduction systems based on resolution and paramodulation. Of these systems, very few have been capable of generating and maintaining aformula database containing more than just a few thousand clauses. These few systems were used to explore mechanisms for rapidly extracting limited subsets of relevant clauses. We have developed a simple, powerful deduction system that reflects some of the best of the ideas that have emerged from the research. This paper describes that deduction system and casts the idea in a form that makes them easily accessible to researchers wishing to write their own high-performance systems.This work was partially supported by National Science Foundation grant CCR-8810947 and by the Office of Scientific Computing, U.S. Department of Energy under contract W-31-109-Eng-38.     

Multistrategy Theory Revision: Induction and Abduction in INTHELEX

This paper presents an integration of induction and abduction in INTHELEX, a prototypical incremental learning system. The refinement operators perform theory revision in a search space whose structure is induced by a quasi-ordering, derived from Plotkin's -subsumption, compliant with the principle of Object Identity. A reduced complexity of the refinement is obtained, without a major loss in terms of expressiveness. These inductive operators have been proven ideal for this search space. Abduction supports the inductive operators in the completion of the incoming new observations. Experiments have been run on a standard dataset about family trees as well as in the domain of document classification to prove the effectiveness of such multistrategy incremental learning system with respect to a classical batch algorithm.     

Representations of numbers and finite automata

Numeration systems, the basis of which is defined by a linear recurrence with integer coefficients, are considered. We give conditions on the recurrence under which the function of normalization which transforms any representation of an integer into the normal one—obtained by the usual algorithm—can be realized by a finite automaton. Addition is a particular case of normalization. The same questions are discussed for the representation of real numbers in basis , where is a real number > 1, in connection with symbolic dynamics. In particular it is shown that if is a Pisot number, then the normalization and the addition in basis are computable by a finite automaton.This work has been supported by the PRC Mathématiques et Informatique.     

Extremal Relations between Additive Loss Functions and the Kolmogorov Complexity

Conditions are presented under which the maximum of the Kolmogorov complexity (algorithmic entropy) K(₁... _N ) is attained, given the cost f( _i ) of a message ₁... _N . Various extremal relations between the message cost and the Kolmogorov complexity are also considered; in particular, the minimization problem for the function f( _i ) – K(₁... _N ) is studied. Here, is a parameter, called the temperature by analogy with thermodynamics. We also study domains of small variation of this function.     

Reduction and unification in lambda calculi with a general notion of subtype

Reduction, equality, and unification are studied for a family of simply typed -calculi with subtypes. The subtype relation is required to relate base types only to base types and to satisfy some order-theoretic conditions. Constants are required to have a least type, that is, no overloading. We define the usual and a subtype-dependent -reduction. These are related to a typed equality relation and shown to be confluent in a certain sense. We present a generic algorithm for preunification modulo -conversion and an arbitrary subtype relation. Furthermore it is shown that unification with respect to any subtype relation is universal.     

Thermal Mass and Thermal Inertia in Fluids — A Comparison of Hypotheses

Thermal inertia and thermal mass are concepts that offer means to describe transport of heat in nonequilibrium fluids. However there are options regarding how to separate the part of the total flow that caries entropy from the "mechanical", nonentropy-bearing part. Some hypotheses are examined and compared for constructing such a field theory of thermal mass in the energy representation. A global intrinsic symmetry and a finite thermal momentum imply that any formulation which hypothesizes a constant ratio of thermal mass to the entropy must tie the thermal mass to the so-called bare mass of particles, to preserve the global conservation of matter. However, in any formulation consistent with the Grad-Boltzmann theory, where must be variable, the thermal mass behaves as a separate variable governed by the entropy and the second law. Nonetheless, in this case has a reasonably broad plateau of values within which entropy is a measure of the thermal mass associated with changes of state. Nonlinear transformations linking usual thermodynamic variables with those of the thermal mass frame preserve the components of the tensor of matter, including Nöther's energy and pressure. A formula is given for the fraction of the observed mass assignable as thermal mass, in accordance with Grad's solution of the Boltzmann equation.     

Computability by finite automata and pisot bases

We prove that the function of normalization in base , which maps any -representation of a real number onto its -development, obtained by a greedy algorithm, is a function computable by a finite automaton over any alphabet if and only if is a Pisot number.Christiane Frougny was supported in part by the PRC Mathématiques et Informatique of the Ministère de la Recherche et de l'Espace.     

Layup optimization against buckling of shear panels

The object of the study was to optimize the shear buckling load of laminated composite plates. The laminates lacked coupling between bending and extension (B _ij=0) but had otherwise arbitrary selection of the ply angle variation through the thickness. The plates were rectangular and either simply supported or clamped on all edges. For orthotropic plates, it was seen that there is only one parameter necessary for finding the optimal design for different materials and plate aspect ratios. This parameter can be interpreted as the layup angle in a (+/–) orthotropic laminate. When bendingtwisting coupling is present, the buckling strength depends on the direction of the applied load. A laminate with non-zero bending-twisting coupling stiffnesses can be described with four lamination parameters. The allowable region of these parameters was investigated, and an optimization of the buckling load within this region was performed. It was seen that even this is a one parameter problem. This parameter can be interpreted as the layup anlge in an off-axis unidirectional laminate ().Notations A _ij in-plane stiffnesses of anisotropic plates, Tsai and Hahn (1980) - B _ij coupling stiffnesses of anisotropic plates - D _ij bending stiffnesses of anisotropic plates - D _ij ^* normalized bending stiffnesses - a, b, h length, width and thickness of the plate - x, y in-plane coordinates - z through-the-thickness coordinate - z ^* normalized through-the-thickness coordinate - w (x, y) out-of-plane deformation - N _xy shear buckling load - W ₁ ^* toW ₄ ^* lamination parameters - U ₁ toU ₅ linear combinations of the on-axis moduli - (z) layup angle - f _k functional of(z)     

A Delay-Averaged Logistic Model

For the equation x(t) = x(t) (1-(1/) _t-- ^t- x(u)du), > 0, > 0, > 0, conditions for the stability of a nonzero stationary solution under small perturbations are determined.     

Pushing Convertible Constraints in Frequent Itemset Mining

Recent work has highlighted the importance of the constraint-based mining paradigm in the context of frequent itemsets, associations, correlations, sequential patterns, and many other interesting patterns in large databases. Constraint pushing techniques have been developed for mining frequent patterns and associations with antimonotonic, monotonic, and succinct constraints. In this paper, we study constraints which cannot be handled with existing theory and techniques in frequent pattern mining. For example, avg(S)v, median(S)v, sum(S)v (S can contain items of arbitrary values, {<, <, , } and v is a real number.) are customarily regarded as tough constraints in that they cannot be pushed inside an algorithm such as Apriori. We develop a notion of convertible constraints and systematically analyze, classify, and characterize this class. We also develop techniques which enable them to be readily pushed deep inside the recently developed FP-growth algorithm for frequent itemset mining. Results from our detailed experiments show the effectiveness of the techniques developed.     

Design sensitivity analysis of nonlinear dynamic response of structural and mechanical systems

This paper describes a unified variational theory for design sensitivity analysis of nonlinear dynamic response of structural and mechanical systems for shape, nonshape, material and mechanical properties selection, as well as control problems. The concept of an adjoint system, the principle of virtual work and a Lagrangian-Eulerian formulation to describe the deformations and the design variations are used to develop a unified view point. A general formula for design sensitivity analysis is derived and interpreted for usual performance functionals. Analytical examples are utilized to demonstrate the use of the theory and give insights for application to more complex problems that must be treated numerically.Derivatives The comma notation for partial derivatives is used, i.e. G,_u = G/u. An upper dot represents material time derivative, i.e. ü = ²u/t². A prime implies derivative with respect to the time measured in the reference time-domain, i.e. u = du/d.     

Comparative complexity of the representation of languages by probabilistic automata

We analyze the effect of the degree of isolation of a cut point on the number of states P(U, ) of a probabilistic automaton representing the language U. We give an example of a language Uⁿ consisting of words of length n such that there exist numbers < for which P(Uⁿ, )/P(Uⁿ, )0 as n.Translated from Kibernetika, No. 3, pp. 21–25, May–June, 1989.     

The π-Calculus in Direct Style

We introduce a calculus which is a direct extension of both the and the calculi. We give a simple type system for it, that encompasses both Curry's type inference for the -calculus, and Milner's sorting for the -calculus as particular cases of typing. We observe that the various continuation passing style transformations for -terms, written in our calculus, actually correspond to encodings already given by Milner and others for evaluation strategies of -terms into the -calculus. Furthermore, the associated sortings correspond to well-known double negation translations on types. Finally we provide an adequate CPS transform from our calculus to the -calculus. This shows that the latter may be regarded as an assembly language, while our calculus seems to provide a better programming notation for higher-order concurrency. We conclude by discussing some alternative design decisions.