From Lucid to TransLucid: Iteration, Dataflow, Intensional and Cartesian Programming

We present the development of the Lucid language from the Original Lucid of the mid-1970s to the TransLucid of today. Each successive version of the language has been a generalisation of previous languages, but with a further understanding of the problems at hand. The Original Lucid (1976), originally designed for purposes of formal verification, was used to formalise the iteration in while-loop programs. The pLucid language (1982) was used to describe dataflow networks. Indexical Lucid (1987) was introduced for intensional programming, in which the semantics of a variable was understood as a function from a universe of possible worlds to ordinary values. With TransLucid, and the use of contexts as firstclass values, programming can be understood in a Cartesian framework.      

A Math Query Language with an Expanded Set of Wildcards

Math search is a new area of research with many enabling technologies but also many challenges. Some of the enabling technologies include XML, XPath, XQuery, and MathML. Some of the challenges involve enabling search systems to recognize mathematical symbols and structures. Several math search projects have made considerable progress in meeting those challenges. One of the remaining challenges is the creation and implementation of a math query language that enables the general users to express their information needs intuitively yet precisely. This paper will present such a language and detail its features. The new math query language offers an alternative way to describe mathematical expressions that is more consistent and less ambiguous than conventional mathematical notation. In addition, the language goes beyond the Boolean and proximity query syntax found in standard text search systems. It defines a powerful set of wildcards that are deemed important for math search. These wildcards provide for more precise structural search and multi-levels of abstractions. Three new sets of wildcards and their implementation details will also be discussed.      

Integrating Lucid’s Declarative Dataflow Paradigm into Object-Orientation

The dataflow language Lucid applies concepts from intensional logic to declarative ISWIM expressions which are intensionalised relative to the dimension of time, thus introducing the notion of an expression’s history. Lucian, a language derived from Lucid, embeds dataflow into object-orientation allowing the intensionalisation of objects. Lucian introduces the notion of a declarative intensional object as the history of an object’s transformations. This paper discusses the embedding relationships and semantics of conjoining the dataflow and object-oriented paradigms to provide the language Lucian for defining intensional objects.      

Lempel–Ziv Factorization Using Less Time & Space

For 30 years the Lempel–Ziv factorization LZ _x of a string x = x[1..n] has been a fundamental data structure of string processing, especially valuable for string compression and for computing all the repetitions (runs) in x. Traditionally the standard method for computing LZ _x was based on Θ(n)-time (or, depending on the measure used, O(n log n)-time) processing of the suffix tree ST _x of x. Recently Abouelhoda et al. proposed an efficient Lempel–Ziv factorization algorithm based on an “enhanced” suffix array – that is, a suffix array SA _x together with supporting data structures, principally an “interval tree”. In this paper we introduce a collection of fast space-efficient algorithms for LZ factorization, also based on suffix arrays, that in theory as well as in many practical circumstances are superior to those previously proposed; one family out of this collection achieves true Θ(n)-time alphabet-independent processing in the worst case by avoiding tree structures altogether. The work of the first and third authors was supported in part by grants from the Natural Sciences & Engineering Research Council of Canada.     

Smoluchowski-Kramers approximation for a general class of SPDEs

We prove that the so-called Smoluchowski-Kramers approximation holds for a class of partial differential equations perturbed by a non-Gaussian noisy term. Namely, we show that the solution of the one-dimensional semi-linear stochastic damped wave equations , u(0) = u₀, u_t (0) = v₀, endowed with Dirichlet boundary conditions, converges as the parameter μ goes to zero to the solution of the semi-linear stochastic heat equation , u(0) = u₀, endowed with Dirichlet boundary conditions. Dedicated to Giuseppe Da Prato on the occasion of his 70th birthday     

Efficient Intensional Implementation for Lazy Functional Languages

The intensional transformation is a technique that can be used in order to eliminate higher-order functions from a functional program by introducing appropriate context-manipulation operators. The transformation can be applied to a significant class of higher-order programs and results in equivalent zero-order intensional programs that can be executed in a simple demand-driven way. Despite its simplicity, the transformation has never been seriously evaluated with respect to its efficiency and potential. Certain simple implementations of the technique have been performed, but questions regarding the merits of the method have remained inconclusive. In this paper we demonstrate that the transformation can be efficiently implemented by using what we call lazy activation records, namely activation records in which some entries are filled on-demand. An evaluation of our implementation demonstrates that the technique outperforms some of the most well-known functional programming systems, for the class of programs that can be transformed. This work has been partially supported by the University of Athens under the project “Kapodistrias” (grant no. 70/4/5827).     

The distribution of values of the enumerating function of finite, non-isomorphic abelian groups in short intervals

The result is: The distribution of values of the enumerating function of finite, non-isomorphic abelian groups in short intervals is similar to the distribution of square-free numbers in short intervals. Moreover, a new estimate of the error term in the corresponding asymptotic formula is given, which improves former estimates.      

A note on primes in short intervals

