A technical note on AC-Unification. The number of minimal unifiers of the equation αx1 + ⋯ + αxp ≐AC βy1 + ⋯ + βyq

We show in this note that the equation αx₁ + #x22EF; +αx_p?_ACβy₁ + α +βy_q where + is an AC operator and αx stands for x+...+x (α times), has exactly $$\left( { - 1} \right)^{p + q} \sum\limits_{i = 0}^p {\sum\limits_{j = 0}^q {\left( { - 1} \right)^{1 + 1} \left( {\begin{array}{*{20}c} p \\ i \\ \end{array} } \right)\left( {\begin{array}{*{20}c} q \\ j \\ \end{array} } \right)} 2^{\left( {\alpha + \begin{array}{*{20}c} {j - 1} \\ \alpha \\ \end{array} } \right)\left( {\beta + \begin{array}{*{20}c} {i - 1} \\ \beta \\ \end{array} } \right)} } $$ minimal unifiers if gcd(α, β)=1.     

A 2.5n lower bound on the monotone network complexity of T 3 n

Summary The k-th threshold function, T _k ⁿ , is defined as: where x _i{0,1} and the summation is arithmetic. We prove that any monotone network computing T _3/n(x ₁,...,x _n) contains at least 2.5n-5.5 gates.This research was supported by the Science and Engineering Research Council of Great Britain, UK     

Formule di quadratura «chiuse» di tipo gaussiano: Tabulzione dei nodi e dei coefficienti

