### Refine

#### Year of publication

- 1999 (425) (remove)

#### Document Type

- Preprint (351)
- Article (66)
- Report (4)
- Diploma Thesis (1)
- Lecture (1)
- Periodical Part (1)
- Study Thesis (1)

#### Language

- English (425) (remove)

#### Keywords

- AG-RESY (6)
- Case-Based Reasoning (6)
- HANDFLEX (5)
- Location Theory (5)
- PARO (5)
- case-based problem solving (5)
- Abstraction (4)
- Knowledge Acquisition (4)
- resolution (4)
- Fallbasiertes Schließen (3)

#### Faculty / Organisational entity

A fundamental variance reduction technique for Monte Carlo integration in the framework of integro-approximation problems is
presented. Using the method of dependent tests a successive hierarchical function approximation algorithm is developed, which
captures discontinuities and exploits smoothness in the target function. The general mathematical scheme and its highly efficient
implementation are illustrated for image generation by ray tracing,
yielding new and much faster image synthesis algorithms.

We study the global solution of Fredholm integral equations of the second kind by the help of Monte Carlo methods. Global solution means that we seek to approximate the full solution function. This is opposed to the usual applications of Monte Carlo, were one only wants to approximate a functional of the solution. In recent years several researchers developed Monte Carlo methods also for the global problem. In this paper we present a new Monte Carlo algorithm for the global solution of integral equations. We use multiwavelet expansions to approximate the solution. We study the behaviour of variance on increasing levels, and based on this, develop a new variance reduction technique. For classes of smooth kernels and right hand sides we determine the convergence rate of this algorithm and show that it is higher
than those of previously developed algorithms for the global problem. Moreover, an information-based complexity analysis shows that our algorithm is optimal among all stochastic algorithms of the same computational
cost and that no deterministic algorithm of the same cost can reach its convergence rate.

Approximation properties of the underlying estimator are used to improve the efficiency of the method of dependent tests. A multilevel approximation procedure is developed such that in each level the number of samples is balanced with the level-dependent variance, resulting in a considerable reduction of the overall computational cost. The new technique is applied to the Monte Carlo estimation of integrals depending on a parameter.

We consider a Darcy flow model with saturation-pressure relation extended
with a dynamic term, namely, the time derivative of the saturation.
This model was proposed in works of J.Hulshof and J.R.King (1998), S.M.Hassanizadeh and W.G.Gray (1993),
F.Stauffer (1978).
We restrict ourself to one spatial dimension and strictly positive
initial saturation. For this case we transform the initial-boundary value
problem into combination of elliptic boundary-value problem and initial
value problem for abstract Ordinary Differential Equation. This splitting
is rather helpful both for theoretical aspects and numerical methods.

Abstract: Random matrix theory (RMT) is a powerful statistical tool to model spectral fluctuations. In addition, RMT provides efficient means to separate different scales in spectra. Recently RMT has found application in quantum chromodynamics (QCD). In mesoscopic physics, the Thouless energy sets the universal scale for which RMT applies. We try to identify the equivalent of a Thouless energy in complete spectra of the QCD Dirac operator with staggered fermions and SU_(2) lattice gauge fields. Comparing lattice data with RMT predictions we find deviations which allow us to give an estimate for this scale.

Beyond the Thouless energy
(1999)

Abstract: The distribution and the correlations of the small eigenvalues of the Dirac operator are described by random matrix theory (RMT) up to the Thouless energy E_= 1 / sqrt (V), where V is the physical volume. For somewhat larger energies, the same quantities can be described by chiral perturbation theory (chPT). For most quantities there is an intermediate energy regime, roughly 1/V < E < 1/sqrt (V), where the results of RMT and chPT agree with each other. We test these predictions by constructing the connected and disconnected scalar susceptibilities from Dirac spectra obtained in quenched SU(2) and SU(3) simulations with staggered fermions for a variety of lattice sizes and coupling constants. In deriving the predictions of chPT, it is important totake into account only those symmetries which are exactly realized on the lattice.

Abstract: Recently, the chiral logarithms predicted by quenched chiral perturbation theory have been extracted from lattice calculations of hadron masses. We argue that the deviations of lattice results from random matrix theory starting around the so-called Thouless energy can be understood in terms of chiral perturbation theory as well. Comparison of lattice data with chiral perturbation theory formulae allows us to compute the pion decay constant. We present results from a calculation for quenched SU(2) with Kogut-Susskind fermions at ß = 2.0 and 2.2.

Abstract: Recently, the contributions of chiral logarithms predicted by quenched chiral perturbation theory have been extracted from lattice calculations of hadron masses. We argue that a detailed comparison of random matrix theory and lattice calculations allows for a precise determination of such corrections. We estimate the relative size of the m log(m), m, and m^2 corrections to the chiral condensate for quenched SU(2).

Abstract: We describe a general technique that allows for an ideal transfer of quantum correlations between light fields and metastable states of matter. The technique is based on trapping quantum states of photons in coherently driven atomic media, in which the group velocity is adiabatically reduced to zero. We discuss possible applications such as quantum state memories, generation of squeezed atomic states, preparation of entangled atomic ensembles and quantum information processing.

Abstract: We show that it is possible to "store" quantum states of single-photon fields by mapping them onto collective meta-stable states of an optically dense, coherently driven medium inside an optical resonator. An adiabatic technique is suggested which allows to transfer non-classical correlations from traveling-wave single-photon wave-packets into atomic states and vise versa with nearly 100% efficiency. In contrast to previous approaches involving single atoms, the present technique does not require the strong coupling regime corresponding to high-Q micro-cavities. Instead, intracavity Electromagnetically Induced Transparency is used to achieve a strong coupling between the cavity mode and the atoms.

Mirrorless oscillation based on resonantly enhanced 4-wave mixing: All-order analytic solutions
(1999)

Abstract: The phase transition to mirrorless oscillation in resonantly enhanced four-wave mixing in double-A systems are studied analytically for the ideal case of infinite lifetimes of ground-state coherences. The stationary susceptibilities are obtained in all orders of the generated fields and analytic solutions of the coupled nonlinear differential equations for the field amplitudes are derived and discussed.

