Solving MDPs using two-timescale simulated annealing with multiplicative weights

We develop extensions of the Simulated Annealing with Multiplicative Weights (SAMW) algorithm that proposed a method of solution of Finite-Horizon Markov Decision Processes (FH-MDPs). The extensions developed are in three directions: a) Use of the dynamic programming principle in the policy update step of SAMW b) A two-timescale actor-critic algorithm that uses simulated transitions alone, and c) Extending the algorithm to the infinite-horizon discounted-reward scenario. In particular, a) reduces the storage required from exponential to linear in the number of actions per stage-state pair. On the faster timescale, a 'critic' recursion performs policy evaluation while on the slower timescale an 'actor' recursion performs policy improvement using SAMW. We give a proof outlining convergence w.p. 1 and show experimental results on two settings: semiconductor fabrication and flow control in communication networks.

Studies on Binary Time Series Models with Applications to Empirical Macroeconomics and Finance

This thesis studies binary time series models and their applications in empirical macroeconomics and finance. In addition to previously suggested models, new dynamic extensions are proposed to the static probit model commonly used in the previous literature. In particular, we are interested in probit models with an autoregressive model structure. In Chapter 2, the main objective is to compare the predictive performance of the static and dynamic probit models in forecasting the U.S. and German business cycle recession periods. Financial variables, such as interest rates and stock market returns, are used as predictive variables. The empirical results suggest that the recession periods are predictable and dynamic probit models, especially models with the autoregressive structure, outperform the static model. Chapter 3 proposes a Lagrange Multiplier (LM) test for the usefulness of the autoregressive structure of the probit model. The finite sample properties of the LM test are considered with simulation experiments. Results indicate that the two alternative LM test statistics have reasonable size and power in large samples. In small samples, a parametric bootstrap method is suggested to obtain approximately correct size. In Chapter 4, the predictive power of dynamic probit models in predicting the direction of stock market returns are examined. The novel idea is to use recession forecast (see Chapter 2) as a predictor of the stock return sign. The evidence suggests that the signs of the U.S. excess stock returns over the risk-free return are predictable both in and out of sample. The new "error correction" probit model yields the best forecasts and it also outperforms other predictive models, such as ARMAX models, in terms of statistical and economic goodness-of-fit measures. Chapter 5 generalizes the analysis of univariate models considered in Chapters 2 4 to the case of a bivariate model. A new bivariate autoregressive probit model is applied to predict the current state of the U.S. business cycle and growth rate cycle periods. Evidence of predictability of both cycle indicators is obtained and the bivariate model is found to outperform the univariate models in terms of predictive power.

A new class of separators and planarity of chordal graphs

We introduce a new class of clique separators, called base sets, for chordal graphs. Base sets of a chordal graph closely reflect its structure. We show that the notion of base sets leads to structural characterizations of planar k-trees and planar chordal graphs. Using these characterizations, we develop linear time algorithms for recognizing planar k-trees and planar chordal graphs. These algorithms are extensions of the Lexicographic_Breadth_First_Search algorithm for recognizing chordal graphs and are much simpler than the general planarity checking algorithm. Further, we use the notion of base sets to prove the equivalence of hamiltonian 2-trees and maximal outerplanar graphs.

Stochastic models of IEEE 802.11e wireless net works with multimedia applications

We provide a survey of some of our recent results ([9], [13], [4], [6], [7]) on the analytical performance modeling of IEEE 802.11 wireless local area networks (WLANs). We first present extensions of the decoupling approach of Bianchi ([1]) to the saturation analysis of IEEE 802.11e networks with multiple traffic classes. We have found that even when analysing WLANs with unsaturated nodes the following state dependent service model works well: when a certain set of nodes is nonempty, their channel attempt behaviour is obtained from the corresponding fixed point analysis of the saturated system. We will present our experiences in using this approximation to model multimedia traffic over an IEEE 802.11e network using the enhanced DCF channel access (EDCA) mechanism. We have found that we can model TCP controlled file transfers, VoIP packet telephony, and streaming video in the IEEE802.11e setting by this simple approximation.

Freezing of a colloidal liquid subject to shear flow

