The existence of solutions,stability, and linearization of volterra systems

LetB be a Banach space ofR _n valued continuous functions on [0, ) withfB. Consider the nonlinear Volterra integral equation (^*)x(t)+ _o ^t K(t,s,x(s))ds. We use the implicit function theorem to give sufficient conditions onB andK (t,s,x) for the existence of a unique solutionxB to (^*) for eachf B with f ^B sufficiently small. Moreover, there is a constantM>0 independent off with Mf^B.Part of this work was done while the author was visiting at Wright State University.     

Shallow circuits and concise formulae for multiple addition and multiplication

A theory is developed for the construction of carry-save networks with minimal delay, using a given collection of carry-save adders each of which may receive inputs and produce outputs using several different representation standards.The construction of some new carry-save adders is described. Using these carry-save adders optimally, as prescribed by the above theory, we get {, , }-circuits of depth 3.48 log₂ n and {, , }-circuits of depth 4.95 log₂ n for the carry-save addition ofn numbers of arbitrary length. As a consequence we get multiplication circuits of the same depth. These circuits put out two numbers whose sum is the result of the multiplication. If a single output number is required then the depth of the multiplication circuits increases respectively to 4.48 log₂ n and 5.95 log₂ n.We also get {, , }-formulae of sizeO (n ^3.13) and {, }-formulae of sizeO (n ^4.57) for all the output bits of a carry-save addition ofn numbers. As a consequence we get formulae of the same size for the majority function and many other symmetric Boolean functions.     

Linear Interval Tolerance Problem and Linear Programming Techniques

In this paper, we consider the linear interval tolerance problem, which consists of finding the largest interval vector included in ([A], [b]) = {x R ⁿ | A [A], b [b], Ax = b}. We describe two different polyhedrons that represent subsets of all possible interval vectors in ([A], [b]), and we provide a new definition of the optimality of an interval vector included in ([A], [b]). Finally, we show how the Simplex algorithm can be applied to find an optimal interval vector in ([A], [b]).     

The Claremont Shakespeare Authorship Clinic: How Severe Are the Problems?

Ward Elliott (from 1987) and Robert Valenza (from 1989) set out to the find the true Shakespeare from among 37 anti-Stratfordian Claimants. As directors of the Claremont Shakespeare Authorship Clinic, Elliott and Valenza developed novel attributional tests, from which they concluded that most Claimants are not-Shakespeare. From 1990-4, Elliott and Valenza developed tests purporting further to reject much of the Shakespeare canon as not-Shakespeare (1996a). Foster (1996b) details extensive and persistent flaws in the Clinic's work: data were collected haphazardly; canonical and comparative text-samples were chronologically mismatched; procedural controls for genre, stanzaic structure, and date were lacking. Elliott and Valenza counter by estimating maximum erosion of the Clinic's findings to include five of our 54 tests, which can amount, at most, to half of one percent (1998). This essay provides a brief history, showing why the Clinic foundered. Examining several of the Clinic's representative tests, I evaluate claims that Elliott and Valenza continue to make for their methodology. A final section addresses doubts about accuracy, validity and replicability that have dogged the Clinic's work from the outset.     

Specification and verification of database dynamics

Summary A framework is proposed for the structured specification and verification of database dynamics. In this framework, the conceptual model of a database is a many sorted first order linear tense theory whose proper axioms specify the update and the triggering behaviour of the database. The use of conceptual modelling approaches for structuring such a theory is analysed. Semantic primitives based on the notions of event and process are adopted for modelling the dynamic aspects. Events are used to model both atomic database operations and communication actions (input/output). Nonatomic operations to be performed on the database (transactions) are modelled by processes in terms of trigger/reaction patterns of behaviour. The correctness of the specification is verified by proving that the desired requirements on the evolution of the database are theorems of the conceptual model. Besides the traditional data integrity constraints, requirements of the form Under condition W, it is guaranteed that the database operation Z will be successfully performed are also considered. Such liveness requirements have been ignored in the database literature, although they are essential to a complete definition of the database dynamics.

Notation

