Modelling the dynamics of log‐domain circuits

Log‐domain filters are an intriguing form of externally linear, internally nonlinear current‐mode circuits, in which a compression stage is first used to convert the input currents to the logarithmic domain, then analogue processing is carried out on the resulting voltages, and finally input–output linearity is restored by mapping the output voltages to current form through an expansion stage. The compressing and expanding operations confer on log‐domain filters a number of desirable features, but they may be responsible for the loss of external linearity. In this paper, sufficient conditions for the external linearity of log‐domain LC‐ladders are established, and the local nature of this external linearity is highlighted. Certain log‐domain LC‐ladders employing floating capacitors may exhibit externally nonlinear behaviour even for zero input and very small initial conditions. We show how transistor parasitic capacitances are central to the emergence of this behaviour, and must be incorporated in the circuit model. Copyright © 2006 John Wiley & Sons, Ltd.     

Langevin-schroedinger formulation of electronic tunneling through a molecular bridge with a dissipative acceptor

Modeling electronic tunneling through molecular bridges is desired in order to understand the mechanism of long-range electron transfer reactions in nature, as well as for the design of novel molecular electronics devices. Particularly interesting is the effect of the nuclear motion at the molecular bridge on the electron transfer mechanism and rate. In this work we study the effect of electronic nuclear coupling at the molecular bridge on a unidirectional electronic tunneling process from an electron donor into a dissipative acceptor, as may appear in controlled electron transfer reactions at biological membranes, or in heterogeneous electron transfer reactions. The model includes a collection of harmonic bath modes coupled to the dissipative acceptor site and a single mode at the molecular bridge. The parameters of the dissipative bath are tuned such that the electronic population decays from the donor to the acceptor. This process is simulated using a time-dependent nonlinear Langevin-Schroedinger equation, based on a mean-field approximation for the electronic-nuclear coupling at the acceptor site and a numerically exact treatment of the electronic-nuclear coupling at the molecular bridge. The simulations at zero temperature and weak electronic-nuclear coupling demonstrate that electronic tunneling is promoted by coupling to the nuclear mode at the bridge. This result is consistent with our previous studies of electronic tunneling oscillations in a symmetric donor-bridge-acceptor complex, and it emphasizes the importance of electronic nuclear coupling in analyzing long-range electron transfer processes through molecular bridges or wires.     

Synthesis of Zirconia Colloids from Aqueous Salt Solutions

We monitor the synthesis of ZrO₂ colloids from dissolved ZrOCl₂·8H₂O using quasi-elastic light scattering and cryo-transmission electron microscopy (cryo-TEM). We investigate the effects of both precursor salt concentration and pH on the final size distribution. We find that the initial pH plays the most important role in the final particle size and yield. These trends and cryo-TEM observations help elucidate the roles of nucleation, aggregation, and recrystallization.     

A formal perspective on the view selection problem

The view selection problem is to choose a set of views to materialize over a database schema, such that the cost of evaluating a set of workload queries is minimized and such that the views fit into a prespecified storage constraint. The two main applications of the view selection problem are materializing views in a database to speed up query processing, and selecting views to materialize in a data warehouse to answer decision support queries. In addition, view selection is a core problem for intelligent data placement over a wide-area network for data integration applications and data management for ubiquitous computing. We describe several fundamental results concerning the view selection problem. We consider the problem for views and workloads that consist of equality-selection, project and join queries, and show that the complexity of the problem depends crucially on the quality of the estimates that a query optimizer has on the size of the views it is considering to materialize. When a query optimizer has good estimates of the sizes of the views, we show a somewhat surprising result, namely, that an optimal choice of views may involve a number of views that is exponential in the size of the database schema. On the other hand, when an optimizer uses standard estimation heuristics, we show that the number of necessary views and the expression size of each view are polynomially bounded. Received: November 20, 1001 / Accepted: May 30, 2002 / Published online: September 25, 2002     

Beeping a maximal independent set