A nonequilibrium generalization of the density-functional theory of freezing is proposed to investigate the shear-induced first-order phase transition in colloidal suspensions. It is assumed that the main effect of a steady shear is to break the symmetry of the structure factor of the liquid and that for small shear rate, the phenomenon of a shear-induced order-disorder transition may be viewed as an equilibrium phase transition. The theory predicts that the effective density at which freezing takes place increases with shear rate. The solid (which is assumed to be a bcc lattice) formed upon freezing is distorted and specifically there is less order in one plane compared with the order in the other two perpendicular planes. It is shown that there exists a critical shear rate above which the colloidal liquid does not undergo a transition to an ordered (or partially ordered) state no matter how large the density is. Conversely, above the critical shear rate an initially formed bcc solid always melts into an amorphous or liquidlike state. Several of these predictions are in qualitative agreement with the light-scattering experiments of Ackerson and Clark. The limitations as well as possible extensions of the theory are also discussed.

Magnetically induced currents and magnetic response properties of molecules

The magnetically induced currents in organic monoring and multiring molecules, in Möbius shaped molecules and in inorganic all-metal molecules have been investigated by means of the Gauge-including magnetically induced currents (GIMIC) method. With the GIMIC method, the ring-current strengths and the ring-current density distributions can be calculated. For open-shell molecules, also the spin current can be obtained. The ring-current pathways and ring-current strengths can be used to understand the magnetic resonance properties of the molecules, to indirectly identify the effect of non-bonded interactions on NMR chemical shifts, to design new molecules with tailored properties and to discuss molecular aromaticity. In the thesis, the magnetic criterion for aromaticity has been adopted. According to this, a molecule which has a net diatropic ring current might be aromatic. Similarly, a molecule which has a net paratropic current might be antiaromatic. If the net current is zero, the molecule is nonaromatic. The electronic structure of the investigated molecules has been resolved by quantum chemical methods. The magnetically induced currents have been calculated with the GIMIC method at the density-functional theory (DFT) level, as well as at the self-consistent field Hartree-Fock (SCF-HF), at the Møller-Plesset perturbation theory of the second order (MP2) and at the coupled-cluster singles and doubles (CCSD) levels of theory. For closed-shell molecules, accurate ring-current strengths can be obtained with a reasonable computational cost at the DFT level and with rather small basis sets. For open-shell molecules, it is shown that correlated methods such as MP2 and CCSD might be needed to obtain reliable charge and spin currents. The basis set convergence has to be checked for open-shell molecules by performing calculations with large enough basis sets. The results discussed in the thesis have been published in eight papers. In addition, some previously unpublished results on the ring currents in the endohedral fullerene Sc3C2@C80 and in coronene are presented. It is shown that dynamical effects should be taken into account when modelling magnetic resonance parameters of endohedral metallofullerenes such as Sc3C2@C80. The ring-current strengths in a series of nano-sized hydrocarbon rings are related to static polarizabilities and to H-1 nuclear magnetic resonance (NMR) shieldings. In a case study on the possible aromaticity of a Möbius-shaped [16]annulene we found that, according to the magnetic criterion, the molecule is nonaromatic. The applicability of the GIMIC method to assign the aromatic character of molecules was confirmed in a study on the ring currents in simple monocylic aromatic, homoaromatic, antiaromatic, and nonaromatic hydrocarbons. Case studies on nanorings, hexaphyrins and [n]cycloparaphenylenes show that explicit calculations are needed to unravel the ring-current delocalization pathways in complex multiring molecules. The open-shell implementation of GIMIC was applied in studies on the charge currents and the spin currents in single-ring and bi-ring molecules with open shells. The aromaticity predictions that are made based on the GIMIC results are compared to other aromaticity criteria such as H-1 NMR shieldings and shifts, electric polarizabilities, bond-length alternation, as well as to predictions provided by the traditional Hückel (4n+2) rule and its more recent extensions that account for Möbius twisted molecules and for molecules with open shells.

A Reference Architecture for Electronic Business-to-Business Collaboration Setup and Enactment Systems

The question what a business-to-business (B2B) collaboration setup and enactment application-system should look like remains open. An important element of such collaboration constitutes the inter-organizational disclosure of business-process details so that the opposing parties may protect their business secrets. For that purpose, eSourcing [37] has been developed as a general businessprocess collaboration concept in the framework of the EU research project Cross- Work. The eSourcing characteristics are guiding for the design and evaluation of an eSourcing Reference Architecture (eSRA) that serves as a starting point for software developers of B2B-collaboration systems. In this paper we present the results of a scenario-based evaluation method conducted with the earlier specified eSourcing Architecture (eSA) that generates as results risks, sensitivity, and tradeoff points that must be paid attention to if eSA is implemented. Additionally, the evaluation method detects shortcomings of eSA in terms of integrated components that are required for electronic B2B-collaboration. The evaluation results are used for the specification of eSRA, which comprises all extensions for incorporating the results of the scenario-based evaluation, on three refinement levels.