Classical Logic Symbols (Appendix 1) for all (universal quantifier) - exists at least once (existential quantifier) - ¬ no (negation) - implies (implication) - is equivalent to (equivalence) - and (conjunction) - or (disjunction) Tense Logic Symbols (Appendix 1) G always in the future - G ₀ always in the future and now - F sometime in the future - F ₀ sometime in the future or now - H always in the past - H ₀ always in the past and now - P sometime in the past - P ₀ sometime in the past or now - X in the next moment - Y in the previous moment - L always - M sometime Event Specification Symbols (Sects. 3 and 4.1) (x) means immediately after the occurrence of x - (x) means immediately before the occurrence of x - (x) means x is enabled, i.e., x may occur next - { } ({w ₁} x{w ₂}) states that if w ₁ holds before the occurrence of x, then w ₂ will hold after the occurrence of x (change rule) - [ ] ([oa₁, ..., oa_n]x) states that only the object attributes oa₁, ..., oa _n are modifiable by x (scope rule) - {{ }} ({{w}}x) states that if x may occur next, then w holds (enabling rule) Process Specification Symbols (Sects. 5.3 and 5.4) :: for causal rules - for behavioural rules Transition-Pattern Composition Symbols (Sects. 5.2 and 5.3) ; sequential composition - ¦ choice composition - parallel composition - :| guarded alternative composition Location Predicates (Sect. 5.2) (z) means immediately after the occurrence of the last event of z (after) - (z) means immediately before the occurrence of the first event of z (before) - (z) means after the beginning of z and before the end of z (during) - ( z) means before the occurrence of an event of z (at)     

Three-valued representative systems

A representative system defined onn voters or propositionsi = 1,,n is a functionF: {1,0, -1} ⁿ {1,0, -1} which is monotonic (D E F(D) F(E)), unanimous (F(1,, 1) = 1), dual (F(-D) = -F(D)), and satisfies a positivity property which says that the set of all non-zero vectors in {1, 0, -1} ⁿ for whichF(D) = 0 can be partitioned into two dual subsets each of which has the property that ifD andE are in the subset thenD _i+E _i > 0 for somei. Representative systems can be defined recursively from the coordinate projectionsS _i (D) = D _i using sign functions, and in this format they are interpreted as hierarchical voting systems in which outcomes of votes in lower levels act as votes in higher levels of the system. For each positive integern, (n) is defined as the smallest positive integer such that all representative systems defined on {1, 0, -1} ⁿ can be characterized by(n) or fewer hierarchical levels. The function is nondecreasing inn, unbounded above, and satisfies(n) n–1 for alln. In addition,(n) = n–1 forn {1, 2, 3, 4}, and it is conjectured that does not continue to grow linearly asn increases.     

Maintaining the visibility map of spheres while moving the viewpoint on a circle at infinity

We investigate three-dimensional visibility problems for scenes that consist ofn non-intersecting spheres. The viewing point moves on a flightpath that is part of a circle at infinity given by a planeP and a range of angles {(t)¦t[01]} [02]. At timet, the lines of sight are parallel to the ray inP, which starts in the origin ofP and represents the angle(t) (orthographic views of the scene). We give an algorithm that computes the visibility graph at the start of the flight, all time parameters at which the topology of the scene changes, and the corresponding topology changes. The algorithm has running time0(n + k + p) logn), wheren is the number of spheres in the scene;p is the number of transparent topology changes (the number of different scene topologies visible along the flight path, assuming that all spheres are transparent); andk denotes the number of vertices (conflicts) which are in the (transparent) visibility graph at the start and do not disappear during the flight.The second author was supported by the ESPRIT II Basic Research Actions Program, under Contract No. 3075 (project ALCOM).     

A New Class of Depth-Size Optimal Parallel Prefix Circuits

Given n values x₁, x₂, ... ,x_n and an associative binary operation o, the prefix problem is to compute x₁ox₂o··· ox_i, 1in. Many combinational circuits for solving the prefix problem, called prefix circuits, have been designed. It has been proved that the size s(D(n)) and the depth d(D(n)) of an n-input prefix circuit D(n) satisfy the inequality d(D(n))+s(D(n))2n–2; thus, a prefix circuit is depth-size optimal if d(D(n))+s(D(n))=2n–2. In this paper, we construct a new depth-size optimal prefix circuit SL(n). In addition, we can build depth-size optimal prefix circuits whose depth can be any integer between d(SL(n)) and n–1. SL(n) has the same maximum fan-out lgn+1 as Snir's SN(n), but the depth of SL(n) is smaller; thus, SL(n) is faster. Compared with another optimal prefix circuit LYD(n), d(LYD(n))+2d(SL(n))d(LYD(n)). However, LYD(n) may have a fan-out of at most 2 lgn–2, and the fan-out of LYD(n) is greater than that of SL(n) for almost all n12. Because an operation node with greater fan-out occupies more chip area and is slower in VLSI implementation, in most cases, SL(n) needs less area and may be faster than LYD(n). Moreover, it is much easier to design SL(n) than LYD(n).     

