Filter theory of BL algebras

In this paper we consider fundamental properties of some types of filters (Boolean, positive implicative, implicative and fantastic filters) of BL algebras defined in Haveshki et al. (Soft Comput 10:657–664, 2006) and Turunen (Arch Math Logic 40:467–473, 2001). It is proved in Haveshki et al. (2006) that if F is a maximal and (positive) implicative filter then it is a Boolean filter. In that paper there is an open problem Under what condition are Boolean filters positive implicative filters? One of our results gives an answer to the problem, that is, we need no more conditions. Moreover, we give simple characterizations of those filters by an identity form ? x, y(t(x, y) ∈ F), where t(x, y) is a term containing x, y.      

Inapproximability of the Tutte polynomial of a planar graph

The Tutte polynomial of a graph G is a two-variable polynomial T(G; x, y) that encodes many interesting properties of the graph. We study the complexity of the following problem, for rationals x and y: given as input a planar graph G, determine T(G; x, y). Vertigan completely mapped the complexity of exactly computing the Tutte polynomial of a planar graph. He showed that the problem can be solved in polynomial time if (x, y) is on the hyperbola H _q given by (x ? 1)(y ? 1) = q for q = 1 or q = 2 or if (x, y) is one of the two special points (x, y) = (?1, ?1) or (x, y) = (1, 1). Otherwise, the problem is #P-hard. In this paper, we consider the problem of approximating T(G; x, y), in the usual sense of “fully polynomial randomized approximation scheme” or FPRAS. Roughly speaking, an FPRAS is required to produce, in polynomial time and with high probability, an answer that has small relative error. Assuming that NP is different from RP, we show that there is no FPRAS for the Tutte polynomial in a large portion of the (x, y) plane. In particular, there is no FPRAS if x > 1, y < ?1 or if y > 1, x < ?1 or if x < 0, y < 0 and q > 5. Also, there is no FPRAS if x < 1, y < 1 and q = 3. For q > 5, our result is intriguing because it shows that there is no FPRAS at (x, y) =?(1 ? q/(1 + ε), ?ε) for any positive ε but it leaves open the limit point ε =?0, which corresponds to approximately counting q-colorings of a planar graph.     

Exact exponential-time algorithms for finding bicliques

Due to a large number of applications, bicliques of graphs have been widely considered in the literature. This paper focuses on non-induced bicliques. Given a graph G=(V,E) on n vertices, a pair (X,Y), with X,Y⊆V, X∩Y=∅, is a non-induced biclique if {x,y}∈E for any x∈X and y∈Y. The NP-complete problem of finding a non-induced (k₁,k₂)-biclique asks to decide whether G contains a non-induced biclique (X,Y) such that |X|=k₁ and |Y|=k₂. In this paper, we design a polynomial-space O(n^1.6914)-time algorithm for this problem. It is based on an algorithm for bipartite graphs that runs in time O(n^1.30052). In deriving this algorithm, we also exhibit a relation to the spare allocation problem known from memory chip fabrication. As a byproduct, we show that the constraint bipartite vertex cover problem can be solved in time O(n^1.30052).     

A sixth-order extrapolation method for special nonlinear fourth-order boundary value problems

A sixth-order convergent finite difference method is developed for the numerical solution of the special nonlinear fourth-order boundary value problem y^(iv)(x) = f(x, y), a < x < b, y(a) = A₀, y″(a) = B₀, y(b) = A₁ y′(b) = B₁, the simple-simple beam problem.The method is based on a second-order convergent method which is used on three grids, sixth-order convergence being obtained by taking a linear combination of the (second-order) numerical results calculated using the three individual grids.Special formulas are proposed for application to points of the discretization adjacent to the boundaries x = a and x= b, the first two terms of the local truncation errors of these formulas being the same as those of the second-order method used at the other points of each grid.Modifications to these two formulas are obtained for problems with boundary conditions of the form y(a) = A₀, y′(a) = C₀, y(b) = A₁, y′(b) = C₁, the clamped-clamped beam problem.The general boundary value problem, for which the differential equation is y^(iv)(x) = f(x, y, y′, y″, y‴), is also considered.     