A Deterministic Optimization Approach to Protein Sequence Design Using Continuous Models

Determining the sequence of amino acid residues in a heteropolymer chain of a protein with a given conformation is a discrete combinatorial problem that is not generally amenable for gradient-based continuous optimization algorithms. In this paper we present a new approach to this problem using continuous models. In this modeling, continuous "state functions" are proposed to designate the type of each residue in the chain. Such a continuous model helps define a continuous sequence space in which a chosen criterion is optimized to find the most appropriate sequence. Searching a continuous sequence space using a deterministic optimization algorithm makes it possible to find the optimal sequences with much less computation than many other approaches. The computational efficiency of this method is further improved by combining it with a graph spectral method, which explicitly takes into account the topology of the desired conformation and also helps make the combined method more robust. The continuous modeling used here appears to have additional advantages in mimicking the folding pathways and in creating the energy landscapes that help find sequences with high stability and kinetic accessibility. To illustrate the new approach, a widely used simplifying assumption is made by considering only two types of residues: hydrophobic (H) and polar (P). Self-avoiding compact lattice models are used to validate the method with known results in the literature and data that can be practically obtained by exhaustive enumeration on a desktop computer. We also present examples of sequence design for the HP models of some real proteins, which are solved in less than five minutes on a single-processor desktop computer Some open issues and future extensions are noted.

A heuristic clustering algorithm using union of overlapping pattern-cells

Relative geometric arrangements of the sample points, with reference to the structure of the imbedding space, produce clusters. Hence, if each sample point is imagined to acquire a volume of a small M-cube (called pattern-cell), depending on the ranges of its (M) features and number (N) of samples; then overlapping pattern-cells would indicate naturally closer sample-points. A chain or blob of such overlapping cells would mean a cluster and separate clusters would not share a common pattern-cell between them. The conditions and an analytic method to find such an overlap are developed. A simple, intuitive, nonparametric clustering procedure, based on such overlapping pattern-cells is presented. It may be classified as an agglomerative, hierarchical, linkage-type clustering procedure. The algorithm is fast, requires low storage and can identify irregular clusters. Two extensions of the algorithm, to separate overlapping clusters and to estimate the nature of pattern distributions in the sample space, are also indicated.

Analytical and numerical solutions of inward spherical solidification of a superheated melt with radiative-convective heat transfer and density jump at freezing front

Analytical and numerical solutions of a general problem related to the radially symmetric inward spherical solidification of a superheated melt have been studied in this paper. In the radiation-convection type boundary conditions, the heat transfer coefficient has been taken as time dependent which could be infinite, at time,t=0. This is necessary, for the initiation of instantaneous solidification of superheated melt, over its surface. The analytical solution consists of employing suitable fictitious initial temperatures and fictitious extensions of the original region occupied by the melt. The numerical solution consists of finite difference scheme in which the grid points move with the freezing front. The numerical scheme can handle with ease the density changes in the solid and liquid states and the shrinkage or expansions of volumes due to density changes. In the numerical results, obtained for the moving boundary and temperatures, the effects of several parameters such as latent heat, Boltzmann constant, density ratios, heat transfer coefficients, etc. have been shown. The correctness of numerical results has also been checked by satisfying the integral heat balance at every timestep.

Automatic verification of distributed logic specifications

Formal specification is vital to the development of distributed real-time systems as these systems are inherently complex and safety-critical. It is widely acknowledged that formal specification and automatic analysis of specifications can significantly increase system reliability. Although a number of specification techniques for real-time systems have been reported in the literature, most of these formalisms do not adequately address to the constraints that the aspects of 'distribution' and 'real-time' impose on specifications. Further, an automatic verification tool is necessary to reduce human errors in the reasoning process. In this regard, this paper is an attempt towards the development of a novel executable specification language for distributed real-time systems. First, we give a precise characterization of the syntax and semantics of DL. Subsequently, we discuss the problems of model checking, automatic verification of satisfiability of DL specifications, and testing conformance of event traces with DL specifications. Effective solutions to these problems are presented as extensions to the classical first-order tableau algorithm. The use of the proposed framework is illustrated by specifying a sample problem.