On Bounding Solutions of Underdetermined Systems

Sufficient conditions for the existence and uniqueness of a solution x* D (R ⁿ ) of Y(x) = 0 where : R ⁿ R ^m (m n) with C ²(D) where D R ⁿ is an open convex set and Y = (x)⁺ are given, and are compared with similar results due to Zhang, Li and Shen (Reliable Computing 5(1) (1999)). An algorithm for bounding zeros of f (·) is described, and numerical results for several examples are given.     

Parallel geometric algorithms on a mesh-connected computer

We show that a number of geometric problems can be solved on a n × n mesh-connected computer (MCC) inO(n) time, which is optimal to within a constant factor, since a nontrivial data movement on an MCC requires (n) time. The problems studied here include multipoint location, planar point location, trapezoidal decomposition, intersection detection, intersection of two convex polygons, Voronoi diagram, the largest empty circle, the smallest enclosing circle, etc. TheO(n) algorithms for all of the above problems are based on the classical divide-and-conquer problem-solving strategy.This work was supported in part by the National Science Foundation under Grant DCR 8420814. A preliminary version was presented in the 1987 FJCC, Dallas, TX.     

Mesh Selection for a Nearly Singular Boundary Value Problem

In this paper, we investigate the numerical solution of a model equation u _xx = exp(– ) (and several slightly more general problems) when 1 using the standard central difference scheme on nonuniform grids. In particular, we are interested in the error behaviour in two limiting cases: (i) the total mesh point number N is fixed when the regularization parameter 0, and (ii) is fixed when N. Using a formal analysis, we show that a generalized version of a special piecewise uniform mesh 12 and an adaptive grid based on the equidistribution principle share some common features. And the optimal meshes give rates of convergence bounded by |log()| as 0 and N is given, which are shown to be sharp by numerical tests.     

From Conditional Events to Conditional Measures: A New Axiomatic Approach

Our starting point is a definition of conditional event EH which differs from many seemingly similar ones adopted in the relevant literature since 1935, starting with de Finetti. In fact, if we do not assign the same third value u (undetermined) to all conditional events, but make it depend on EH, it turns out that this function t(EH) can be taken as a general conditional uncertainty measure, and we get (through a suitable – in a sense, compulsory – choice of the relevant operations among conditional events) the natural axioms for many different (besides probability) conditional measures.     

Hierarchy theorems for two-way finite state transducers

Summary For a family of languages , CAL() is defined as the family of images of under nondeterministic two-way finite state transducers, while FINITE · VISIT() is the closure of under deterministic two-way finite state transducers; CAL⁰()= and for n0, CAL ⁿ⁺¹()=CAL ⁿ (CAL()). For any semiAFL , if FINITE · VISIT() CAL(), then CAL ⁿ () forms a proper hierarchy and for every n0, FINITE · VISIT(CALⁿ()) CAL ⁿ⁺¹() FINITE · VISIT(CAL ⁿ⁺¹()). If is a SLIP semiAFL or a weakly k-iterative full semiAFL or a semiAFL contained in any full bounded AFL, then FINITE · VISIT() CAL() and in the last two cases, FINITE · VISIT(). If is a substitution closed full principal semiAFL and FINITE · VISIT(), then FINITE · VISIT() CAL(). If is a substitution closed full principal semiAFL generated by a language without an infinite regular set and ₁ is a full semiAFL, then is contained in CAL^m(₁) if and only if it is contained in ₁. Among the applications of these results are the following. For the following families , CAL ⁿ () forms a proper hierarchy: =INDEXED, =ETOL, and any semiAFL contained in CF. The family CF is incomparable with CAL ^m (NESA) where NESA is the family of one-way nonerasing stack languages and INDEXED is incomparable with CAL ^m (STACK) where STACK is the family of one-way stack languages.This work was supported in part by the National Science Foundation under Grants No. DCR74-15091 and MCS-78-04725     

Constructing sets of functions which have a givenF-cardinality

The termF-cardinality of (=F-card()) is introduced whereF: ^{n n} is a partial function and is a set of partial functionsf: ^{n n} . TheF-cardinality yields a lower bound for the worst-case complexity of computingF if only functionsf can be evaluated by the underlying abstract automaton without conditional jumps. This complexity bound isindependent from the oracles available for the abstract machine. Thus it is shown that any automaton which can only apply the four basic arithmetic operations needs (n logn) worst-case time to sortn numbers; this result is even true if conditional jumps witharbitrary conditions are possible. The main result of this paper is the following: Given a total functionF: ^{n n} and a natural numberk, it is almost always possible to construct a set such that itsF-cardinality has the valuek; in addition, can be required to be closed under composition of functionsf,g . Moreover, ifF is continuous, then consists of continuous functions.     

