Quantifier-free logic for nondeterministic theories

We develop a quantifier-free logic for deriving consequences of multialgebraic theories. Multialgebras are used as models for nondeterminism in the context of algebraic specifications. They are many sorted algebras with set-valued operations. Formulae are sequents over atoms allowing one to state set-inclusion or identity of 1-element sets (determinacy). We introduce a sound and weakly complete Rasiowa–Sikorski (R–S) logic for proving multialgebraic tautologies. We then extend this system for proving consequences of specifications based on translation of finite theories into logical formulae. Finally, we show how such a translation may be avoided—introduction of the specific cut rules leads to a sound and strongly complete Gentzen system for proving directly consequences of specifications. Besides giving examples of the general techniques of R–S and the specific cut rules, we improve the earlier logics for multialgebras by providing means to handle empty carriers (as well as empty result-sets) without the use of quantifiers, and to derive consequences of theories without translation into another format and without using general cut.     

Informative labeling schemes for graphs

This paper introduces the notion of informative labeling schemes for arbitrary graphs. Let f(W) be a function on subsets of vertices W. An f labeling scheme labels the vertices of a weighted graph G in such a way that f(W) can be inferred (or at least approximated) efficiently for any vertex subset W of G by merely inspecting the labels of the vertices of W, without having to use any additional information sources.A number of results illustrating this notion are presented in the paper. We begin by developing f labeling schemes for three functions f over the class of n-vertex trees. The first function, SepLevel, gives the separation level of any two vertices in the tree, namely, the depth of their least common ancestor. The second, LCA, provides the least common ancestor of any two vertices. The third, Center, yields the center of any three given vertices v₁,v₂,v₃ in the tree, namely, the unique vertex z connected to them by three edge-disjoint paths. All of these three labeling schemes use O-bit labels, which is shown to be asymptotically optimal.Our main results concern the function Steiner(W), defined for weighted graphs. For any vertex subset W in the weighted graph G, Steiner(W) represents the weight of the Steiner tree spanning the vertices of W in G. Considering the class of n-vertex trees with M-bit edge weights, it is shown that for this class there exists a Steiner labeling scheme using O((M+logn)logn) bit labels, which is asymptotically optimal. It is then shown that for the class of arbitrary n-vertex graphs with M-bit edge weights, there exists an approximate-Steiner labeling scheme, providing an estimate (up to a factor of O(logn)) for the Steiner weight Steiner(W) of a given set of vertices W, using O bit labels.     

Automatic diatom identification using contour analysis by morphological curvature scale spaces

A method for automatic identification of diatoms (single-celled algae with silica shells) based on extraction of features on the contour of the cells by multi-scale mathematical morphology is presented. After extracting the contour of the cell, it is smoothed adaptively, encoded using Freeman chain code, and converted into a curvature representation which is invariant under translation and scale change. A curvature scale space is built from these data, and the most important features are extracted from it by unsupervised cluster analysis. The resulting pattern vectors, which are also rotation-invariant, provide the input for automatic identification of diatoms by decision trees and k-nearest neighbor classifiers. The method is tested on two large sets of diatom images. The techniques used are applicable to other shapes besides diatoms. Andrei C. Jalba received his B.Sc. (1998) and M.Sc. (1999) in Applied Electronics and Information Engineering from “Politehnica” University of Bucharest, Romania. He recently obtained a Ph.D. degree at the Institute for Mathematics and Computing Science of the University of Groningen, where he now is a postdoctoral researcher. His research interests include computer vision, pattern recognition, image processing, and parallel computing. Michael Wilkinson obtained an M.Sc. in astronomy from the Kapteyn Laboratory, University of Groningen (RuG) in 1993, after which he worked on image analysis of intestinal bacteria at the Department of Medical Microbiology, RuG. This work formed the basis of his Ph.D. at the Institute of Mathematics and Computing Science (IWI), RuG, in 1995. He was appointed as researcher at the Centre for High Performance Computing (also RuG) working on simulating the intestinal microbial ecosystem on parallel computers. During that time he edited the book “Digital Image Analysis of Microbes” (John Wiley, UK, 1998) together with Frits Schut. After this he worked as a researcher at the IWI on image analysis of diatoms. He is currently assistant professor at the IWI. Jos B.T.M. Roerdink received his M.Sc. (1979) in theoretical physics from the University of Nijmegen, the Netherlands. Following his Ph.D. (1983) from the University of Utrecht and a 2-year position (1983--1985) as a Postdoctoral Fellow at the University of California, San Diego, both in the area of stochastic processes, he joined the Centre for Mathematics and Computer Science in Amsterdam. There he worked from 1986-1992 on image processing and tomographic reconstruction. He was appointed associate professor (1992) and full professor (2003), respectively, at the Institute for Mathematics and Computing Science of the University of Groningen, where he currently holds a chair in Scientific Visualization and Computer Graphics. His current research interests include biomedical visualization, neuroimaging and bioinformatics. Micha Bayer graduated from St. Andrews University, Scotland, with an M.Sc. in Marine Biology in 1994. He obtained his Ph.D. in Marine Biology from there in 1998, and then followed this up with two postdoctoral positions at the Royal Botanic Garden Edinburgh, Scotland, first on the ADIAC and then on the DIADIST project. In both of these projects he was responsible for establishing the collections of diatom training data to be used for the pattern recognition systems. From 2002–2003 he was enrolled for an M.Sc. in information technology at the University of Glasgow, Scotland, and is now working as a grid developer at the National e-Science Centre at Glasgow University. Stephen Juggins is a senior lecturer at the School of Geography, Politics and Sociology, University of Newcastle. His research focuses on the use of diatoms for monitoring environmental change and on the analysis of ecological and palaeoecological data. He has worked in Europe, North America and Central Asia on problems of river water quality, historical lake acidification, coastal eutrophication and Quaternary climate change.     