We consider the problem of computing a maximal independent set (MIS) in an extremely harsh broadcast model that relies only on carrier sensing. The model consists of an anonymous broadcast network in which nodes have no knowledge about the topology of the network or even an upper bound on its size. Furthermore, it is assumed that an adversary chooses at which time slot each node wakes up. At each time slot a node can either beep, that is, emit a signal, or be silent. At a particular time slot, beeping nodes receive no feedback, while silent nodes can only differentiate between none of its neighbors beeping, or at least one of its neighbors beeping. We start by proving a lower bound that shows that in this model, it is not possible to locally converge to an MIS in sub-polynomial time. We then study four different relaxations of the model which allow us to circumvent the lower bound and find an MIS in polylogarithmic time. First, we show that if a polynomial upper bound on the network size is known, it is possible to find an MIS in $\mathcal O (\log ^3 n)$ time. Second, if we assume sleeping nodes are awoken by neighboring beeps, then we can also find an MIS in $\mathcal O (\log ^3 n)$ time. Third, if in addition to this wakeup assumption we allow sender-side collision detection, that is, beeping nodes can distinguish whether at least one neighboring node is beeping concurrently or not, we can find an MIS in $\mathcal O (\log ^2 n)$ time. Finally, if instead we endow nodes with synchronous clocks, it is also possible to find an MIS in $\mathcal O (\log ^2 n)$ time.     

Language resources for Hebrew

We describe a suite of standards, resources and tools for computational encoding and processing of Modern Hebrew texts. These include an array of XML schemas for representing linguistic resources; a variety of text corpora, raw, automatically processed and manually annotated; lexical databases, including a broad-coverage monolingual lexicon, a bilingual dictionary and a WordNet; and morphological processors which can analyze, generate and disambiguate Hebrew word forms. The resources are developed under centralized supervision, so that they are compatible with each other. They are freely available and many of them have already been used for several applications, both academic and industrial.

Data integration with uncertainty

This paper reports our first set of results on managing uncertainty in data integration. We posit that data-integration systems need to handle uncertainty at three levels and do so in a principled fashion. First, the semantic mappings between the data sources and the mediated schema may be approximate because there may be too many of them to be created and maintained or because in some domains (e.g., bioinformatics) it is not clear what the mappings should be. Second, the data from the sources may be extracted using information extraction techniques and so may yield erroneous data. Third, queries to the system may be posed with keywords rather than in a structured form. As a first step to building such a system, we introduce the concept of probabilistic schema mappings and analyze their formal foundations. We show that there are two possible semantics for such mappings: by-table semantics assumes that there exists a correct mapping but we do not know what it is; by-tuple semantics assumes that the correct mapping may depend on the particular tuple in the source data. We present the query complexity and algorithms for answering queries in the presence of probabilistic schema mappings, and we describe an algorithm for efficiently computing the top-k answers to queries in such a setting. Finally, we consider using probabilistic mappings in the scenario of data exchange.     

Representing uncertain data: models, properties, and algorithms

In general terms, an uncertain relation encodes a set of possible certain relations. There are many ways to represent uncertainty, ranging from alternative values for attributes to rich constraint languages. Among the possible models for uncertain data, there is a tension between simple and intuitive models, which tend to be incomplete, and complete models, which tend to be nonintuitive and more complex than necessary for many applications. We present a space of models for representing uncertain data based on a variety of uncertainty constructs and tuple-existence constraints. We explore a number of properties and results for these models. We study completeness of the models, as well as closure under relational operations, and we give results relating closure and completeness. We then examine whether different models guarantee unique representations of uncertain data, and for those models that do not, we provide complexity results and algorithms for testing equivalence of representations. The next problem we consider is that of minimizing the size of representation of models, showing that minimizing the number of tuples also minimizes the size of constraints. We show that minimization is intractable in general and study the more restricted problem of maintaining minimality incrementally when performing operations. Finally, we present several results on the problem of approximating uncertain data in an insufficiently expressive model.     

MiniCon: A scalable algorithm for answering queries using views

The problem of answering queries using views is to find efficient methods of answering a query using a set of previously materialized views over the database, rather than accessing the database relations. The problem has received significant attention because of its relevance to a wide variety of data management problems, such as data integration, query optimization, and the maintenance of physical data independence. To date, the performance of proposed algorithms has received very little attention, and in particular, their scale up in the presence of a large number of views is unknown. We first analyze two previous algorithms, the bucket algorithm and the inverse-rules, and show their deficiencies. We then describe the MiniCon, a novel algorithm for finding the maximally-contained rewriting of a conjunctive query using a set of conjunctive views. We present the first experimental study of algorithms for answering queries using views. The study shows that the MiniCon scales up well and significantly outperforms the previous algorithms. We describe an extension of the MiniCon to handle comparison predicates, and show its performance experimentally. Finally, we describe how the MiniCon can be extended to the context of query optimization. Received: 15 October 2000 / Accepted: 15 April 2001 Published online: 28 June 2001