Abstract: We utilize the generation of large atomic coherence to enhance the resonant nonlinear magneto-optic effect by several orders of magnitude, thereby eliminating power broadening and improving the fundamental signal-to-noise ratio. A proof-of-principle experiment is carried out in a dense vapor of Rb atoms. Detailed numerical calculations are in good agreement with the experimental results. Applications such as optical magnetometry or the search for violations of parity and time reversal symmetry are feasible.

Abstract: Spontaneous emission and Lamb shift of atoms in absorbing dielectrics are discussed. A Green's-function approach is used based on the multipolar interaction Hamiltonian of a collection of atomic dipoles with the quantised radiation field. The rate of decay and level shifts are determined by the retarded Green's-function of the interacting electric displacement field, which is calculated from a Dyson equation describing multiple scattering. The positions of the atomic dipoles forming the dielectrics are assumed to be uncorrelated and a continuum approximation is used. The associated unphysical interactions between different atoms at the same location is eliminated by removing the point-interaction term from the free-space Green's-function (local field correction). For the case of an atom in a purely dispersive medium the spontaneous emission rate is altered by the well-known Lorentz local-field factor. In the presence of absorption a result different from previously suggested expressions is found and nearest-neighbour interactions are shown to be important.

Abstract: We aim to establish a link between path-integral formulations of quantum and classical field theories via diagram expansions. This link should result in an independent constructive characterisation of the measure in Feynman path integrals in terms of a stochastic differential equation (SDE) and also in the possibility of applying methods of quantum field theory to classical stochastic problems. As a first step we derive in the present paper a formal solution to an arbitrary c-number SDE in a form which coincides with that of Wick's theorem for interacting bosonic quantum fields. We show that the choice of stochastic calculus in the SDE may be regarded as a result of regularisation, which in turn removes ultraviolet divergences from the corresponding diagram series.

We show that the solution to an arbitrary c-number stochastic differential equation (SDE) can be represented as a diagram series. Both the diagram rules and the properties of the graphical elements reflect causality properties of the SDE and this series is therefore called a causal diagram series. We also discuss the converse problem, i.e. how to construct an SDE of which a formal solution is a given causal diagram series. This then allows for a nonperturbative summation of the diagram series by solving this SDE, numerically or analytically.

Abstract: We propose a simple method for measuring the populations and the relative phase in a coherent superposition of two atomic states. The method is based on coupling the two states to a third common (excited) state by means of two laser pulses, and measuring the total fluorescence from the third state for several choices of the excitation pulses.

Abstract: We present experimental and theoretical results of a detailed study of laser-induced continuum structures (LICS) in the photoionization continuum of helium out of the metastable state 2s^1 S_0. The continuum dressing with a 1064 nm laser, couples the same region of the continuum to the 4s^1 S_0 state. The experimental data, presented for a range of intensities, show pronounced ionization suppression (by asmuch as 70% with respect to the far-from-resonance value) as well as enhancement, in a Beutler-Fano resonance profile. This ionization suppression is a clear indication of population trapping mediated by coupling to a contiuum. We present experimental results demonstrating the effect of pulse delay upon the LICS, and for the behavior of LICS for both weak and strong probe pulses. Simulations based upon numerical solution of the Schrödinger equation model the experimental results. The atomic parameters (Rabi frequencies and Stark shifts) are calculated using a simple model-potential method for the computation of the needed wavefunctions. The simulations of the LICS profiles are in excellent agreement with experiment. We also present an analytic formulation of pulsed LICS. We show that in the case of a probe pulse shorter than the dressing one the LICS profile is the convolution of the power spectra of the probe pulse with the usual Fano profile of stationary LICS. We discuss some consequences of deviation from steady-state theory.

We present results from a study of the coherence properties of a system involving three discrete states coupled to each other by two-photon processes via a common continuum. This tripod linkage is an extension of the standard laser-induced continuum structure (LICS) which involves two discrete states and two lasers. We show that in the tripod scheme, there exist two population trapping conditions; in some cases these conditions are easier to satisfy than the single trapping condition in two-state LICS. Depending on the pulse timing, various effects can be observed. We derive some basic properties of the tripod scheme, such as the solution for coincident pulses, the behaviour of the system in the adiabatic limit for delayed pulses, the conditions for no ionization and for maximal ionization, and the optimal conditions for population transfer between the discrete states via the continuum. In the case when one of the discrete states is strongly coupled to the continuum, the population dynamics reduces to a standard two-state LICS problem (involving the other two states) with modified parameters; this provides the opportunity to customize the parameters of a given two-state LICS system.

Abstract: In this paper we present a renormalizability proof for spontaneously broken SU (2) gauge theory. It is based on Flow Equations, i.e. on the Wilson renormalization group adapted to perturbation theory. The power counting part of the proof, which is conceptually and technically simple, follows the same lines as that for any other renormalizable theory. The main difficulty stems from the fact that the regularization violates gauge invariance. We prove that there exists a class of renormalization conditions such that the renormalized Green functions satisfy the Slavnov-Taylor identities of SU (2) Yang-Mills theory on which the gauge invariance of the renormalized theory is based.

Magnetic anisotropies of MBE-grown fcc Co(110)-films on Cu(110) single crystal substrates have been determined by using Brillouin light scattering(BLS) and have been correlated with the structural properties determined by low energy electron diffraction (LEED) and scanning tunneling microscopy (STM). Three regimes of film growth and associated anisotropy behavior are identified: coherent growth in the Co film thickness regime of up to 13 Å, in-plane anisotropic strain relaxation between 13 Å and about 50 Å and inplane isotropic strain relaxation above 50 Å. The structural origin of the transition between anisotropic and isotropic strain relaxation was studied using STM. In the regime of anisotropic strain relaxation long Co stripes with a preferential [ 110 ]-orientation are observed, which in the isotropic strain relaxation regime are interrupted in the perpendicular in-plane direction to form isotropic islands. In the Co film thickness regime below 50 Å an unexpected suppression of the magnetocrystalline anisotropy contribution is observed. A model calculation based on a crystal field formalism and discussed within the context of band theory, which explicitly takes tetragonal misfit strains into account, reproduces the experimentally observed anomalies despite the fact that the thick Co films are quite rough.