Signals of additional Z ` boson in e(+)e(-) -> W+W- at the ILC with polarized beams

We consider the possibility of fingerprinting the presence of heavy additional Z' bosons that arise naturally in extensions of the standard model such as E-6 models and left-right symmetric models, through their mixing with the standard model Z boson. By considering a class of observables including total cross sections, energy distributions and angular distributions of decay leptons we find significant deviation from the standard model predictions for these quantities with right-handed electrons and left-handed positrons at root s= 800GeV. The deviations being less pronounced at smaller centre of mass energies as the models are already tightly constrained. Our work suggests that the ILC should have a strong beam polarization physics program particularly with these configurations. On the other hand, a forward backward asymmetry and lepton fraction in the backward direction are more sensitive to new physics with realistic polarization due to interesting interplay with the neutrino t-channel diagram. This process complements the study of fermion pair production processes that have been considered for discrimination between these models.

Entanglement and nonclassicality for multimode radiation-field states

Nonclassicality in the sense of quantum optics is a prerequisite for entanglement in multimode radiation states. In this work we bring out the possibilities of passing from the former to the latter, via action of classicality preserving systems like beam splitters, in a transparent manner. For single-mode states, a complete description of nonclassicality is available via the classical theory of moments, as a set of necessary and sufficient conditions on the photon number distribution. We show that when the mode is coupled to an ancilla in any coherent state, and the system is then acted upon by a beam splitter, these conditions turn exactly into signatures of negativity under partial transpose (NPT) entanglement of the output state. Since the classical moment problem does not generalize to two or more modes, we turn in these cases to other familiar sufficient but not necessary conditions for nonclassicality, namely the Mandel parameter criterion and its extensions. We generalize the Mandel matrix from one-mode states to the two-mode situation, leading to a natural classification of states with varying levels of nonclassicality. For two-mode states we present a single test that can, if successful, simultaneously show nonclassicality as well as NPT entanglement. We also develop a test for NPT entanglement after beam-splitter action on a nonclassical state, tracing carefully the way in which it goes beyond the Mandel nonclassicality test. The result of three-mode beam-splitter action after coupling to an ancilla in the ground state is treated in the same spirit. The concept of genuine tripartite entanglement, and scalar measures of nonclassicality at the Mandel level for two-mode systems, are discussed. Numerous examples illustrating all these concepts are presented.

Nonequilibrium phase transitions in a driven sandpile model

We construct a driven sandpile slope model and study it by numerical simulations in one dimension. The model is specified by a threshold slope sigma(c), a parameter alpha, governing the local current-slope relation (beyond threshold), and j(in), the mean input current of sand. A non-equilibrium phase diagram is obtained in the alpha-j(in) plane. We find an infinity of phases, characterized by different mean slopes and separated by continuous or first-order boundaries, some of which we obtain analytically. Extensions to two dimensions are discussed.z

Physics with e(+)e(-) linear colliders

The physics potential of e(+) e(-) linear colliders is summarized in this report. These machines are planned to operate in the first phase at a center-of-mass energy of 500 GeV, before being scaled up to about 1 TeV. In the second phase of the operation, a final energy of about 2 TeV is expected. The machines will allow us to perform precision tests of the heavy particles in the Standard Model, the top quark and the electroweak bosons. They are ideal facilities for exploring the properties of Higgs particles, in particular in the intermediate mass range. New vector bosons and novel matter particles in extended gauge theories can be searched for and studied thoroughly. The machines provide unique opportunities for the discovery of particles in supersymmetric extensions of the Standard Model, the spectrum of Higgs particles, the supersymmetric partners of the electroweak gauge and Higgs bosons, and of the matter particles. High precision analyses of their properties and interactions will allow for extrapolations to energy scales close to the Planck scale where gravity becomes significant. In alternative scenarios, i.e. compositeness models, novel matter particles and interactions can be discovered and investigated in the energy range above the existing colliders lip to the TeV scale. Whatever scenario is realized in Nature, the discovery potential of e(+) e(-) linear colliders and the high precision with which the properties of particles and their interactions can be analyzed, define an exciting physics program complementary to hadron machines. (C) 1998 Elsevier Science B.V. All rights reserved.