Characterisation and testing of micro specimen

Currently for the design of micro components often no reliable material data is available. Therefore in the German Collaborative Research Centre (SFB) 499 [1] metallic and ceramic micro specimen that are manufactured by different micro moulding techniques as micro casting, slip casting or micro powder injection moulding are investigated with respect to their microstructure, mechanical and tribological properties. As metal was investigated a AuAgCu-alloy named Stabilor G and as ceramic was investigated ZrO₂. Additionally the wear behaviour of mould inserts made of different materials as X38CrMoV5–1, Ni and Cu63Zn37 and the modifications of near surface microstructures due to micro milling in X38CrMoV5–1 in different heat treatment states are presented.Abbreviations R_b Bending strength of one specimen - ₀ Characteristic beinding strength of a batch after Weibull - m_corr Weibull exponent corrected by the Maximum Likelihood Method - P_F Probability of failure - Friction coefficient - W Linear amount of wear - f DeflectionThe authors are grateful for the support of the research work in the SFB499 Design, production and quality assurance of moulded micro components made of metallic and ceramic materials by the Deutsche Forschungsgemeinschaft.     

Efficient monitoring of safety properties

The problem of testing whether a finite execution trace of events generated by an executing program violates a linear temporal logic (LTL) formula occurs naturally in runtime analysis of software. Two efficient algorithms for this problem are presented in this paper, both for checking safety formulae of the form always P, where P is a past-time LTL formula. The first algorithm is implemented by rewriting, and the second synthesizes efficient code from formulae. Further optimizations of the second algorithm are suggested, reducing space and time consumption. Special operators suitable for writing succinct specifications are discussed and shown to be equivalent to the standard past-time operators. This work is part of NASAs PathExplorer project, the objective of which is to construct a flexible framework for efficient monitoring and analysis of program executions.     

Anfragesprachen für das Semantic Web

Das Semantic Web wird seit dem visionären Artikel von Berners-Lee, Hendler und Lassila [3] allgemein als die nächste Evolutionsstufe des World Wide Web betrachtet. * Vorschläge an Prof.Dr. Frank Puppe <puppe@informatik.uni-wuerzburg.de> oder Dieter Steinbauer <dieter.steinbauer@schufa.de>Alle Aktuellen Schlagwörter seit 1988 finden Sie unter: www.ai-wuerzburg.de/as     

A 2n−2 step algorithm for routing in ann ×n array with constant-size queues

In this paper we describe a deterministic algorithm for solving any 1–1 packet-routing problem on ann ×n mesh in 2n–2 steps using constant-size queues. The time bound is optimal in the worst case. The best previous deterministic algorithm for this problem required time 2n+(n/q) using queues of size (q) for any 1qn, and the best previous randomized algorithm required time 2n+(logn) using constant-size queues.This research was supported by the Clear Center at UTD, DARPA Contracts N00014-91-J-1698 and N00014-92-J-1799, Air Force Contract F49620-92-J-0125, Army Contract DAAL-03-86-K-0171, an NSF Presidential Young Investigator Award with matching funds from AT&T and IBM, and by the Texas Advanced Research Program under Grant No. 3972. A preliminary version of this paper appeared in [5].     

Maximum entropy two-station cyclic queues with multiple general servers

Summary The efficient implementation and extension of various approximate methods for general queueing networks require the study of two-station cyclic queues. In this paper maximum entropy formalism is used to analyse two-station cyclic queues with multiple general servers and a fixed number of jobs. New robust one step recursions for the queue length distribution are derived and asymptotic connections to infinite capacity queues are established. Links with Birth-Death and global balance solutions are determined and extensions to load dependent servers with Bernoulli feedback are presented. Numerical examples provide useful information on how critically system behaviour is affected by the distributional form of service times and simple bounds for typical performance measures such as throughout and mean queue length are defined. Moreover, the utility of the work as a building block for the approximate analysis of a general central server model is demonstrated.Some of the material included in this paper has been orally presented to the International Workshop on Computer Performance Evaluation, 28–30 April 1986, Sophia-Antipolis (INRIA), France [1]This work is jointly supported by Science and Engineering Research Council (SERC), UK and Metron Technology Ltd., UK, under grants GR/D/12422 and GR/AA/772, respectively     

Arithmetiken für komplexe Kreise