Absract: We report on measurements of the two-dimensional intensity distribtion of linear and non-linear spin wave excitations in a LuBiFeO film. The spin wave intensity was detected with a high-resolution Brillouinlight scatteringspectroscopy setup. The observed snake-like structure of the spin wave intensity distribution is understood as a mode beating between modes with different lateral spin wave intensity distributions. The theoretical treatment of the linear regime is performed analytically, whereas the propagation of non-linear spin waves is simulated by a numerical solution of a non-linear Schrödinger equation with suitable boundary conditions.

Abstract: The periodic bounce configurations responsible for quantum tunneling are obtained explicitly and are extended to the finite energy case for minisuperspace models of the Universe. As a common feature of the tunneling models at finite energy considered here we observe that the period of the bounce increases with energy monotonically. The periodic bounces do not have bifurcations and make no contribution to the nucleation rate except the one with zero energy. The sharp first order phase transition from quantum tunneling to thermal activation is verified with the general criterions.

We consider a (2 + 1)-dimensional mechanical system with the Lagrangian linear in the torsion of a light-like curve. We give Hamiltonian formulation of this system and show that its mass and spin spectra are defined by one-dimensional nonrelativistic mechanics with a cubic potential. Consequently, this system possesses the properties typical of resonance-like particles.

Starting from the Hamiltonian operator of the noncompensated two-sublattice model of a small antiferromagnetic particle, we derive the e effective Lagrangian of a biaxial antiferromagnetic particle in an external magnetic field with the help of spin-coherent-state path integrals. Two unequal level-shifts induced by tunneling through two types of barriers are obtained using the instanton method. The energy spectrum is found from Bloch theory regarding the periodic potential as a superlattice. The external magnetic field indeed removes Kramers' degeneracy, however a new quenching of the energy splitting depending on the applied magnetic field is observed for both integer and half-integer spins due to the quantum interference between transitions through two types of barriers.

The development of complex software systems is driven by many diverse and sometimes contradictory requirements such as correctness and maintainability of resulting products, development costs, and time-to-market. To alleviate these difficulties, we propose a development method for distributed systems that integrates different basic approaches. First, it combines the use of the formal description technique SDL with software reuse concepts. This results in the definition of a use-case driven, incremental development method with SDL-patterns as the main reusable artifacts. Experience with this approach has shown that there are several other factors of influence, such as the quality of reuse artifacts or the experience of the development team. Therefore, we further combined our SDL-pattern approach with an improvement methodology known from the area of experimental software engineering. In order to demonstrate the validity of this integrating approach, we sketch some representative outcomings of a case study.

We consider three applications of impulse control in financial mathematics, a cash management problem, optimal control of an exchange rate, and portfolio optimisation under transaction costs. We sketch the different ways of solving these problems with the help of quasi-variational inequalities. Further, some viscosity solution results are presented.

Continuous and discrete superselection rules induced by the interaction with the environment are investigated for a class of exactly soluble Hamiltonian models. The environment is given by a Boson field. Stable superselection sectors can only emerge if the low frequences dominate and the ground state of the Boson field disappears due to infrared divergence. The models allow uniform estimates of all transition matrix elements between different superselection sectors.

The paper studies quantum states of a Bloch particle in presence of external ac and dc fields. Provided the period of the ac field and the Bloch period are commensurate, an effective scattering matrix is introduced, the complex poles of which are the system quasienergy spectrum. The statistics of the resonance width and the Wigner delay time shows a close relation of the problem to random matrix theory of chaotic scattering.

The paper studies metastable states of a Bloch electron in the presence of external ac and dc fields. Provided resonance condition between period of the driving frequency and the Bloch period, the complex quasienergies are numerically calculated for two qualitatively different regimes (quasiregular and chaotic) of the system dynamics. For the chaotic regime an effect of quantum stabilization, which suppresses the classical decay mechanism, is found. This effect is demonstrated to be a kind of quantum interference phenomenon sensitive to the resonance condition.

A novel method is presented which allows a fast computation of complex energy resonance states in Stark systems, i.e. systems in a homogeneous field. The technique is based on the truncation of a shift-operator in momentum space. Numerical results for space periodic and non-periodic systems illustrate the extreme simplicity of the method.

A new method for calculating Stark resonances is presented and applied for illustration to the simple case of a one-particle, one-dimensional model Hamiltonian. The method is applicable for weak and strong dc fields. The only need, also for the case of many particles in multi-dimensional space, are either the short time evolution matrix elements or the eigenvalues and Fourier components of the eigenfunctions of the field-free Hamiltonian.

We present an entropy concept measuring quantum localization in dynamical systems based on time averaged probability densities. The suggested entropy concept is a generalization of a recently introduced [PRL 75, 326 (1995)] phase-space entropy to any representation chosen according to the system and the physical question under consideration. In this paper we inspect the main characteristics of the entropy and the relation to other measures of localization. In particular the classical correspondence is discussed and the statistical properties are evaluated within the framework of random vector theory. In this way we show that the suggested entropy is a suitable method to detect quantum localization phenomena in dynamical systems.

The Filter-Diagonalization Method is applied to time periodic Hamiltonians and used to find selectively the regular and chaotic quasienergies of a driven 2D rotor. The use of N cross-correlation probability amplitudes enables a selective calculation of the quasienergies from short time propagation to the time T (N). Compared to the propagation time T (1) which is required for resolving the quasienergy spectrum with the same accuracy from auto-correlation calculations, the cross-correlation time T (N) is shorter by the factor N , that is T (1) = N T (N).

The global dynamical properties of a quantum system can be conveniently visualized in phase space by means of a quantum phase space entropy in analogy to a Poincare section in classical dynamics for two-dimensional time independent systems. Numerical results for the Pullen Edmonds systems demonstrate the properties of the method for systems with mixed chaotic and regular dynamics.

In this paper we deal with the determination of the whole set of Pareto-solutions of location problems with respect to Q general criteria.These criteria include median, center or cent-dian objective functions as particular instances.The paper characterizes the set of Pareto-solutions of a these multicriteria problems. An efficient algorithm for the planar case is developed and its complexity is established. Extensions to higher dimensions as well as to the non-convexcase are also considered.The proposed approach is more general than the previously published approaches to multi-criteria location problems and includes almost all of them as particular instances.