Gurland's ratio for the gamma function

We consider the ratio T(x, y) = г(x)г(y) / г²((x + y)/2) and its properties related to convexity, logarithmic convexity, Schur-convexity, and complete monotonicity. Several new bounds and asymptotic expansions for T are derived. Sharp bounds for the function x → x/(1 - e^−x) are presented, as well as bounds for the trigamma function. The results are applied to a problem related to the volume of the unit ball in Rⁿ and also to the problem of finding the inverse of the function x → T(1/x, 3/x), which is of importance in applied statistics.     

Sensitivity analysis of the knapsack sharing problem: Perturbation of the weight of an item

In this paper, we study the sensitivity analysis of the optimum of the knapsack sharing problem (KSP) to the perturbation of the weight of an arbitrary item. We determine the interval limits of the weight of each perturbed item using a heuristic approach which reduces the original problem to a series of single knapsack problems. A perturbed item belongs either to an optimal class or to a non-optimal class. We evaluate the performance of the proposed heuristic on a set of problem instances of the literature. Encouraging results are obtained.     

Algebraic approach to the interval linear static identification,tolerance, and control problems,or one more application of kaucher arithmetic

In this paper, theidentification problem, thetolerance problem, and thecontrol problem are treated for the interval linear equation Ax=b. These problems require computing an inner approximation of theunited solution set Σ_??(A, b)={x ∈ ? ⁿ | (?A ∈ A)(Ax ∈ b)}, of thetolerable solution set Σ_??(A, b)={x ∈ ? ⁿ | (?A ∈ A)(Ax ∈ b)}, and of thecontrollable solution set Σ_??(A, b)={x ∈ ? ⁿ | (?b ∈ b)(Ax ∈b)} respectively. Analgebraic approach to their solution is developed in which the initial problem is replaced by that of finding analgebraic solution of some auxiliary interval linear system in Kaucher extended interval arithmetic. The algebraic approach is proved almost always to give inclusion-maximal inner interval estimates of the solutionsets considered. We investigate basic properties of the algebraic solutions to the interval linear systems and propose a number of numerical methods to compute them. In particular, we present the simple and fastsubdifferential Newton method, prove its convergence and discuss numerical experiments.     

Weak Schur numbers and the search for G.W. Walker’s lost partitions

A set A of integers is weakly sum-free if it contains no three distinct elements x,y,z such that x+y=z. Given k≥1, let WS(k) denote the largest integer n for which {1,…,n} admits a partition into k weakly sum-free subsets. In 1952, G.W. Walker claimed the value WS(5)=196, without proof. Here we show WS(5)≥196, by constructing a partition of {1,…,196} of the required type. It remains as an open problem to prove the equality. With an analogous construction for k=6, we obtain WS(6)≥572. Our approach involves translating the construction problem into a Boolean satisfiability problem, which can then be handled by a SAT solver.     

Numerische Lösung von Anfangswertaufgaben gewöhnlicher Differentialgleichungen n-ter Ordnung mittels Einschrittverfahren

In the present paper a new exponentially fitted one-step method is given for the numerical treatment of the initial value problemy ⁽ⁿ⁾=f(x, y, y′, ..., y ^(n?1)),y ^(j) (x ₀)=y ₀ ^(j) j=0, 1, ...n?1. The method is given by a local linearisation off(x, y, y′, ..., y ^(n?1)). Using new functions the solution of a special linear differential equation of then-th order with constant coefficients is transformed in such a way so that it no longer contains numerical singularities. The efficiency of the method is demonstrated by several numerical stiff-examples.     

Asymptotic behaviour of the solutions of second order functional differential equations

This paper presents integral criteria to determine the asymptotic behaviour of the solutions of second order nonlinear differential equations of the type y^″(x)+q(x)f(y(x))=0, with q(x)>0 and f(y) odd and positive for y>0, as x tends to +∞. It also compares them with the results obtained by Chanturia (1975) in [11] for the same problem.     

A Linear Time Algorithm for L(2,1)-Labeling of Trees

