Minimization of norms and logarithmic norms by diagonal similarities

It is a commonly occurring problem to find good norms · or logarithmic norms (·) for a given matrix in the sense that they should be close to respectively the spectral radius (A) and the spectral abscissa (A). Examples may be the certification thatA is convergent, i.e. (A)A<1 or stable, i.e. (A)(A)<0. Often the ordinary norms do not suffice and one would like to try simple modifications of them such as using an ordinary norm for a diagonally transformed matrix. This paper treats this problem for some of the ordinary norms.

---

Minimisierung von Normen und Logarithmischen Normen durch Diagonale Transformationen

Zusammenfassung Ein oft vorkommendes praktisches Problem ist die Konstruktion von guten Normen · und logarithmischen Normen (·) für eine gegebene MatrixA. Mit gut wird dann verstanden, daß A den Spektralradius (A)=max |₁| und (A) die Spektralabszisse (A)=max Re _i gut approximieren. Beispiele findet man für konvergente Matrizen wo (A)A<1 gewünscht ist, und für stabile Matrizen wo (A)(A)<0 zu zeigen ist. Wir untersuchen hier, wie weit man mit Diagonaltransformationen und dengewöhnlichsten Normen kommen kann.

     

On characterizations of recursively enumerable languages

Summary Geffert has shown that earch recursively enumerable languageL over can be expressed in the formL{h(x) ^–1 g(x)x in ⁺} ^* where is an alphabet andg, h is a pair of morphisms. Our purpose is to give a simple proof for Geffert's result and then sharpen it into the form where both of the morphisms are nonerasing. In our method we modify constructions used in a representation of recursively enumerable languages in terms of equality sets and in a characterization of simple transducers in terms of morphisms. As direct consequences, we get the undecidability of the Post correspondence problem and various representations ofL. For instance,L =(L ₀) ^* whereL ₀ is a minimal linear language and is the Dyck reductiona, A.     

On computing Boolean connectives of characteristic functions

This paper is a study of the existence of polynomial time Boolean connective functions for languages. A languageL has an AND function if there is a polynomial timef such thatf(x,y) L x L andy L. L has an OR function if there is a polynomial timeg such thatg(x,y) xL oryL. While all NP complete sets have these functions, Graph Isomorphism, which is probably not complete, is also shown to have both AND and OR functions. The results in this paper characterize the complete sets for the classes D^p and p^SAT[O(logn)] in terms of AND and OR and relate these functions to the structure of the Boolean hierarchy and the query hierarchies. Also, this paper shows that the complete sets for the levels of the Boolean hierarchy above the second level cannot have AND or OR unless the polynomial hierarchy collapses. Finally, most of the structural properties of the Boolean hierarchy and query hierarchies are shown to depend only on the existence of AND and OR functions for the NP complete sets.The first author was supported in part by NSF Research Grants DCR-8520597 and CCR-88-23053, and by an IBM Graduate Fellowship.     

On structured perturbations for two classes of linear infinite-dimensional systems

This paper considers two classes of infinite-dimensional systems described by an abstract differential equationx (t) = (A + BC)x(t),x(0) =x ₀, on a Hilbert space, whereA, B, C are linear, possibly unbounded operators and is an unknown, linear, bounded perturbation. The two classes of systems are defined in terms of properties imposed on the triple (A, B, C). It is proved that for every the perturbed system (A + EF, B, C) inherits all the properties of the unperturbed system {A, B, C}) if (A, E, F) and {A, B, F} are in the same class.     

A predicate transformer for the progress property ‘to-always’

The temporal property to-always has been proposed for specifying progress properties of concurrent programs. Although the to-always properties are a subset of the leads-to properties for a given program, to-always has more convenient proof rules and in some cases more accurately describes the desired system behavior. In this paper, we give a predicate transformerwta, derive some of its properties, and use it to define to-always. Proof rules for to-always are derived from the properties ofwta. We conclude by briefly describing two application areas, nondeterministic data flow networks and self-stabilizing systems where to-always properties are useful.     

The Use of Certain Equations of Mathematical Physics in Optimization of a Function on a Set. I