Classification of finger activation for use in a robotic prosthesis arm

Hand amputees would highly benefit from a robotic prosthesis, which would allow the movement of a number of fingers. In this paper we propose using the electromyographic signals recorded by two pairs of electrodes placed over the arm for operating such prosthesis. Multiple features from these signals are extracted whence the most relevant features are selected by a genetic algorithm as inputs for a simple classifier. This method results in a probability of error of less than 2%.     

Estimating the survival of Clostridium botulinum spores during heat treatments

A recently published study of the inactivation of Clostridium botulinum spores at various temperatures in the range of 101 to 121 degrees C and neutral pH revealed that their semilogarithmic survival curves all had considerable upward concavity. This finding indicated that heat inactivation of the spores under these conditions did not follow a first-order kinetics and that meaningful D values could not be calculated. The individual survival curves could be described by the cumulative form of the Weibull distribution, i.e., by log S = -b(T)t(n(T)), where S is the survival ratio and b(T) and n(T) are temperature-dependent coefficients. The fact that at all temperatures in the above range n(T) was smaller than 1 suggested that as time increases sensitive members of the population parish and survivors with increasing resistance remain. If damage accumulation is not a main factor, and the inactivation is path independent, then survival curves under monotonously increasing temperature can be constructed using a relatively simple model, which can be used to calculate the spores' survival in a limiting case. This is demonstrated with computer-simulated heating curves and the experimental constants of the C. botulinum spores, setting the number of decades reduction to 8, 10, and 12 (the current criterion for commercial sterility).     

Air Pollution Emission Inventory Survey for Israel

High ozone levels are regularly measured during summer months over the inland and mountainous regions of Israel. Studies analyzing the back trajectories of air masses responsible for the high ozone levels showed that the precursors originated from the densely populated Israeli coastline. In order to better understand the contribution of those emission sources to ozone production, it is essential to have an accurate emission inventory that can be inputted into a photochemical model. The present paper describes the methods used in preparing an emission inventory for Israel based on information available and published until 1998. The source and accuracy of the data available are described. The calculations performed and the assumptions taken in order to obtain data not directly available are clarified. The sources reported in the inventory were the major polluters (power plants, oil refineries, and cement industries); industry; transportation; and biogenic sources. The pollutants studied were SO₂, NO_x, CO, saturated and unsaturated hydrocarbons, ethylene, isoprene, toluene, xylene, formaldehyde, and aldehydes. The inventory showed that transportation is responsible for almost the entire CO and 30% of the volatile organic compounds emitted, although transportation itself accounts for only a fifth of total fuel consumption. About 75% of the NO_x emitted can be attributed to industrial sources and the remaining 25% to transportation. Model simulations using the emission inventory were performed and compared to data available from a monitoring station situated 30 km east of Tel Aviv. The results showed good agreement, validating the accuracy of the emission inventory. The present emission inventory provides an important database as input to photochemical models used in forecasting ozone levels over Israel.     

Distance-Dependent Distributed Directories

Distributed systems often make use of directory servers enabling the storage and retrieval of global information in the network. In many practical situations, the data are directly related to particular sites of the network, and therefore the desired retrieval characteristics are dependent on the network topology; for example, priority is given to having high accessibility to data generated in nearby locations. This paper defines the concept of distance-dependent directories, and then proposes appropriate accessibility measures and presents strategies for constructing such directories. The construction methods are based on efficient solutions to a new type of graph-covering problem. As an application, it is shown how to use a distance-dependent directory to implement a name-server component for a routing scheme.     

Fuzzy and probability vectors as elements of a vector space

The problem of defining vector space operations on fuzzy and probability vectors is discussed. It is shown that such a definition is equivalent to choosing a 1-1 and onto mapping from the unit interval into the real axis. Although such a mapping cannot be continuous, it is suggested that under certain approximations a continuous mapping can be chosen. A characterization of some useful mappings with applications to image processing is also given.     

Digital Image Compression by Outer Product Expansion

We approximate a digital image as a sum of outer products dxy^Twheredis a real number but the vectorsxandyhave elements +1, -1, or 0 only. The expansion gives a least squares approximation. Work is proportional to the number of pixels; reconstruction involves only additions.