In a discrete-time financial market setting, the paper relates various concepts introduced for dynamic portfolios (both in discrete and in continuous time). These concepts are: value preserving portfolios, numeraire portfolios, interest oriented portfolios, and growth optimal portfolios. It will turn out that these concepts are all associated with a unique martingale measure which agrees with the minimal martingale measure only for complete markets.

Facility Location Problems are concerned with the optimal location of one or several new facilities, with respect to a set of existing ones. The objectives involve the distance between new and existing facilities, usually a weighted sum or weighted maximum. Since the various stakeholders (decision makers) will have different opinions of the importance of the existing facilities, a multicriteria problem with several sets of weights, and thus several objectives, arises. In our approach, we assume the decision makers to make only fuzzy comparisons of the different existing facilities. A geometric mean method is used to obtain the fuzzy weights for each facility and each decision maker. The resulting multicriteria facility location problem is solved using fuzzy techniques again. We prove that the final compromise solution is weakly Pareto optimal and Pareto optimal, if it is unique, or under certain assumptions on the estimates of the Nadir point. A numerical example is considered to illustrate the methodology.

Value Preserving Strategies and a General Framework for Local Approaches to Optimal Portfolios
(1999)

We present some new general results on the existence and form of value preserving portfolio strategies in a general semimartingale setting. The concept of value preservation will be derived via a mean-variance argument. It will also be embedded into a framework for local approaches to the problem of portfolio optimisation.

Discretizations for the Incompressible Navier-Stokes Equations based on the Lattice Boltzmann Method
(1999)

A discrete velocity model with spatial and velocity discretization based on a lattice Boltzmann method is considered in the low Mach number limit. A uniform numerical scheme for this model is investigated. In the limit, the scheme reduces to a finite difference scheme for the incompressible Navier-Stokes equation which is a projection method with a second order spatial discretization on a regular grid. The discretization is analyzed and the method is compared to Chorin's original spatial discretization. Numerical results supporting the analytical statements are presented.

In this paper we derive fluid dynamic equations byperforming asymptotic analysis for the generalized Boltzmann equationfor polyatomic gases. In particular, we consider the steady state,one-dimensional Boltzmann equation with one additional internal energyand different relaxation times. Moreover, we present a new approachto define coupling procedures for the Boltzmann equation and Navier-Stokesequations based on the 14-moments expansion of Levermore. These coupledmodels are validated by numerical simulations.

We consider a scale discrete wavelet approach on the sphere based on spherical radial basis functions. If the generators of the wavelets have a compact support, the scale and detail spaces are finite-dimensional, so that the detail information of a function is determined by only finitely many wavelet coefficients for each scale. We describe a pyramid scheme for the recursive determination of the wavelet coefficients from level to level, starting from an initial approximation of a given function. Basic tools are integration formulas which are exact for functions up to a given polynomial degree and spherical convolutions.

Moment inequalities for the Boltzmann equation and applications to spatially homogeneous problems
(1999)

Some inequalities for the Boltzmann collision integral are proved. These inequalities can be considered as a generalization of the well-known Povzner inequality. The inequalities are used to obtain estimates of moments of solution to the spatially homogeneous Boltzmann equation for a wide class of intermolecular forces. We obtained simple necessary and sufficient conditions (on the potential) for the uniform boundedness of all moments. For potentials with compact support the following statement is proved. .....

Using an experience factory is one possible concept for supporting and improving reuse in software development. (i.e., reuse of products, processes, quality models, ...). In the context of the Sonderforschungsbereich 501: "Development of Large Systems with Generic methods" (SFB501), the Software Engineering Laboratory (SE Lab) runs such an experience factory as part of the infrastructure services it offers. The SE Lab also provides several tools to support the planning, developing, measuring, and analyzing activities of software development processes. Among these tools, the SE Lab runs and maintains an experience base, the SFB-EB. When an experience factory is utilized, support for experience base maintenance is an important issue. Furthermore, it might be interesting to evaluate experience base usage with regard to the number of accesses to certain experience elements stored in the database. The same holds for the usage of the tools provided by the SE LAB. This report presents a set of supporting tools that were designed to aid in these tasks. These supporting tools check the experience base's consistency and gather information on the usage of SFB-EB and the tools installed in the SE Lab. The results are processed periodically and displayed as HTML result reports (consistency checking) or bar charts (usage profiles).

Manipulating deformable linear objects - Vision-based recognition of contact state transitions -
(1999)

A new and systematic approach to machine vision-based robot manipulation of deformable (non-rigid) linear objects is introduced. This approach reduces the computational needs by using a simple state-oriented model of the objects. These states describe the relation of the object with respect to an obstacle and are derived from the object image and its features. Therefore, the object is segmented from a standard video frame using a fast segmentation algorithm. Several object features are presented which allow the state recognition of the object while being manipulated by the robot.

Comprehensive reuse and systematic evolution of reuse artifacts as proposed by the Quality Improvement Paradigm (QIP) do not only require tool support for mere storage and retrieval. Rather, an integrated management of (potentially reusable) experience data as well as project-related data is needed. This paper presents an approach exploiting object-relational database technology to implement the QIP-driven reuse repository of the SFB 501. Requirements, concepts, and implementational aspects are discussed and illustrated through a running example, namely the reuse and continuous improvement of SDL patterns for developing distributed systems. Based on this discussion, we argue that object-relational database management systems (ORDBMS) are best suited to implement such a comprehensive reuse repository. It is demonstrated how this technology can be used to support all phases of a reuse process and the accompanying improvement cycle. Although the discussions of this paper are strongly related to the requirements of the SFB 501 experience base, the basic realization concepts, and, thereby, the applicability of ORDBMS, can easily be extended to similar applications, i. e., reuse repositories in general.

The paper shows that characterizing the causal relationship between significant events is an important but non-trivial aspect for understanding the behavior of distributed programs. An introduction to the notion of causality and its relation to logical time is given; some fundamental results concerning the characterization of causality are pre- sented. Recent work on the detection of causal relationships in distributed computations is surveyed. The relative merits and limitations of the different approaches are discussed, and their general feasibility is analyzed.