Best Huffman trees

Summary Given a sequence of positive weights, W=w ₁...w _n >0, there is a Huffman tree, T (T-up) which minimizes the following functions: max{d(w_i)}; d(w_i); f(d(w_i)) w _i(here d(w _i) represents the distance of a leaf of weight w _i to the root and f is a function defined for nonnegative integers having the property that g(x) = f(x + 1) – f(x) is monotone increasing) over the set of all trees for W having minimal expected length. Minimizing the first two functions was first done by Schwartz [5]. In the case of codes where W is a sequence of probabilities, this implies that the codes based on T have all their absolute central moments minimal. In particular, they are the least variance codes which were also described by Kou [3]. Furthermore, there exists a Huffman tree T, (T-down) which maximizes the functions considered above.However, if g(x) is monotone decreasing, T and T, respectively maximize and minimize f(d(w_i) w _i) over the set of all trees for W having minimal expected length. In addition, we derive a number of interesting results about the distribution of labels within Huffman trees. By suitable modifications of the usual Huffman tree construction, (see [1]) T and T can also be constructed in time O(n log n).     

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     

Dynamic half-space range reporting and its applications

We consider the half-space range-reporting problem: Given a setS ofn points in ^d, preprocess it into a data structure, so that, given a query half-space , allk points ofS can be reported efficiently. We extend previously known static solutions to dynamic ones, supporting insertions and deletions of points ofS. For a given parameterm,n m n ^d/2 and an arbitrarily small positive constant , we achieveO(m ¹⁺) space and preprocessing time, O((n/m ^d/2 logn+k) query time, and O(m¹⁺n) amortized update time (d 3). We present, among others, the following applications: an O(n¹⁺)-time algorithm for computing convex layers in ³, and an output sensitive algorithm for computing a level in an arrangements of planes in ³, whose time complexity is O((b+n) n, whereb is the size of the level.Work by the first author has been supported by National Science Foundation Grant CCR-91-06514. A preliminary version of this paper appeared in Agarwalet al. [2], which also contains the results of [20] on dynamic bichromatic closest pair and minimum spanning trees.     

Logic Based Abstractions of Real-Time Systems

When verifying concurrent systems described by transition systems, state explosion is one of the most serious problems. If quantitative temporal information (expressed by clock ticks) is considered, state explosion is even more serious. We present a notion of abstraction of transition systems, where the abstraction is driven by the formulae of a quantitative temporal logic, called qu-mu-calculus, defined in the paper. The abstraction is based on a notion of bisimulation equivalence, called , n-equivalence, where is a set of actions and n is a natural number. It is proved that two transition systems are , n-equivalent iff they give the same truth value to all qu-mu-calculus formulae such that the actions occurring in the modal operators are contained in , and with time constraints whose values are less than or equal to n. We present a non-standard (abstract) semantics for a timed process algebra able to produce reduced transition systems for checking formulae. The abstract semantics, parametric with respect to a set of actions and a natural number n, produces a reduced transition system , n-equivalent to the standard one. A transformational method is also defined, by means of which it is possible to syntactically transform a program into a smaller one, still preserving , n-equivalence.     

Duality in Quantum Information Geometry

Let H be a separable Hilbert space. We consider the manifold M consisting of density operators on H such that ^p is of trace class for some p (0, 1). We say M is nearby if there exists C > 1 such that C ^–1C. We show that the space of nearby points to can be furnished with the two flat connections known as the (±)-affine structures, which are dual relative to the BKM metric. We furnish M with a norm making it into a Banach manifold.     

Low-Rank Approximation of Integral Operators by Interpolation

A central component of the analysis of panel clustering techniques for the approximation of integral operators is the so-called -admissibility condition min {diam(),diam()} 2dist(,) that ensures that the kernel function is approximated only on those parts of the domain that are far from the singularity. Typical techniques based on a Taylor expansion of the kernel function require a subdomain to be far enough from the singularity such that the parameter has to be smaller than a given constant depending on properties of the kernel function. In this paper, we demonstrate that any is sufficient if interpolation instead of Taylor expansionisused for the kernel approximation, which paves the way for grey-box panel clustering algorithms.