Zusammenfassung Drei Einschließungskreise werden definiert für Mengen, die bei Addition, Subtraktion, Multiplikation und Division komplexer Kreise entstehen. Die algebraische Struktur der dadurch erzeugten Arithmetiken und die Radien der Einschließungskreise werden verglichen. Neben zwei von N. Krier [5] dargestellten Arithmetiken sind die kleinsten Einschließungskreise angegeben, durch die die algebraische Struktur vonP() voll erhalten bleibt (optimale Kreisarithmetik). Bei der Berechnung einer inversen Matrix mit Arithmetiken für komplexe Kreise und achsenparallele Rechtecke werden Fehlerschranken und Rechenzeiten angegeben.

---

Arithmetic procedures for complex circles

Three enclosing circles are defined for sets that are obtained by addition, subtraction, multiplication and division of complex circles. The algebraic structures resulting from these arithmetic procedures and the radii of the enclosing circles are compared. In addition to the two arithmetic procedures described by N. Krier [5], the smallest enclosing circles are defined which preserve the algebraic structure ofP() (optimal circular arithmetic). Calculations of an inverse matrix are made by arithmetic procedures for complex circles and axially-parallel rectangles, and the error bounds and computation times are compared.

     

Structural analysis of the complexity of inverse functions

For a given polynomial-time computable honest function, the complexity of its max inverse function is compared with that of the other inverse functions. Two structural results are shown which suggest that the max inverse function is not the easiest.The preliminary version of this paper was presented at the International Symposium SIGAL 90 [WT]. Osamu Watanabe was supported in part by a Grant in Aid for Scientific Research of the Ministry of Education, Science and Culture of Japan under Grant-in-Aid for Co-operative Research (A) 02302047 (1990).     

Thiele Rational Interpolation for the Numerical Computation of the Reversible Randles–Sevcik Function in Electrochemistry

This paper uses Thiele rational interpolation to derive a simple method for computing the Randles–Sevcik function ^1/2(x), with relative error at most 1.9 × 10^–5 for – < x < . We develop a piecewise approximation method for the numerical computation of ^1/2(x) on the union (–, –10) [–10, 10] (10, ). This approximation is particularly convenient to employ in electrochemical applications where four significant digits of accuracy are usually sufficient. Although this paper is primarily concerned with the approximation of the Randles–Sevcik function, some examples are included that illustrate how Thiele rational interpolation can be employed to generate useful approximations to other functions of interest in scientific work.     

On the number of Eulerian orientations of a graph

An Eulerian orientation of an undirected Eulerian graph is an orientation of the edges of the graph such that for every vertex the in-degree is equal to the out-degree. Eulerian orientations are natural flow-like structures, and Welsh has pointed out that computing their number corresponds to evaluating the Tutte polynomial at the point (0, –2) [JVW], [Wl], and is further equivalent to evaluating ice-type partition functions in statistical physics [W2]. In this paper we resolve the complexity of counting the number of Eulerian orientations of an arbitrary Eulerian graph.We give an efficient randomized approximation algorithm for counting Eulerian orientations of any Eulerian graph. Our algorithm is based on a reduction to counting perfect matchings for a class of graphs for which the methods of Broder [B], Jerrum and Sinclair [JS1], and others [DL] [DS] apply. A crucial step of the reduction is the Monotonicity Lemma (Lemma 3.1) which is of independent combinatorial interest. Roughly speaking, the Monotonicity Lemma establishes the intuitive fact that increasing the number of constraints applied on a flow problem cannot increase the number of solutions. The proof of the lemma involves a new decomposition technique which decouples problematically overlapping structures (a recurrent obstacle in handling large combinatorial populations) and allows detailed enumeration arguments. As a by-product, we exhibit a class of graphs for which perfect and near-perfect matchings are polynomially related, and hence the permanent can be approximated, for reasons other than short augmenting paths (previously the only known approach).We also give the complementary hardness result, namely, that counting exactly Eulerian orientations is #P-complete. Finally, we provide some connections with counting Euler tours.     

Über die Konvergenz des Relaxationsverfahrens bei nicht-negativen und diagonaldominanten Matrizen

Zusammenfassung In der folgenden Arbeit werden zunächst die Begriffe Gesamtschrittverfahren, Einzelschrittverfahren und Relaxationsverfahren allgemein formuliert und dann auf allgemeine lineare Gleichungssysteme angewandt. Im Spezialfall einer Matrix mit verschwindender Hauptdiagonale erhält man so die bekanntenJacobi-, Gauss-Seidel- und Relaxationsverfahren. Satz 1 macht eine Aussage über die Konvergenz des Einzelschrittverfahrens bei allgemeinen, nicht-negativen Matrizen. Der Beweis verläuft ähnlich wie in einem bereits 1948 vonStein undRosenberg [2] behandelten Spezialfall. Als Korollar ergibt sich eine Aussage über die Konvergenz des Relaxationsverfahrens bei nicht-negativen Matrizen. Es wird ferner der Satz 2 über die Konvergenz des Relaxationsverfahrens bei diagonaldominanten Matrizen beweisen.