Trigonometric invariants are defined for each Weyl group orbit on the root lattice. They are real and periodic on the coroot lattice. Their polynomial algebra is spanned by a basis which is calculated by means of an algorithm. The invariants of the basis can be used as coordinates in any cell of the coroot space and lead to an exactly solvable model of Sutherland type. We apply this construction to the \(F_4\) case.

The Hamiltonian of the \(N\)-particle Calogero model can be expressed in terms of generators of a Lie algebra for a definite class of representations. Maintaining this Lie algebra, its representations, and the flatness of the Riemannian metric belonging to the second order differential operator, the set of all possible quadratic Lie algebra forms is investigated. For \(N = 3\) and \(N = 4\) such forms are constructed explicitly and shown to correspond to exactly solvable Sutherland models. The results can be carried over easily to all \(N\).

The task of handling non-rigid one-dimensional objects by a robot manipulation system is investigated. To distinguish between different non-rigid object behaviors, five classes of deformable objects from a robotic point of view are proposed. Additionally, an enumeration of all possible contact states of one-dimensional objects with polyhedral obstacles is provided. Finally, the qualitative motion behavior of linear objects is analyzed for stable point contacts. Experiments with different materials validate the analytical results.

We present an approach to learning cooperative behavior of agents. Our ap-proach is based on classifying situations with the help of the nearest-neighborrule. In this context, learning amounts to evolving a set of good prototypical sit-uations. With each prototypical situation an action is associated that should beexecuted in that situation. A set of prototypical situation/action pairs togetherwith the nearest-neighbor rule represent the behavior of an agent.We demonstrate the utility of our approach in the light of variants of thewell-known pursuit game. To this end, we present a classification of variantsof the pursuit game, and we report on the results of our approach obtained forvariants regarding several aspects of the classification. A first implementationof our approach that utilizes a genetic algorithm to conduct the search for a setof suitable prototypical situation/action pairs was able to handle many differentvariants.

The common wisdom that goal orderings can be used to improve planning performance is nearly as old as planning itself. During the last decades of research several approaches emerged that computed goal orderings for different planning paradigms, mostly in the area of state-space planning. For partial-order, plan-space planners goal orderings have not been investigated in much detail. Mechanisms developed for statespace planning are not directly applicable because partial-order planners do not have a current (world) state. Further, it is not completely clear how plan-space planners should make use of goal orderings. This paper describes an approach to extract goal orderings to be used by the plan-space planner CAPlan. The extraction of goal orderings is based on the analysis of an extended version of operator graphs which previously have been found useful for the analysis of interactions and recursion of plan-space planners.

Freivalds, Karpinski and Smith [8] explored a special type of learning in the limit: identification of an unknown concept (function) by eliminating (erasing) all but one possible hypothesis (this type of learning is called co-learning). The motivation behind learning by erasing lies in the process of human and automated computer learning: often we can discard incorrect solutions much easier than to come up with the correct one. In Gödel numberings any learnable family can be learned by an erasing strategy. In this paper we concentrate on co-learning minimal programs. We show that co-learning of minimal programs, as originally defined is significantly weaker than learning minimal programs in Gödel numberings. In order to enhance the learning power

We present an approach to automating the selection of search-guiding heuris-tics that control the search conducted by a problem solver. The approach centerson representing problems with feature vectors that are vectors of numerical val-ues. Thus, similarity between problems can be determined by using a distancemeasure on feature vectors. Given a database of problems, each problem beingassociated with the heuristic that was used to solve it, heuristics to be employedto solve a novel problem are suggested in correspondence with the similaritybetween the novel problem and problems of the database.Our approach is strongly connected with instance-based learning and nearest-neighbor classification and therefore possesses incremental learning capabilities.In experimental studies it has proven to be a viable tool for achieving the finaland crucial missing piece of automation of problem solving - namely selecting anappropriate search-guiding heuristic - in a flexible way.This work was supported by the Deutsche Forschungsgemeinschaft (DFG).

This report presents the properties of a specification of the domain of process planning for rotary symmetrical workpieces. The specification results from a model for problem solving in this domain that involves different reasoners, one of which is an AI planner that achieves goals corresponding to machining workpieces by considering certain operational restrictions of the domain. When planning with SNLP (McAllester and Rosenblitt, 1991), we will show that the resulting plans have the property of minimizing the use of certain key operations. Further, we will show that, for elastic protected plans (Kambhampati et al., 1996) such as the ones produced by SNLP, the goals corresponding to machining parts of a workpiece are OE-constrained trivial serializable, a special form of trivial serializability (Barrett and Weld, 1994). However, we will show that planning with SNLP in this domain can be very difficult: elastic protected plans for machining parts of a workpiece are nonmergeable. Finally, we will show that, for sufix, prefix or sufix and prefix plans such as the ones produced by state-space planners, it is not possible to have both properties, being OEconstrained trivial serializable and minimizing the use of the key operations, at the same time.

The feature interaction problem in telecommunications systems increasingly obstructsthe evolution of such systems. We develop formal detection criteria which render anecessary (but less than sufficient) condition for feature interactions. It can be checkedmechanically and points out all potentially critical spots. These have to be analyzedmanually. The resulting resolution decisions are incorporated formally. Some prototypetool support is already available. A prerequisite for formal criteria is a formal definitionof the problem. Since the notions of feature and feature interaction are often used in arather fuzzy way, we attempt a formal definition first and discuss which aspects can beincluded in a formalization (and therefore in a detection method). This paper describeson-going work.

Collecting Experience on the Systematic Development of CBR Applications using the INRECA Methodology
(1999)

This paper presents an overview of the INRECA methodology for building and maintaining CBR applications. This methodology supports the collection and reuse of experience on the systematic development of CBR applications. It is based on the experience factory and the software process modeling approach from software engineering. CBR development experience is documented using software process models and stored in different levels of generality in a three-layered experience base. Up to now, experience from 9 industrial projects enacted by all INRECA II partners has been collected.

Automata-Theoretic vs. Property-Oriented Approaches for the Detection of Feature Interactions in IN
(1999)