An L(2,1)-labeling of a graph G is an assignment f from the vertex set V(G) to the set of nonnegative integers such that |f(x)?f(y)|≥2 if x and y are adjacent and |f(x)?f(y)|≥1 if x and y are at distance 2, for all x and y in V(G). A k-L(2,1)-labeling is an L(2,1)-labeling f:V(G)→{0,…,k}, and the L(2,1)-labeling problem asks the minimum k, which we denote by λ(G), among all possible assignments. It is known that this problem is NP-hard even for graphs of treewidth 2, and tree is one of very few classes for which the problem is polynomially solvable. The running time of the best known algorithm for trees had been O(Δ ^4.5 n) for more than a decade, and an O(min{n ^1.75,Δ ^1.5 n})-time algorithm has appeared recently, where Δ and n are the maximum degree and the number of vertices of an input tree, however, it has been open if it is solvable in linear time. In this paper, we finally settle this problem by establishing a linear time algorithm for L(2,1)-labeling of trees. Furthermore, we show that it can be extended to a linear time algorithm for L(p,1)-labeling with a constant p.     

Geodesic methods in quantitative image analysis

Let X be a part of an image to be analysed. Given two arbitrary points x and y of X, let us define the number d_x(x, y) as follows: d_x(x, y) is the lower bound of the lengths of the arcs in X ending at points x and y, if such arcs exist, and + α if not. The function d_x is an X-intrinsic distance function, called ‘geodesic distance’. Note that if x and y belong to two disjoint connected components of X, d_x(x, y) = + α. In other words, d_x seems to be an appropriate distance function to deal with connectivity problems.In the metric space (X, d_x), all the classical morphological transformations (dilation, erosion, skeletonization, etc.) can be defined. The geodesic distance d_x also provides rigorous definitions of topological transformations, which can be performed by automatic image analysers with the help of parallel iterative algorithms.All these notions are illustrated by several examples (definition of the length of a fibre and of an effective length factor; automatic detection of cells having at least one nucleus or having one single nucleus; definitions of the geodesic center and of the ends of an object without a hole; etc.). The corresponding algorithms are described.     

A reconstruction algorithm for a subclass of instances of the 2-color problem

In the field of Discrete Tomography, the 2-color problem consists in reconstructing a matrix whose elements are of two different types, starting from its horizontal and vertical projections. It is known that the 1-color problem admits a polynomial time reconstruction algorithm, while the c-color problem, with c≥2, is NP-hard. Thus, the 2-color problem constitutes an interesting example of a problem just in the frontier between hard and easy problems.In this paper we define a linear time algorithm (in the size of the output matrix) to solve a subclass of its instances, where some values of the horizontal and vertical projections are constant, while the others are upper bounded by a positive number proportional to the dimension of the problem. Our algorithm relies on classical studies for the solution of the 1-color problem.     

Predictive complexity and information

The notions of predictive complexity and of corresponding amount of information are considered. Predictive complexity is a generalization of Kolmogorov complexity which bounds the ability of any algorithm to predict elements of a sequence of outcomes. We consider predictive complexity for a wide class of bounded loss functions which are generalizations of square-loss function. Relations between unconditional KG(x) and conditional KG(x|y) predictive complexities are studied. We define an algorithm which has some “expanding property”. It transforms with positive probability sequences of given predictive complexity into sequences of essentially bigger predictive complexity. A concept of amount of predictive information IG(y:x) is studied. We show that this information is noncommutative in a very strong sense and present asymptotic relations between values IG(y:x), IG(x:y), KG(x) and KG(y).     

An interactive method for the selection of design criteria and the formulation of optimization problems in computer aided optimal design

This paper presents an interactive method for the selection of design criteria and the formulation of optimization problems within a computer aided optimization process of engineering systems. The key component of the proposed method is the formulation of an inverse optimization problem for the purpose of determining the design preferences of the engineer. These preferences are identified based on an interactive modification of a preliminary optimization result that is the solution of an initial problem statement. A formulation of the inverse optimization problem is presented, which is based on a weighted-sum multi-objective approach and leads to an explicit optimization problem that is computationally inexpensive to solve. Numerical studies on structural shape optimization problems show that the proposed method is able to identify the optimization criteria and the formulation of the optimization problem which drive the interactive user modifications.     