This paper is concerned with the number of primes in short intervals. We prove that , for θ > 1/2, with the assumption of an heuristic hypothesis weaker than the Lindel?f hypothesis. Received: 8 October 2007, Revised: 14 April 2008     

On values of n 2 + 1 free of large prime factors

Let P ⁺(m) denote the greatest prime factor of the positive integer m. Improving and simplifying work of Dartyge [3] we show that

Minimal Order Semihypergroups of Type U on the Right

We study existence and possible uniqueness of special semihypergroups of type U on the right. In particular, we prove that there exists a unique proper semihypergroup of this kind having order 6, apart of isomorphisms; the least order for a hypergroup of type U on the right to have a stable part which is not a subhypergroup is 9; and the minimal cardinality of a proper semihypergroup of that kind whose heart and derived semihypergroup are proper and nontrivial is 12. Contextually, we analyze properties of the kernel of homomorphisms g : H ↦ G, where H is a finite semihypergroup of type U on the right and G is a group. In this way, we obtain results that are immediately applicable both to the heart and to the derived of such semihypergroups.      

Organization, Transformation, and Propagation of Mathematical Knowledge in Ωmega

Mathematical assistance systems and proof assistance systems in general have traditionally been developed as large, monolithic systems which are often hard to maintain and extend. In this article we propose a component network architecture as a means to design and implement such systems. Under this view a mathematical assistance system is an integrated knowledge-based system composed as a network of individual, specialized components. These components manipulate and mutually exchange different kinds of mathematical knowledge encoded within different document formats. Consequently, several units of mathematical knowledge coexist throughout the system within these components and this knowledge changes non-monotonically over time. Our approach has resulted in a lean and maintainable system code and makes the system open for extensions. Moreover, it naturally decomposes the global and complex reasoning and truth maintenance task into local reasoning and truth maintenance tasks inside the system components. The interplay between neighboring components in the network is thereby realized by nonmonotonic updates over agreed interface representations encoding different kinds of mathematical knowledge. This work has been funded by the DFG Collaborative Research Center on Resource-Adaptive Cognitive Processes, SFB 378, and was supported by grants from Studienstiftung des Deutschen Volkes e.V .     

A Tutorial on Computational Cluster Analysis with Applications to Pattern Discovery in Microarray Data

Microarrays offer unprecedented possibilities for the so-called omic, e.g., genomic and proteomic, research. However, they are also quite challenging data to analyze. The aim of this paper is to provide a short tutorial on the most common approaches used for pattern discovery and cluster analysis as they are currently used for microarrays, in the hope to bring the attention of the Algorithmic Community on novel aspects of classification and data analysis that deserve attention and have potential for high reward. R. Giancarlo is partially supported by Italian MIUR grants PRIN “Metodi Combinatori ed Algoritmici per la Scoperta di Patterns in Biosequenze” and FIRB “Bioinformatica per la Genomica e la Proteomica” and Italy-Israel FIRB Project “Pattern Discovery Algorithms in Discrete Structures, with Applications to Bioinformatics”. D. Scaturro is supported by a MIUR Fellowship in the Italy-Israel FIRB Project “Pattern Discovery Algorithms in Discrete Structures, with Applications to Bioinformatics”.     

Scattering of an incident acoustic wave by an elastic sphere in a shallow water

The scattering of acoustic waves by an elastic sphere in a shallow ocean wave guide is investigated taking into account the shear waves which can exist in addition to compressional waves in scatterers of solid material. Expressions for the scattered waves are given. Numerical values for a quantity called the farfield form function for various depth are presented in graphical forms.      

Néron Models and Formal Groups

We show that formal groups can be used to simplify the construction of Néron models. Also we give a new proof of the stable reduction theorem for abelian varieties. Received: September 2007     

On approximate solutions to the first initial boundary value problem for the m-Hessian evolution equations

We adapt to degenerate m-Hessian evolution equations the notion of m-approximate solutions introduced by N. Trudinger for m-Hessian elliptic equations, and we present close to necessary and sufficient conditions guaranteeing the existence and uniqueness of such solutions for the first initial boundary value problem. Dedicated to Professor Felix Browder     

On the Yao-Yao partition theorem

The Yao-Yao partition theorem states that for any probability measure μ on having a density which is continuous and bounded away from 0, it is possible to partition into 2ⁿ regions of equal measure for μ in such a way that every affine hyperplane of avoids at least one of the regions. We give a constructive proof of this result and extend it to slightly more general measures. Received: 21 August 2008     

On orbits of automorphism groups II

Let G be a finite group, let A be a group of automorphisms of G and let C_G(A) denote the subgroup of fixed points of A in G. If the order of C_G(A) is coprime to the number of orbits of A in G, then C_G(A) is contained in the autocommutator subgroup [G, A]. The notion of class-avoiding automorphism is used to extend theorems of J. Thompson and P. Rowley. Received: 3 November 2008, Revised: 1 December 2008