The feature interaction problem in Intelligent Networks obstructs more and morethe rapid introduction of new features. Detecting such feature interactions turns out to be a big problem. The size of the systems and the sheer computational com-plexity prevents the system developer from checking manually any feature against any other feature. We give an overview on current (verification) approaches and categorize them into property-oriented and automata-theoretic approaches. A comparisonturns out that each approach complements the other in a certain sense. We proposeto apply both approaches together in order to solve the feature interaction problem.

This paper presents a completely systematic design procedure for asynchronous controllers.The initial step is the construction of a signal transition graph (STG, an interpreted Petri net) ofthe dialog between data path and controller: a formal representation without reference to timeor internal states. To implement concurrently operating control structures, and also to reducedesign effort and circuit cost, this STG can be decomposed into overlapping subnets. A univer-sal initial solution is then obtained by algorithmically constructing a primitive flow table fromeach component net. This step links the procedure to classical asynchronous design, in particu-lar to its proven optimization methods, without restricting the set of solutions. In contrast toother approaches, there is no need to extend the original STG intuitively.

An interrupter for use in a daisy-chained VME bus interrupt system has beendesigned and implemented as an asynchronous sequential circuit. The concur-rency of the processes posed a design problem that was solved by means of asystematic design procedure that uses Petri nets for specifying system and in-terrupter behaviour, and for deriving a primitive flow table. Classical designand additional measures to cope with non-fundamental mode operation yieldeda coded state-machine representation. This was implemented on a GAL 22V10,chosen for its hazard-preventing structure and for rapid prototyping in studentlaboratories.

Location problems with Q (in general conflicting) criteria are considered. After reviewing previous results of the authors dealing with lexicographic and Pareto location the main focus of the paper is on max-ordering locations. In these location problems the worst of the single objectives is minimized. After discussing some general results (including reductions to single criterion problems and the relation to lexicographic and Pareto locations) three solution techniques are introduced and exemplified using one location problem class, each: The direct approach, the decision space approach and the objective space approach. In the resulting solution algorithms emphasis is on the representation of the underlying geometric idea without fully exploring the computational complexity issue. A further specialization of max-ordering locations is obtained by introducing lexicographic max-ordering locations, which can be found efficiently. The paper is concluded by some ideas about future research topics related to max-ordering location problems.

In this paper we deal with locating a line in the plane. If d is a distance measure our objective is to find a straight line l which minimizes f(l) of g(l) (see the paper for the definition of these functions). We show that for all distance measures d derived from norms, one of the lines minimizing f(l) contains at least two of the existing facilities. For the center objective we always get an optimal line which is at maximum distance from at least three of the existing facilities. If all weights are equal, there is an optimal line which is parallel to one facet of the convex hull of the existing facilities.

In this paper relationships between Pareto points and saddle points in multiple objective programming are investigated. Convex and nonconvex problems are considered and the equivalence between Pareto points and saddle points is proved in both cases. The results are based on scalarizations of multiple objective programs and related linear and augmented Lagrangian functions. Partitions of the index sets of objectives and constranints are introduced to reduce the size of the problems. The relevance of the results in the context of decision making is also discussed.

Discrete Decision Problems, Multiple Criteria Optimization Classes and Lexicographic Max-Ordering
(1999)

The topic of this paper are discrete decision problems with multiple criteria. We first define discrete multiple criteria decision problems and introduce a classification scheme for multiple criteria optimization problems. To do so we use multiople criteria optimization classes. The main result is a characterization of the class of lexicographic max-ordering problems by two very useful properties, reduction and regularity. Subsequently we discuss the assumptions under which the application of this specific MCO class is justified. Finally we provide (simple) solution methods to find optimal decisions in the case of discrete multiple criteria optimization problems.

In line location problems the objective is to find a straight line which minimizes the sum of distances, or the maximum distance, respectively to a given set of existing facilities in the plane. These problems have well solved. In this paper we deal with restricted line location problems, i.e. we have given a set in the plane where the line is not allowed to pass through. With the help of a geometric duality we solve such problems for the vertical distance and then extend these results to block norms and some of them even to arbitrary norms. For all norms we give a finite candidate set for the optimal line.

In this survey we deal with the location of hyperplanes in n-dimensional normed spaces, i.e., we present all known results and a unifying approach to the so-called median hyperplane problem in Minkowski spaces. We describe how to find a hyperplane H minimizing the weighted sum f(H) of distances to a given, finite set of demand points. In robust statistics and operations research such an optimal hyperplane is called a median hyperplane.After summarizing the known results for the Euclidean and rectangular situation, we show that for all distance measures d derived from norms one of the hyperplanes minimizing f(H) is the affine hull of n of the demand points and, moreover, that each median hyperplane is a halving one (in a sense defined below) with respect to the geiven point set. Also an independence of norm result for finding optimal hyperplanes with fixed slope will be given. Furthermore we discuss how these geometric criteria can be used for algorithmical approaches to median hyperplanes, with an extra discussion for the case of polyhedral norms. And finally a characterizatio of all smooth norms by a sharpened incidence criterion for median hyperplanes is mentioned.

A large set of criteria to evaluate formal methods for reactive systems is presented. To make this set more comprehensible, it is structured according to a Concept-Model of formal methods. It is made clear that it is necessary to make the catalogue more specific before applying it. Some of the steps needed to do so are explained. As an example the catalogue is applied within the context of the application domain building automation systems to three different formal methods: SDL, statecharts, and a temporallogic.

Today, the worlds and terminologies of mechanical engineering and software engineering coexist, but they do not always work together seamlessly. Both worlds have developed their own separate formal vocabulary for expressing their concepts as well as for capturing and communicating their respective domain knowledge. But, these two vocabularies are not unified, interwoven, or at least interconnected in a reasonable manner. Thus, the subject of this paper is a comparison of the vocabularies of the two fields, namely feature technology from the area of mechanical engineering and software design patterns from the software engineering domain. Therefore, a certain amount of definitions, history, examples, etc. is presented for features as well as for design patterns. After this, an analysis is carried out to identify analogies and differences. The main intention of this paper is to inform both worlds - mechanical and software engineering - about the other side's terminology and to start a discussion about potential mutual benefits and possibilities to bridge the gap between these two worlds, e.g. to improve the manageability of CAx product development processes.