On the moore test for coupled equations

In this paper an improved Moore test for the coupled system:f(x, y)=0,g(x, y)=0 is described: x⁺ is calculated from x and y in a forward-substep, and we use x⁺ and y to compute y⁺ in a backward-substep. It is shown that, if x⁺ ? x, y⁺ ? y, then a solution of the coupled system (x*,y*) ∈ (x⁺, y⁺) exists. On this foundation, we prove convergence of a point iterative algorithm for solving coupled systems.     

A recursive and a grammatical characterization of the exponential-time languages

We characterize the class of all languages which are acceptable in exponential time by means of recursive and grammatical methods. (i) The class of all languages which are acceptable in exponential time is uniquely characterized by the class of all (0-1)-functions which can be generated, starting with the initial functions of the Grzegorczyk-class $\text{E}$², by means of subtitution and limited recursion of the form f(x, y + 1) = h(x, y), f(x, y), f(x, l(x, y))), l(x, y) ? y. (ii) The class of all languages which are acceptable in exponential time is equal to the class of all languages generated by context-sensitive grammars with context-free control sets.     

Some remarks on a conjecture in parameter adaptive control

A.S. Morse has raised the following question: Do there exist differentiable functions

$\text{f:R}{}^2\text{→ R}\text{and}\text{g:R}{}^2\text{→ R}$

with the property that for every nonzero real number λ and every (x₀, y₀) ∈ $\text{R}$² the solution (x(t),y(t)) of

$\text{x}\text{?}\text{(t) = x(t) + λf(x(t),y(t))}$

,

$\text{y}\text{?}\text{(t) = g(x(t),y(t))}$

,

$\text{x(0) = x}{}_0\text{, y(0) = y}{}_0$

, is defined for all t ? 0 and satisfies

$\text{lim}\text{t → + ∞}$

and y(t) is bounded on [0,∞)? We prove that the answer is yes, and we give explicit real analytic functions f and g which work. However, we prove that if f and g are restricted to be rational functions, the answer is no.     

Inapproximability of the Tutte polynomial

The Tutte polynomial of a graph G is a two-variable polynomial T(G;x,y) that encodes many interesting properties of the graph. We study the complexity of the following problem, for rationals x and y: take as input a graph G, and output a value which is a good approximation to T(G;x,y). Jaeger et al. have completely mapped the complexity of exactly computing the Tutte polynomial. They have shown that this is #P-hard, except along the hyperbola (x-1)(y-1)=1 and at four special points. We are interested in determining for which points (x,y) there is a fully polynomial randomised approximation scheme (FPRAS) for T(G;x,y). Under the assumption RP≠NP, we prove that there is no FPRAS at (x,y) if (x,y) is in one of the half-planes x<-1 or y<-1 (excluding the easy-to-compute cases mentioned above). Two exceptions to this result are the half-line x<-1,y=1 (which is still open) and the portion of the hyperbola (x-1)(y-1)=2 corresponding to y<-1 which we show to be equivalent in difficulty to approximately counting perfect matchings. We give further intractability results for (x,y) in the vicinity of the origin. A corollary of our results is that, under the assumption RP≠NP, there is no FPRAS at the point (x,y)=(0,1-λ) when λ>2 is a positive integer. Thus, there is no FPRAS for counting nowhere-zero λ flows for λ>2. This is an interesting consequence of our work since the corresponding decision problem is in P for example for λ=6. Although our main concern is to distinguish regions of the Tutte plane that admit an FPRAS from those that do not, we also note that the latter regions exhibit different levels of intractability. At certain points (x,y), for example the integer points on the x-axis, or any point in the positive quadrant, there is a randomised approximation scheme for T(G;x,y) that runs in polynomial time using an oracle for an NP predicate. On the other hand, we identify a region of points (x,y) at which even approximating T(G;x,y) is as hard as #P.