The results of application of potential theory to optimization are used to extend the use of (Helmholtz) diffusion and diffraction equations for optimization of their solutions (x, ) with respect to both x, and . If the aim function is modified such that the optimal point does not change, then the function (x, ) is convex in (x, for small . The possibility of using heat conductivity equation with a simple boundary layer for global optimization is investigated. A method is designed for making the solution U(x,t) of such equations to have a positive-definite matrix of second mixed derivatives with respect to x for any x in the optimization domain and any small t < 0 (the point is remote from the extremum) or a negative-definite matrix in x (the point is close to the extremum). For the functions (x, ) and U(x,t) having these properties, the gradient and the Newton–Kantorovich methods are used in the first and second stages of optimization, respectively.     

Range Estimation Is NP-Hard for ε2 Accuracy and Feasible for ε2−δ

The basic problem of interval computations is: given a function f(x ₁,..., x _n) and n intervals [x _i, x _i], find the (interval) range yof the given function on the given intervals. It is known that even for quadratic polynomials f(x ₁,..., x _n), this problem is NP-hard. In this paper, following the advice of A. Neumaier, we analyze the complexity of asymptotic range estimation, when the bound on the width of the input intervals tends to 0. We show that for small c > 0, if we want to compute the range with an accuracy c ₂, then the problem is still NP-hard; on the other hand, for every > 0, there exists a feasible algorithm which asymptotically, estimates the range with an accuracy c ^2–.     

Integration of parametric and “ad hoc” second order polymorphism in a calculus with subtyping

In this paper we define an extension ofF [CUG92] to which we add functions that dispatch on different terms according to the type they receive as argument. In other words, we enrich the explicit parametric polymorphism ofF by an explicit ad hoc polymorphism (according the classification of [Str67]). We prove that the calculus we obtain, calledF ^& , enjoys the properties of Church-Rosser and Subject Reduction and that its proof system is coherent. We also define a significant subcalculus for which the subtyping is decidable. This extension has not only a logical interest but it is strongly motivated by the foundation of a broadly used programming style: object-oriented programming. The connections betweenF ^& and object-oriented languages are widely stressed, and the modelling byF ^& of some features of the object-oriented style is described, continuing the work of [CGL96].Part of this work has appeared under the title F ^& : integrating parametric and ad hoc second order polymorphism in the 4th International Workshop on Database Programming Languages. New York City, August 1993.The author was supported by grant n. 203.01.56 of the Consiglio Nazionale delle Ricerche-Comitato Nazionale delle Scienze Matematiche to work at LIENS.     

A two-layer fuzzy pattern matching procedure for the evaluation of conditions involving vague quantifiers

In this note, we are interested in the evaluation of conditions of the form The value of attribute a for Q items of X is in F or more shortly Q items of X are F, where X is a set of items, Q denotes a possibly vague proportion (which may be linguistically expressed, e.g. most), F is a (possibly fuzzy) subset of the attribute domain of a. and where the available knowledge about the value a(x) of the attribute a for any item x may be imprecise or even vague. The evaluation is based on a fuzzy pattern matching procedure repeated two times. Such conditions may be encountered in queries addressed to an incomplete information data base or in the if-part of expert rules.     

The Objective Conception of Context and Its Logic

In this paper, an objective conception of contexts based loosely upon situation theory is developed and formalized. Unlike subjective conceptions, which take contexts to be something like sets of beliefs, contexts on the objective conception are taken to be complex, structured pieces of the world that (in general) contain individuals, other contexts, and propositions about them. An extended first-order language for this account is developed. The language contains complex terms for propositions, and the standard predicate ist that expresses the relation that holds between a context and a proposition just in case the latter is true in the former. The logic for the objective conception features a global classical predicate calculus, a local logic for reasoning within contexts, and axioms for propositions. The specter of paradox is banished from the logic by allowing ist to be nonbivalent in problematic cases: it is not in general the case, for any context c and proposition p, that either ist(c,p) or ist(c, ¬ p). An important representational capability of the logic is illustrated by proving an appropriately modified version of an illustrative theorem from McCarthy's classic Blocks World example.     

PI k mass production and an optimal circuit for the Nečiporuk slice

Letf: {0,1} ⁿ {0,1} ^m be anm-output Boolean function inn variables.f is called ak-slice iff(x) equals the all-zero vector for allx with Hamming weight less thank andf(x) equals the all-one vector for allx with Hamming weight more thank. Wegener showed that PI _k -set circuits (set circuits over prime implicants of lengthk) are at the heart of any optimum Boolean circuit for ak-slicef. We prove that, in PI _k -set circuits, savings are possible for the mass production of anyFX, i.e., any collectionF ofm output-sets given any collectionX ofn input-sets, if their PI _k -set complexity satisfiesSC _m (FX)3n+2m. This PI _k mass production, which can be used in monotone circuits for slice functions, is then exploited in different ways to obtain a monotone circuit of complexity 3n+o(n) for the Neiporuk slice, thus disproving a conjecture by Wegener that this slice has monotone complexity (n ^3/2). Finally, the new circuit for the Neiporuk slice is proven to be asymptotically optimal, not only with respect to monotone complexity, but also with respect to combinational complexity.     

A note on dense and nondense families of complexity classes

In a model for a measure of computational complexity, , for a partial recursive functiont, letR _t denote all partial recursive functions having the same domain ast and computable within timet. Let = {R _t |t is recursive} and let = { |_i is actually the running time function of a computation}. and are partially ordered under set-theoretic inclusion. These partial orderings have been extensively investigated by Borodin, Constable and Hopcroft in [3]. In this paper we present a simple uniform proof of some of their results. For example, we give a procedure for easily calculating a model of computational complexity for which is not dense while is dense. In our opinion, our technique is so transparent that it indicates that certain questions of density are not intrinsically interesting for general abstract measures of computational complexity, . (This is not to say that similar questions are necessarily uninteresting for specific models.)Supported by NSF Research Grants GP6120 and GJ27127.     

Viscous Lattices

Let E be an arbitrary space, and an extensive dilation of P(E) into itself, with an adjoint erosion . Then, the image [P(E)] of P(E) by is a complete lattice P where the sup is the union and the inf the opening of the intersection according to . The lattice L, named viscous, is not distributive, nor complemented. Any dilation on P(E) admits the same expression in L. However, the erosion in L is the opening according to of the erosion in P(E). Given a connection C on P(E) the image of C under turns out to be a connection C on L as soon as (C)eq C. Moreover, the elementary connected openings _x of C and _(x) are linked by the relation _(x) = _x. A comprehensive class of connection preverving closings is constructed. Two examples, binary and numerical (the latter comes from the heart imaging), prove the relevance of viscous lattices in interpolation and in segmentation problems.Jean Serra obtained the degree of Mining Engineer, in 1962 in Nancy, France, and in 1967 his Ph.D. for a work dealing with the estimation of the iron ore body of Lorraine by geostatistics. In cooperation with Georges Matheron, he laid the foundations of a new method, that he called Mathematical Morphology (1964). Its purpose was to describe quantitatively shapes and textures of natural phenomena, at micro and macro scales. In 1967, he founded with G. Matheron, the Centre de Morphologie Mathematique, at School of Mines of Paris, on the campus of Fontainebleau. Since this time, he has been working in this framework as a Directeur de Recherches. His main book is a two-volume treatise entitled Image Analysis and Mathematical Morphology (Ac. Press, 1982, 1988). He has been Vice President for Europe of the International Society for Stereology from 1979 to 1983. He founded the International Society for Mathematical Morphology in 1993, and was elected his first president. His achievements include several patents of devices for image processing, various awards and titles, such as the first AFCET award, in 1988, or Doctor Honoris Causa of the University of Barcelona (Spain) in 1993. He recently developed a new theory of segmentation, which is based on set connections (2001–2004), and currently works on colour image processing.     

Optimal algorithms for symmetry detection in two and three dimensions

Exact algorithms for detecting all rotational and involutional symmetries in point sets, polygons and polyhedra are described. The time complexities of the algorithms are shown to be (n) for polygons and (n logn) for two- and three-dimensional point sets. (n logn) time is also required for general polyhedra, but for polyhedra with connected, planar surface graphs (n) time can be achieved. All algorithms are optimal in time complexity, within constants.     

Shape optimization of elasto-plastic bodies under plane strains: Sensitivity analysis and numerical implementation

Optimal shape design problems for an elastic body made from physically nonlinear material are presented. Sensitivity analysis is done by differentiating the discrete equations of equilibrium. Numerical examples are included.Notation U ^ad set of admissible continuous design parameters - U _h ^ad set of admissible discrete design parameters - function fromU _h ^ad defining shape of body - _h function fromU _h ^ad defining approximated shape of body - vector of nodal values of _h - { _n} sequence of functions tending to - () domain defined by - K bulk modulus - shear modulus - penalty parameter for contact condition - V() space of virtual displacements in() - V _h(_h) finite element approximation ofV() - J cost functional - J _h discretized cost functional - J algebraic form ofJ _h - (u) stress tensor - e(u) strain tensor - K stiffness matrix - f force vector - b(q) term arising from nonlinear boundary conditions - q vector of nodal degrees of freedom - p vector of adjoint state variables - J Jacobian of isoparametric mapping - |J| determinant ofJ - N vector of shape function values on parent element - L matrix of shape function derivatives on parent element - G matrix of Cartesian derivatives of shape functions - X matrix of nodal coordinates of element - D matrix of elastic coefficients - B strain-displacement matrix - _P part of boundary where tractions are prescribed - _u part of boundary where displacements are prescribed - variable part of boundary - strain invariant     

Information Gaps as Communication Needs: A New Semantic Foundation for Some Non-Classical Logics

Semantics connected to some information based metaphor are well-known in logic literature: a paradigmatic example is Kripke semantic for Intuitionistic Logic. In this paper we start from the concrete problem of providing suitable logic-algebraic models for the calculus of attribute dependencies in Formal Contexts with information gaps and we obtain an intuitive model based on the notion of passage of information showing that Kleene algebras, semi-simple Nelson algebras, three-valued ukasiewicz algebras and Post algebras of order three are, in a sense, naturally and directly connected to partially defined information systems. In this way wecan provide for these logic-algebraic structures a raison dêetre different from the original motivations concerning, for instance, computability theory.     

An Estimation Problem for Quasilinear Stochastic Partial Differential Equations

A problem of estimating a functional parameter (x) and functionals () based on observation of a solution u (t, x) of the stochastic partial differential equation is considered. The asymptotic problem setting, as the noise intensity 0, is investigated.     

Conditions for the Light-Traffic Insensitivity to Loss Probability in a GI/G/m/0 Queueing System

A loss queueing system GI/G/m/0 is considered. Let a(x) be a p.d.f. of interarrival intervals. Assume that this function behaves like cx^-1 for small x. Further let B(x) be a d.f. of service time; (1/) be the mean service time. Conditions are derived for the light-traffic insensitivity of the loss probability to the form of B(x) as (/ ) 0. In particular, the condition = 1 is necessary. Estimates for the loss probability are obtained.     

Condensed detachment is complete for relevance logic: A computer-aided proof

The condensed detachment ruleD is a combination of modus ponens with a minimal amount of substitution. EarlierD has been shown to be complete for intuitionistic and classical implicational logic but incomplete forBCK andBCI logic. We show thatD is complete for the relevance logic. One of the main steps is the proof of the formula ((a a) a) a found in interaction with our resolution theorem prover. Various strategies of generating consequences of the axioms and choosing best ones for the next iteration were tried until the proof was found.     

Asymmetric Rendezvous Search on the Circle

The rendezvous search problem asks how two blind searchers in a known search region, having maximum speed one, can minimize the expected time needed to meet. Suppose that two players are placed an arc-distance x [ 0,1/2] apart on a circle of circumference 1, and faced in random directions. If x has a continuous density function h which is either decreasing and satisfies ht( 1/2) h(0)/2,or increasing, we determine an optimal rendezvous strategy. Furthermore if h is strictly monotone, this strategy (which depends in a simple manner on h) is uniquely optimal. This work extends that of J. V. Howard, who showed for the uniform density h(x) = 2 that search and wait is optimal , with expected search time 1/2. We also show that the uniform density is the only counterexample on the circle to S. Gal's conjecture (which he proved for the line) on the nonoptimality of search and wait.