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.      

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.      

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.     

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).     

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     

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”.     

Blossom V: a new implementation of a minimum cost perfect matching algorithm

We describe a new implementation of the Edmonds’s algorithm for computing a perfect matching of minimum cost, to which we refer as Blossom V. A key feature of our implementation is a combination of two ideas that were shown to be effective for this problem: the “variable dual updates” approach of Cook and Rohe (INFORMS J Comput 11(2):138–148, 1999) and the use of priority queues. We achieve this by maintaining an auxiliary graph whose nodes correspond to alternating trees in the Edmonds’s algorithm. While our use of priority queues does not improve the worst-case complexity, it appears to lead to an efficient technique. In the majority of our tests Blossom V outperformed previous implementations of Cook and Rohe (INFORMS J Comput 11(2):138–148, 1999) and Mehlhorn and Schäfer (J Algorithmics Exp (JEA) 7:4, 2002), sometimes by an order of magnitude. We also show that for large VLSI instances it is beneficial to update duals by solving a linear program, contrary to a conjecture by Cook and Rohe.     

A Class of Integral Operators on the Unit Ball of \mathbb{C}^{n}

For real parameters a, b, c, and t, where c is not a nonpositive integer, we determine exactly when the integral operator

Maximal ℓ-Frattini quotients of ℓ-Poincaré duality groups of dimension 2

Any morphism of profinite groups has maximal ℓ-Frattini quotients

Certain invariants of extension algebras of C({\mathbb{T}}^{2})

In this paper, we compute certain invariants of extension algebras of the torus algebra by , where is the C*-algebra of compact operators on an infinite dimensional separable Hilbert space H. These extension algebras are also constructed up to isomorphism. Received: 5 July 2007, Revised: 14 February 2008     

On the Wu metric in unbounded domains

We discuss the properties of the Wu pseudometric and present counterexamples for its upper semicontinuity that answers the question posed by Jarnicki and Pflug. We also give formulae for the Wu pseudometric in elementary Reinhardt domains. Received: 12 September 2007