The coefficientsA _hi and the nodesx _mi for «closed” Gaussian-type quadrature formulae $$\int\limits_{ - 1}^1 {f(x)dx = \sum\limits_{h = 0}^{2_8 } {\sum\limits_{i = 0}^{m + 1} {A_{hi} f^{(h)} (x_{mi} ) + R\left[ {f(x)} \right]} } } $$ withx _m0 =?1,x _{m, m+1} =1 andR[f(x)]=0 iff(x) is a polinomial of degree at most2m(s+1)+2(2s+1)?1, have been tabulated for the cases: $$\left\{ \begin{gathered} s = 1,2 \hfill \\ m = 2,3,4,5 \hfill \\ \end{gathered} \right.$$ .     

Maximum concurrent flows and minimum cuts

In many applications, we need to find a minimum cost partition of a network separating a given pair of nodes. A classical example is the Max-Flow Min-Cut Theorem, where the cost of the partition is defined to be the sum of capacities of arcs connecting the two parts. Other similar concepts such as minimum weighted sparsest cut and flux cut have also been introduced. There is always a cost associated with a cut, and we always seek the min-cost cut separating a given pair of nodes. A natural generalization from the separation of a given pair is to find all minimum cost cuts separating all pairs of nodes, with arbitrary costs associated with all 2^n–1 — 1 cuts. In the present paper, we show thatn — 1 minimum cost cuts are always sufficient to separate all pairs of nodes.A further generalization is to considerk-way partitions rather than two-way partitions. An interesting relationship exists betweenk-way partitions, the multicommodity flow problem, and the minimum weighted sparsest cut. Namely, if the staturated arcs in a multicommodity flow problem form ak-way partition (k 4), then thek-way partition contains a two-way partition. This two-way partition is the minimum weight sparsest cut.This work is supported in part by the NSF under Grant MIP-8700767 and micro program under Grants 506205 and 506215, Intergraph, and Data General.     

Metodi pseudo Runge-Kutta ottimali

For the numerical integration of the problem with initial value $$y' = f(x,y),y(x_0 ) = y_0 ,\begin{array}{*{20}c} {\begin{array}{*{20}c} x \\ {x_0 } \\ \end{array} \in [a,b],} \\ \end{array} $$ the pseudo R. K. methods of second kind are taken again and approximations are drawn, that in particular casef(x, y)≡f(x) are reduced to quadrature formulae of Radau and Lobatto. The limits of the trancation's error and the stability's intervals of the pseudo R. K. methods of the first and second species with the approximations of the same order of R. K. are determined and compared. At the end of that, a numerical example is taken.     

On-line graph coloring of {\mathbb{P}_5}-free graphs

Kierstead et al. (SIAM J Discret Math 8:485–498, 1995) have shown 1 that the competitive function of on-line coloring for -free graphs (i.e., graphs without induced path on 5 vertices) is bounded from above by the exponential function . No nontrivial lower bound was known. In this paper we show the quadratic lower bound . More precisely, we prove that is the exact competitive function for ()-free graphs. In this paper we also prove that 2 - 1 is the competitive function of the best clique covering on-line algorithm for ()-free graphs.     

Convergence,stability and truncation error estimation of a method for the numerical integration of the initial value problemY″=F(X,Y)

In this paper a detailed study of the convergence and stability of a numerical method for the differential problem $$\left\{ \begin{gathered} y'' = f(x,y) \hfill \\ y(x_0 ) = y_0 \hfill \\ y'(x_0 ) = y_0 ^\prime \hfill \\ \end{gathered} \right.$$ has carried out and its truncation error estimated. Some numerical experiments are described.     

Un metodo del terzo ordine per l'integrazione numerica dell'equazione differenziale ordinaria

For the numerical integration of the ordinary differential equation $$\frac{{dy}}{{dx}} = F(x,y) y(x_0 ) = y_0 \begin{array}{*{20}c} x \\ {x_0 } \\ \end{array} \varepsilon [a,b]$$ a third method utilizing only two points for every step, is determined different from the analogous Runge-Kutta method employing three points; it is useless take the first step as the «pseudo Runge-Kutta method». The truncation error is given, the convergence is proved and finally a numerical exercise is given.     

A note on the Bernstein algorithm for bounds for interval polynomials

In computing the range of values of a polynomial over an intervala≤x≤b one may use polynomials of the form $$\left( {\begin{array}{*{20}c} k \\ j \\ \end{array} } \right)\left( {x - a} \right)^j \left( {b - x} \right)^{k - j} $$ called Bernstein polynomials of the degreek. An arbitrary polynomial of degreen may be written as a linear combination of Bernstein polynomials of degreek≥n. The coefficients of this linear combination furnish an upper/lower bound for the range of the polynomial. In this paper a finite differencelike scheme is investigated for this computation. The scheme is then generalized to interval polynomials.     

Metodi Multistep con accelerazione per la risoluzione numerica dei sistemi di equazioni differenziali ordinarie

In this paper a procedure for the acceleration of the convergence is given. It allows the doubling of the order of the multistep methods for the numerical solution of the systems of ordinary differential equations: $$Y' = F(x,Y); Y_0 = Y(x_0 ) \begin{array}{*{20}c} x \\ {x_0 } \\ \end{array} \in [a,b]$$ whereY andF(x,Y) aret-vectors.     

A Representation of the Interval Hull of a Tolerance Polyhedron Describing Inclusions of Function Values and Slopes

Given a nonempty set of functions

Quantitative theorems on approximation by Bernstein-Stancu operators

In 1972 D. D. Stancu introduced a generalization \(L_{mp} ^{< \alpha \beta \gamma > }\) of the classical Bernstein operators given by the formula $$L_{mp}< \alpha \beta \gamma > (f,x) = \sum\limits_{k = 0}^{m + p} {\left( {\begin{array}{*{20}c} {m + p} \\ k \\ \end{array} } \right)} \frac{{x^{(k, - \alpha )} \cdot (1 - x)^{(m + p - k, - \alpha )} }}{{1^{(m + p, - \alpha )} }}f\left( {\frac{{k + \beta }}{{m + \gamma }}} \right)$$ . Special cases of these operators had been investigated before by quite a number of authors and have been under investigation since then. The aim of the present paper is to prove general results for all positiveL _mp ^<αβγ> 's as far as direct theorems involving different kinds of moduli of continuity are concerned. When applied to special cases considered previously, all our corollaries of the general theorems will be as good as or yield improvements of the known results. All estimates involving the second order modulus of continuity are new.     

The addition of bounded quantification and partial functions to a computational logic and its theorem prover

We describe an extension to our quantifier-free computational logic to provide the expressive power and convenience of bounded quantifiers and partial functions. By quantifier we mean a formal construct which introduces a bound or indicial variable whose scope is some subexpression of the quantifier expression. A familiar quantifier is the Σ operator which sums the values of an expression over some range of values on the bound variable. Our method is to represent expressions of the logic as objects in the logic, to define an interpreter for such expressions as a function in the logic, and then define quantifiers as ‘mapping functions’. The novelty of our approach lies in the formalization of the interpreter and its interaction with the underlying logic. Our method has several advantages over other formal systems that provide quantifiers and partial functions in a logical setting. The most important advantage is that proofs not involving quantification or partial recursive functions are not complicated by such notions as ‘capturing’, ‘bottom’, or ‘continuity’. Naturally enough, our formalization of the partial functions is nonconstructive. The theorem prover for the logic has been modified to support these new features. We describe the modifications. The system has proved many theorems that could not previously be stated in our logic. Among them are:

? classic quantifier manipulation theorems, such as $$\sum\limits_{{\text{l}} = 0}^{\text{n}} {{\text{g}}({\text{l}}) + {\text{h(l) = }}} \sum\limits_{{\text{l = }}0}^{\text{n}} {{\text{g}}({\text{l}})} + \sum\limits_{{\text{l = }}0}^{\text{n}} {{\text{h(l)}};} $$

? elementary theorems involving quantifiers, such as the Binomial Theorem: $$(a + b)^{\text{n}} = \sum\limits_{{\text{l = }}0}^{\text{n}} {\left( {_{\text{i}}^{\text{n}} } \right)} \user2{ }{\text{a}}^{\text{l}} {\text{b}}^{{\text{n - l}}} ;$$

? elementary theorems about ‘mapping functions’ such as: $$(FOLDR\user2{ }'PLUS\user2{ O L) = }\sum\limits_{{\text{i}} \in {\text{L}}}^{} {{\text{i}};} $$

? termination properties of many partial recursive functions such as the fact that an application of the partial function described by $$\begin{gathered} (LEN X) \hfill \\ \Leftarrow \hfill \\ ({\rm I}F ({\rm E}QUAL X NIL) \hfill \\ {\rm O} \hfill \\ (ADD1 (LEN (CDR X)))) \hfill \\ \end{gathered} $$ terminates if and only if the argument ends in NIL;

? theorems about functions satisfying unusual recurrence equations such as the 91-function and the following list reverse function: $$\begin{gathered} (RV X) \hfill \\ \Leftarrow \hfill \\ ({\rm I}F (AND (LISTP X) (LISTP (CDR X))) \hfill \\ (CONS (CAR (RV (CDR X))) \hfill \\ (RV (CONS (CAR X) \hfill \\ (RV (CDR (RV (CDR X))))))) \hfill \\ X). \hfill \\ \end{gathered} $$

     

Attractive energy contribution to nanoconfined fluids behavior: the normal pressure tensor

The aim of our research is to demonstrate the role of attractive intermolecular potential energy on normal pressure tensor of confined molecular fluids inside nanoslit pores of two structureless purely repulsive parallel walls in xy plane at z = 0 and z = H, in equilibrium with a bulk homogeneous fluid at the same temperature and at a uniform density. To achieve this we have derived the perturbation theory version of the normal pressure tensor of confined inhomogeneous fluids in nanoslit pores:

Extracting maximal information about sets of minimum cuts

There are two well-known, elegant, compact, and efficiently computed representations of selected minimum edge cuts in a weighted, undirected graphG=(V, E) withn nodes andm edges: at one extreme, the Gomory-Hu cut tree [12] represents minimum cuts, one for each pair of nodes inG; at the other extreme, the Picard-Queyranne DAG [24] represents all the minimum cuts between a single pair of nodes inG. The GH cut tree is constructed with onlyn–1 max-flow computations, and the PQ DAG is constructed with one max-flow computation, plusO(m) additional time. In this paper we show how to marry these two representations, getting the best features of both. We first show that we can construct all DAGs, one for each fixed pair of nodes, using onlyn–1 max-flow computations as in [12], plusO(m) time per DAG as in [24]. This speeds up the obvious approach by a factor ofn. We then apply this approach to an unweighted graphG, to find all the edge-connectivity cuts inG, i.e., cuts with capacity equal to the connectivity ofG. Matula [22] gave a method to find one connectivity cut inO(nm) time; we show thatO(nm) time suffices to represent all connectivity cuts compactly, and to list all of them explicitly. This improves the previous best time bound ofO(n ² m) [3] for listing the connectivity cuts. The connectivity cuts are central in network reliability calculations. We then show how to find all pairs of nodes that are separated by at least one connectivity cut inO(nm) time.Research was partially supported by Grant CCR-8803704 from the National Science Foundation.     

Stability of Linear Difference and Differential Inclusions

Any given n×n matrix A is shown to be a restriction, to the A-invariant subspace, of a nonnegative N×N matrix B of spectral radius (B) arbitrarily close to (A). A difference inclusion , where is a compact set of matrices, is asymptotically stable if and only if can be extended to a set of nonnegative matrices B with or . Similar results are derived for differential inclusions.     

Estimating temperature fluctuations in the early universe

A lagrangian for a k-essence field is constructed for a constant scalar potential, and its form is determined when the scale factor is very small as compared to the present epoch but very large as compared to the inflationary epoch. This means that one is already in an expanding and flat universe. The form is similar to that of an oscillator with time-dependent frequency. Expansion is naturally built into the theory with the existence of growing classical solutions of the scale factor. The formalism allows one to estimate the temperature fluctuations of the background radiation at these early stages (as compared to the present epoch) of the Universe. If the temperature is T _a at time t _a and T _b at time t _b (t _b > t _a ), then, for small times, the probability evolution for the logarithm of the inverse temperature can be estimated as

Exact asymptotics of small deviations for a stationary Ornstein-Uhlenbeck process and some Gaussian diffusion processes in the L p -norm, 2 ≤ p ≤ ∞

We prove results on exact asymptotics of the probabilities