In this paper we prove a reduction result for the number of criteria in convex multiobjective optimization. This result states that to decide wheter a point x in the decision space is pareto optimal it suffices to consider at most n? criteria at a time, where n is the dimension of the decision space. The main theorem is based on a geometric characterization of pareto, strict pareto and weak pareto solutions

Ramsey Numbers of K_m versus (n,k)-graphs and the Local Density of Graphs not Containing a K_m
(1999)

In this paper generalized Ramsey numbers of complete graphs K_m versus the set langle ,n,k angle of (n,k)-graphs are investigated. The value of r(K_m,langle n,k angle) is given in general for (relative to n) values of k small compared to n using a correlation with Turan numbers. These generalized Ramsey numbers con be used to determine the local densities of graphs not containing a subgraph K_m.

The Weber problem for a given finite set of existing facilities {cal E}x = {Ex_1,Ex_2, ... ,Ex_M} subset R^2 with positive weights w_m (m = 1, ... ,M) is to find a new facility X* in R^2 such that sum_{m=1}^{M} w_{m}d(X,Ex_m) is minimized for some distance function d. In this paper we consider distances defined by polyhedral gauges. A variation of this problem is obtained if barriers are introduced which are convex polygonal subsets of the plane where neither location of new facilities nor traveling is allowed. Such barriers like lakes, military regions, national parks or mountains are frequently encountered in practice.From a mathematical point of view barrier problems are difficult, since the prensence of barriers destroys the convexity of the objective function. Nevertheless, this paper establishes a descretization result: One of the grid points in the grid defined by the existing facilities and the fuundamental directions of the gauge distances can be proved to be an optimal location. Thus the barrier problem can be solved with a polynomial algorithm.

Kernel smoothing in nonparametric autoregressive schemes offers a powerful tool in modelling time series. In this paper it is shown that the bootstrap can be used for estimating the distribution of kernel smoothers. This can be done by mimicking the stochastic nature of the whole process in the bootstrap resampling or by generating a simple regression model. Consistency of these bootstrap procedures will be shown.

In this paper we consider generalizations of multifacility location problems in which as an additional constraint the new facilities are not allowed to be located in a presprcified region. We propose several different solution schemes for this non-convex optimization problem. These include a linear programming type approach, penalty approaches and barrier approaches. Moreover, structural results as well as illustratrive examples showing the difficulties of this problem are presented

To present the decision maker's (DM) preferences in multicriteria decision problems as a partially ordered set is an effective method to catch the DM's purpose and avoid misleading results. Since our paper is focused on minimal path problems, we regard the ordered set of edges (E,=). Minimal paths are defined in repect to power-ordered sets which provides an essential tool to solve such problems. An algorithm to detect minimal paths on a multicriteria minimal path problem is presented

Let P be a probability measure of the real line R such that each of the product measures P^{otimes n} assigns the value 1/2 to every half space in R^{n} having the origin as a boundary point. Then P is symmetric.Example: A strictly stable law on R is symmetric iff it has median zero. The treated symmetry problem is related to the problem of characterizing the distribution of X_1 by the distribution of (X_2 + X_1, ... ,X_n + X_1), with X_1, ... ,X_n being independent and identically distributed random variables.

In continous location problems we are given a set of existing facilities and we are looking for the location of one or several new facilities. In the classical approaches weights are assigned to existing facilities expressing the importance of the new facilities for the existing ones. In this paper, we consider a pointwise defined objective function where the weights are assigned to the existing facilities depending on the location of the new facility. This approach is shown to be a generalization of the median, center and centdian objective functions. In addition, this approach allows to formulate completely new location models. Efficient algorithms as well as structure results for this algebraic approach for location problems are presented. Extensions to the multifacility and restricted case are also considered.

In this paper we consider the problem of optimizing a piecewise-linear objective function over a non-convex domain. In particular we do not allow the solution to lie in the interior of a prespecified region R. We discuss the geometrical properties of this problems and present algorithms based on combinatorial arguments. In addition we show how we can construct quite complicated shaped sets R while maintaining the combinatorial properties.

In this paper we deal with the determination of the whole set of Pareto-solutions of location problems with respect to Q general criteria. These criteria include as particular instances median, center or cent-dian objective functions. The paper characterizes the set of Pareto-solutions of all these multicriteria problems. An efficient algorithm for the planar case is developed and its complexity is established. the proposed approach is more general than the previously published approaches to multicriteria location problems and includes almost all of them as particular instances.

The computational complexity of combinatorial multiple objective programming problems is investigated. NP-completeness and #P-completeness results are presented. Using two definitions of approximability, general results are presented, which outline limits for approximation algorithms. The performance of the well known tree and Christofides' heuristics for the TSP is investigated in the multicriteria case with respect to the two definitions of approximability.

Convex Operators in Vector Optimization: Directional Derivatives and the Cone of Decrease Directions
(1999)

The paper is devoted to the investigation of directional derivatives and the cone of decrease directions for convex operators on Banach spaces. We prove a condition for the existence of directional derivatives which does not assume regularity of the ordering cone K. This result is then used to prove that for continuous convex operators the cone of decrease directions can be represented in terms of the directional derivatices . Decrease directions are those for which the directional derivative lies in the negative interior of the ordering cone K. Finally, we show that the continuity of the convex operator can be replaced by its K-boundedness.

The notion of the balance number introduced in [3,page 139] through a certain set contraction procedure for nonscalarized multiobjective global optimization is represented via a min-max operation on the data of the problem. This representation yields a different computational procedure for the calculation of the balance number and allows us to generalize the approach for problems with countably many performance criteria.

In this paper we consider the problem of locating one new facility in the plane with respect to a given set of existing facility where a set of polygonal barriers restricts traveling. This non-convex optimization problem can be reduced to a finite set of convex subproblems if the objective function is a convex function of the travel distances between the new and the existing facilities (like e.g. the Median and Center objective functions). An exact Algorithm and a heuristic solution procedure based on this reduction result are developed.