---

Summary In this paper we give a general definition what is meant by total-step-, single-step- and successive relaxation iterative method and we apply these concepts on systems of linear equations. In the special case of a matrix with zero diagonal entries we obtain the well knownJacobi-, Gauss-Seidel- and Relaxation iterative method. Theorem 1 gives conditions for the convergence of the singlestep-iterative method for general, non-negative matrices. The proof is similar to that given byStein andRosenberg in [2] (1948) for a special case. A corollary gives conditions for the convergence of the relaxation-iterative method for non-negative matrices. Further on we prove theorem 2 about the convergence of the relaxation-iterative method with diagonally dominant matrices.

     

High-Speed Tools for Global Information Management. II. Specifications and Uses of the Transparent Query Language (TQL)

This part, PART IIB [2], of the document HIGH-SPEED TOOLS FOR GLOBAL INFORMATION MANAGEMENT. II. Specifications and Uses of the Transparent Query Language (TQL) [1–6] contains the specifications for the operations that provide the arithmetic capabilities for Transparent Query Language. PART IIB references PART IIA [1] and PART IIC [3]. Concise definitions of Transparent Query Language terms, Conclusions and Acknowledgments are given in PART IIF [6].     

Quasi-static and cyclic testing of specimens with high aspect ratios produced by micro-casting and micro-powder-injection-moulding

 The presented investigations of material properties of micro-components have been carried out in one project of the DFG Collaborative Research Centre (SFB) 499 “Development, production and quality assurance of moulded micro-components made out of metallic and ceramic materials” [SFB01]. The aim of this SFB is to develop production methods for micro-components in large-, middle and short-batches, where the applied metallic and ceramic materials can sustain high stresses and are wear-resistant, e.g. in relation to plastics. A micro-turbine and a sun-and-planet gearing with three stages (outside diameter: 1.9 mm; already realised in plastic [THü99]) are planned as a demonstration device. However, for the design of such micro-components, no reliable data for material states in small dimensions are available. Therefore, bending-specimens made out of micro-cast Stabilor G and out of micro-powder-injection-moulded ZrO₂ were investigated with respect to their behaviour under quasi-static as well as under cyclic loading. Received: 10 August 2001/Accepted: 24 September 2001     

Design of experiments to detect nonnegligible variables in a linear model

The design of sifting experiments is considered. The properties of superoptimal designs discovered by Meshalkin [3, 4] are investigated.Translated from Kibernetika, No. 3, pp. 91–97, May–June, 1991.     

Closed-form solutions to image flow equations for 3D structure and motion

A major source of three-dimensional (3D) information about objects in the world is available to the observer in the form of time-varying imagery. Relative motion between textured objects and the observer generates a time-varying optic array at the image, from which image motion of contours, edge fragments, and feature points can be extracted. These dynamic features serve to sample the underlying image flow field. New, closed-form solutions are given for the structure and motion of planar and curved surface patches from monocular image flow and its derivatives through second order. Both planar and curved surface solutions require at most, the solution of a cubic equation. The analytic solution for curved surface patches combines the transformation of Longuet-Higgins and Prazdny [25] with the planar surface solution of Subbarao and Waxman [43]. New insights regarding uniqueness of solutions also emerge. Thus, the structure-motion coincidence of Waxman and Ullman [54] is interpreted as the duality of tangent plane solutions. The multiplicity of transformation angles (up to three) is related to the sign of the Gaussian curvature of the surface patch. Ovoid patches (i.e., bowls) are shown to possess a unique transform angle, though they are subject to the local structure-motion coincidence. Thus, ovoid patches almost always yield a unique 3D interpretation. In general, ambiguous solutions can be resolved by requiring continuity of the solution over time.The support of the Defense Advanced Research Projects Agency and the U.S. Army Night Vision Laboratory under Contract DAAK70-83-K-0018 (DARPA Order 3206) is gratefully acknowledged.     

Deterministic sequential functions

The simple rational partial functions accepted by generalized sequential machines are shown to coincide with the compositions _P ^–1 , where _P consists of the prefix codings. The rational functions accepted by generalized sequential machines are proved to coincide with the compositions _P ^–1 , where is the family of endmarkers and is the family of removals of endmarkers. (The compositions are read from left to right). We also show that _P ^–1 is the family of the subsequential functions.This work was partially supported by the Esprit Basic Research Action Working Group No. 3166 ASMICS, the CNRS and the Academy of Finland     

On Steiner minimal trees withLp distance