Let rC and rD be two convexdistance funtions in the plane with convex unit balls C and D. Given two points, p and q, we investigate the bisector, B(p,q), of p and q, where distance from p is measured by rC and distance from q by rD. We provide the following results. B(p,q) may consist of many connected components whose precise number can be derived from the intersection of the unit balls, C nd D. The bisector can contain bounded or unbounded 2-dimensional areas. Even more surprising, pieces of the bisector may appear inside the region of all points closer to p than to q. If C and D are convex polygons over m and m vertices, respectively, the bisector B(p,q) can consist of at most min(m,n) connected components which contain at most 2(m+n) vertices altogether. The former bound is tight, the latter is tight up to an additive constant. We also present an optimal O(m+n) time algorithm for computing the bisector.

In planar location problems with barriers one considers regions which are forbidden for the siting of new facilities as well as for trespassing. These problems areimportant since they reflect various real-world situations.The resulting mathematical models have a non-convex objectivefunction and are therefore difficult to tackle using standardmethods of location theory even in the case of simple barriershapes and distance funtions.For the case of center objectives with barrier distancesobtained from the rectilinear or Manhattan metric it is shown that the problem can be solved by identifying a finitedominating set (FDS) the cardinality of which is bounded bya polynomial in the size of the problem input. The resultinggenuinely polynomial algorithm can be combined with bound computations which are derived from solving closely connectedrestricted location and network location problems.It is shown that the results can be extended to barrier center problems with respect to arbitrary block norms having fourfundamental directions.

In this paper we deal with an NP-hard combinatorial optimization problem, the k-cardinality tree problem in node weighted graphs. This problem has several applications , which justify the need for efficient methods to obtain good solutions. We review existing literature on the problem. Then we prove that under the condition that the graph contains exactly one trough, the problem can be solved in ploynomial time. For the general NP-hard problem we implemented several local search methods to obtain heuristics solutions, which are qualitatively better than solutions found by constructive heuristics and which require significantly less time than needed to obtain optimal solutions. We used the well known concepts of genetic algorithms and tabu search with useful extensions. We show that all the methods find optimal solutions for the class of graphs containing exactly one trough. The general performance of our methods as compared to other heuristics is illustrated by numerical results.

Given a finite set of points in the plane and a forbidden region R, we want to find a point X not an element of int(R), such that the weighted sum to all given points is minimized. This location problem is a variant of the well-known Weber Problem, where we measure the distance by polyhedral gauges and allow each of the weights to be positive or negative. The unit ball of a polyhedral gauge may be any convex polyhedron containing the origin. This large class of distance functions allows very general (practical) settings - such as asymmetry - to be modeled. Each given point is allowed to have its own gauge and the forbidden region R enables us to include negative information in the model. Additionally the use of negative and positive weights allows to include the level of attraction or dislikeness of a new facility. Polynomial algorithms and structural properties for this global optimization problem (d.c. objective function and a non-convex feasible set) based on combinatorial and geometrical methods are presented.

In this paper a new trend is introduced into the field of multicriteria location problems. We combine the robustness approach using the minmax regret criterion together with Pareto-optimality. We consider the multicriteria Weber location problem which consists of simultaneously minimizing a number of weighted sum-distance functions and the set of Pareto-optimal locations as its solution concept. For this problem, we characterize the Pareto-optimal solutions within the set of robust locations for the original weighted sum-distance functions. These locations have both the properties of stability and non-domination which are required in robust and multicriteria programming.

We present a mathematical knowledge base containing the factual know-ledge of the first of three parts of a textbook on semi-groups and automata,namely "P. Deussen: Halbgruppen und Automaten". Like almost all math-ematical textbooks this textbook is not self-contained, but there are somealgebraic and set-theoretical concepts not being explained. These concepts areadded to the knowledge base. Furthermore there is knowledge about the nat-ural numbers, which is formalized following the first paragraph of "E. Landau:Grundlagen der Analysis".The data base is written in a sorted higher-order logic, a variant of POST ,the working language of the proof development environment OmegaGamma mkrp. We dis-tinguish three different types of knowledge: axioms, definitions, and theorems.Up to now, there are only 2 axioms (natural numbers and cardinality), 149definitions (like that for a semi-group), and 165 theorems. The consistency ofsuch knowledge bases cannot be proved in general, but inconsistencies may beimported only by the axioms. Definitions and theorems should not lead to anyinconsistency since definitions form conservative extensions and theorems areproved to be consequences.

The problem of finding an optimal location X* minimizing the maximum Euclidean distance to existing facilities is well solved by e.g. the Elzinga-Hearn algorithm. In practical situations X* will however often not be feasible. We therefore suggest in this note a polynomial algorithm which will find an optimal location X^F in a feasible subset F of the plane R^2

In the following, we discuss a procedure for interpolating a spatial-temporal stochastic process. We stick to a particular, moderately general model but the approach can be easily transered to other similar problems. The original data, which motivated this work, are measurements of gas concentrations (SO2, NO, O2) and several meteorological parameters (temperature, sun radiation, procipitation, wind speed etc.). These date have been and are still recorded twice every hour at several irregularly located places in the forests of the state Rheinland-Pfalz as part of a program monitoring the air pollution in the forests.

We consider a multiple objective linear program (MOLP) max{Cx|Ax = b,x in N_{0}^{n}} where C = (c_ij) is the p x n - matrix of p different objective functions z_i(x) = c_{i1}x_1 + ... + c_{in}x_n , i = 1,...,p and A is the m x n - matrix of a system of m linear equations a_{k1}x_1 + ... + a_{kn}x_n = b_k , k=1,...,m which form the set of constraints of the problem. All coefficients are assumed to be natural numbers or zero. The set M of admissable solutions {hat x} is an admissible solution such that there exists no other admissable solution x' with C{hat x} Cx'. The efficient solutions play the role of optimal solutions for the MOLP and it is our aim to determine the set of all efficient solutions

In this paper we give the definition of a solution concept in multicriteria combinatorial optimization. We show how Pareto, max-ordering and lexicographically optimal solutions can be incorporated in this framework. Furthermore we state some properties of lexicographic max-ordering solutions, which combine features of these three kinds of optimal solutions. Two of these properties, which are desirable from a decision maker" s point of view, are satisfied if and only of the solution concept is that of lexicographic max-ordering.