LetL _p be the plane with the distanced _p (A ₁ ,A ₂ ) = (¦x ₁ –x ₂¦ ^p + ¦y₁ –y ₂¦^p)^/1p wherex _i andy _i are the cartesian coordinates of the pointA _i . LetP be a finite set of points inL _p . We consider Steiner minimal trees onP. It is proved that, for 1 <p < , each Steiner point is of degree exactly three. Define the Steiner ratio _p to be inf{L _s (P)/L _m (P)¦PL _p } whereL _s (P) andL _m (P) are lengths of the Steiner minimal tree and the minimal spanning tree onP, respectively. Hwang showed ₁ = 2/3. Chung and Graham proved ₂ > 0.842. We prove in this paper that {} = 2/3 and (2/2)_{12 p} 3/2 for anyp.This work was supported in part by the National Science Foundation of China and the President Foundation of Academia Sinica.     

On closure properties of bounded two-sided error complexity classes

We show that if a complexity classC is closed downward under polynomial-time majority truth-table reductions ( _mtt ^p ), then practically every other polynomial closure property it enjoys is inherited by the corresponding bounded two-sided error class BP[C]. For instance, the Arthur-Merlin game class AM [B1] enjoys practically every closure property of NP. Our main lemma shows that, for any relativizable classD which meets two fairly transparent technical conditions, we haveC ^BP[C] BP[D ^C]. Among our applications, we simplify the proof by Toda [Tol], [To2] that the polynomial hierarchy PH is contained in BP[P]. We also show that relative to a random oracleR, PH ^R is properly contained in P ^R .The first author was supported in part by NSF Grant CCR-9011248 and the second author was supported in part by NSF Grant CCR-89011154.     

Multiscale modeling of developmental processes

In contrast to most synthetic neural nets, biological neural networks have a strong component of genetic determination which acts before and during experiential learning. Three broad levels of phenomena are present: long-term evolution, involving crossover as well as point mutation; a developmental process mapping genetic information to a set of cells and their internal states of gene expression (genotype to phenotype); and the subsequent synaptogenesis. We describe a very simple mathematical idealization of these three levels which combines the crossover search method of genetic algorithms with the developmental models used in our previous work on genetic or recursively generated artificial neural nets [18] (and elaborated into a connectionist model of biological development [19]). Despite incorporating all three levels (evolution on genes; development of cells; synapse formation) the model may actually be far cheaper to compute with than a comparable search directly in synaptic weight space.Supported in part by grant 1-RO1-RR07801 from the National Institutes of Health of the US.Supported in part by the US Air Force Office of Scientific Research under grant US AFOSR 88-0240.     

High-Speed Tools for Global Information Management. II. Specifications and Uses of the Transparent Query Language (TQL)

In this part, PART IIE [5], of the document HIGH-SPEED TOOLS FOR GLOBAL INFORMATION MANAGEMENT. II. Specifications and Uses of the Transparent Query Language (TQL) [1–6] the conversion of queries coded in SQL, Relational Algebra, QUEL and Query-By-Examples (QBE) to TQL are demonstrated. PART IIE references PART IIA [1], PART IIB [2], PART IID [3] and PART IIF [6]. Concise definitions of Transparent Query Language terms, Conclusions and Acknowledgments are given in PART IIF [6].     

Two spurious varieties of compositionality

The paper examines an alleged distinction claimed to exist by Van Gelder between two different, but equally acceptable ways of accounting for the systematicity of cognitive output (two varieties of compositionality): concatenative compositionality vs. functional compositionality. The second is supposed to provide an explanation alternative to the Language of Thought Hypothesis. I contend that, if the definition of concatenative compositionality is taken in a different way from the official one given by Van Gelder (but one suggested by some of his formulations) then there is indeed a different sort of compositionality; however, the second variety is not an alternative to the language of thought in that case. On the other hand, if the concept of concatenative compositionality is taken in a different way, along the lines of Van Gelder's explicit definition, then there is no reason to think that there is an alternative way of explaining systematicity.This paper has its origin in very helpful and stimulating discussions with Pepa Toribio. I would like to express my gratitude also to Ned Block, Josep Corbí, Joe Lau, Begoña Navarrete, David Pineda, Ignacio Vicario and an anonymous referee for Minds and Machines for valuable comments that led to improvements. A previous version of the paper was presented at the third conference of the European Society for Philosophy and Psychology held in Paris, 1–4 September 1994, where I benefited from comments by G. Rey and J. Higginbotham. Finally, I thank Michael Maudsley for his careful revision of the grammar. Research for this paper has been funded by the Spanish Government's DGICYT, Ministry of Education, as part of the research project PB93-1049-C03-01.