Inequalities for the Number of Walks in Graphs

We investigate the growth of the number w _k of walks of length k in undirected graphs as well as related inequalities. In the first part, we deduce the inequality w _2a+c ?w _2(a+b)+c ≤w _2a ?w _2(a+b+c), which we call the Sandwich Theorem. It unifies and generalizes an inequality by Lagarias et al. and an inequality by Dress and Gutman. In the same way, we derive the inequality w _2a+c (v,v)?w _2(a+b)+c (v,v)≤w _2a (v,v)?w _2(a+b+c)(v,v) for the number w _k (v,v) of closed walks of length k starting at a given vertex v. We then use a theorem of Blakley and Dixon to show $w_{2\ell+p}^{k}\leq w_{2\ell+pk}\cdot w_{2\ell}^{k-1}$ , which unifies and generalizes an inequality by Erd?s and Simonovits and, again, the inequality by Dress and Gutman. Both results can be translated directly into the corresponding forms using the higher order densities, which extends former results. In the second part, we provide a new family of lower bounds for the largest eigenvalue λ ₁ of the adjacency matrix based on closed walks. We apply the Sandwich Theorem to show monotonicity in this and a related family of lower bounds of Nikiforov. This leads to generalized upper bounds for the energy of graphs. In the third part, we demonstrate that a further natural generalization of the Sandwich Theorem is not valid for general graphs. We show that the inequality w _a+b ?w _a+b+c ≤w _a ?w _a+2b+c does not hold even in very restricted cases like w ₁?w ₂≤w ₀?w ₃ (i.e., $\bar{d}\cdot w_{2}\leq w_{3}$ ) in the context of bipartite or cycle free graphs. In contrast, we show that surprisingly this inequality is always satisfied for trees and we show how to construct worst-case instances (regarding the difference of both sides of the inequality) for a given degree sequence. We also prove the inequality w ₁?w ₄≤w ₀?w ₅ (i.e., $\bar{d}\cdot w_{4}\leq w_{5}$ ) for trees and conclude with a corresponding conjecture for longer walks.     

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.     

Bounded DOL languages

For an alphabet A and a morphism h : A¹ → A¹, the set of words w such that the DOL language L(A, h, w) is a BOUNDED language is shown to be B¹, where B is an effectively computable subset of A. Consequently, BOUNDEDNESS is decidable for DOL languages. The result depends on the authors' recent results on periodic DOL languages. Interpretation of the result for polynomially bounded DOL languages is also considered.     

Border Correlations of Partial Words

Partial words are finite sequences over a finite alphabet A that may contain a number of “do not know” symbols denoted by ?’s. Setting $A_{\diamond}=A\cup\lbrace{\diamond}\rbracePartial words are finite sequences over a finite alphabet A that may contain a number of “do not know” symbols denoted by ⋄’s. Setting A_à=Aè{à}A_{\diamond}=A\cup\lbrace{\diamond}\rbrace , A _⋄ ^* denotes the set of all partial words over A. In this paper, we investigate the border correlation function b:A_à^*?{a,b}^*\beta:A_{\diamond}^{*}\rightarrow\lbrace a,b\rbrace^{*} that specifies which conjugates (cyclic shifts) of a given partial word w of length n are bordered, that is, β(w)=c ₀ c ₁…c _n−1 where c _i =a or c _i =b according to whether the ith cyclic shift σ ⁱ (w) of w is unbordered or bordered. A partial word w is bordered if a proper prefix x ₁ of w is compatible with a proper suffix x ₂ of w, in which case any partial word x containing both x ₁ and x ₂ is called a border of w. In addition to β, we investigate an extension β′:A _⋄ ^*→ℕ^* that maps a partial word w of length n to m ₀ m ₁…m _n−1 where m _i is the length of a shortest border of σ ⁱ (w). Our results extend those of Harju and Nowotka.     

Test sets and checking words for homomorphism equivalence

Given a language L over an alphabet Σ and two homomorphisms g and h, defined on $\text{Σ}{}^1$, we want to decide whether or not g and h are equivalent on L, i.e., whether or not g(w) = h(w) holds for all words w in L. We prove the following results' for the case where Σ consists of two letters. Every language L possesses a finite subset L, such that, for any pair (g, h), g and h are equivalent on L if and only if they are equivalent on L₁. For every language L (with the exception of some trivial cases), there is a word w (not necessarily in L) such that, for any pair (g, h), g and h are equivalent on L if and only if g(w) = h(w). Our constructions are, in general, noneffective. Also some related notions are discussed in the paper.     

Economy of description by parsers,DPDA's,and PDA's

It is shown that there is a sequence of languages E₁, E₂,… such that every correct prefix parser (one which detects errors at the earliest possible moment, e.g., LR or LL parsers) for E_n has size 2^cn, yet a deterministic PDA recognizing E_n exists and has size O(n²). There is another easily described sequence of languages N₁, N₂,… for which N has a nondeterministic PDA of size O(n²), but no deterministic PDA of size less than 2^cn. It is shown moreover, that this latter gap can be made arbitrarily large for different sequences of languages.     

Lower bounds for the smallest singular value

Let A = (a_ij) be an n × n complex matrix. Suppose that G(A), the undirected graph of A, has no isolated vertex. Let E be the set of edges of G(A). We prove that the smallest singular value of A, σ_n, satisfies: σ_n ≥ min σ_ij | (i, j) ∈ E, where g_ij ≡ a_i + a_j − [(a_i − a_j)² + (r_i + c_i)(r_j + c_j)]^1/2/2 with a_i ≡ |a_ii| and r_i,c_i are the i^th deleted absolute row sum and column sum of A, respectively. The result simplifies and improves that of Johnson and Szulc: σ_n ≥ min_i≠j σ_ij. (See [1].)     

On the cubicity of bipartite graphs

A unit cube in k-dimension (or a k-cube) is defined as the Cartesian product R₁×R₂×?×Rk, where each Ri is a closed interval on the real line of the form [ai,ai+1]. The cubicity of G, denoted as cub(G), is the minimum k such that G is the intersection graph of a collection of k-cubes. Many NP-complete graph problems can be solved efficiently or have good approximation ratios in graphs of low cubicity. In most of these cases the first step is to get a low dimensional cube representation of the given graph.It is known that for a graph G, . Recently it has been shown that for a graph G, cub(G)?4(Δ+1)lnn, where n and Δ are the number of vertices and maximum degree of G, respectively. In this paper, we show that for a bipartite graph G=(A∪B,E) with |A|=n₁, |B|=n₂, n₁?n₂, and Δ^′=min{ΔA,ΔB}, where ΔA=maxa∈Ad(a) and ΔB=maxb∈Bd(b), d(a) and d(b) being the degree of a and b in G, respectively, cub(G)?2(Δ^′+2)⌈lnn₂⌉. We also give an efficient randomized algorithm to construct the cube representation of G in 3(Δ^′+2)⌈lnn₂⌉ dimensions. The reader may note that in general Δ^′ can be much smaller than Δ.     

Connectivity-preserving transformations of binary images

A binary image I is B_a, W_b-connected, where a, b ∈ {4, 8}, if its foreground is a-connected and its background is b-connected. We consider a local modification of a B_a, w_b-connected image I in which a black pixel can be interchanged with an adjacent white pixel provided that this preserves the connectivity of both the foreground and the background of I. We have shown that for any (a, b) ∈ {(4, 8), (8, 4), (8, 8)}, any two B_a, w_b-connected images I and J each with n black pixels differ by a sequence of Θ(n²) interchanges. We have also shown that any two B₄, W₄-connected images I and J each with n black pixels differ by a sequence of O(n⁴) interchanges.     

A fast algorithm for computing a longest common increasing subsequence

Let A=〈a₁,a₂,…,am〉 and B=〈b₁,b₂,…,bn〉 be two sequences, where each pair of elements in the sequences is comparable. A common increasing subsequence of A and B is a subsequence 〈ai₁=bj₁,ai₂=bj₂,…,ail=bjl〉, where i₁<i₂<?<il and j₁<j₂<?<jl, such that for all 1?k<l, we have aik<aik+1. A longest common increasing subsequence of A and B is a common increasing subsequence of the maximum length. This paper presents an algorithm for delivering a longest common increasing subsequence in O(mn) time and O(mn) space.     

Weighted aggregation operators based on minimization

Minimization based aggregation operators A_g,D are discussed. Special attention is paid to weighting function g based cases related to some fixed dissimilarity function D. When D₂(x,y)=(x-y)², we recognize mixture operators and we recall some sufficient conditions for g ensuring the monotonicity of A_g,D. For D₁(x,y)=|x-y| and non-decreasing (non-increasing) g, A_g,D is shown to be the upper (lower) median whenever A_g,D is an aggregation operator.     

Managed Agreement: Generalizing two fundamental distributed agreement problems

This paper presents a family of agreement problems called Managed Agreement, which is parameterized by the number of aristocrat nodes in the system; NBAC is a special case of this family when all nodes are aristocrats while Consensus is a special case of this family when there are no aristocrats. The paper also presents a parameterized family of failure detectors F(A) such that F(A) is the weakest failure detector class that enables solving Managed Agreement with a set A of aristocrats in an asynchronous environment.     

Substitutions into propositional tautologies

We prove that there is a polynomial time substitution (y₁,…,yn):=g(x₁,…,xk) with k?n such that whenever the substitution instance A(g(x₁,…,xk)) of a 3DNF formula A(y₁,…,yn) has a short resolution proof it follows that A(y₁,…,yn) is a tautology. The qualification “short” depends on the parameters k and n.     

Improving the efficiency index in enclosing a root of an equation

Recently several algorithms have been developed which achieve high efficiency index in enclosing a root of the equationf(x)=0 in an interval [a, b] over whichf(x) is continuous andf(a)f(b)<0. The highest efficiency index, 1.6686 ..., was achieved in [4] using the inverse cubic interpolation. This paper studies the possibility of improving efficiency index by using high order inverse interpolations. A class of algorithms are presented and the optimal one of the class has achieved the efficiency index 1.7282 ... With a user-given accurary ? and starting with the initial interval [a ₁,b ₁]=[a, b], these algorithms guarantee to find in finitely many iterations an enclosing interval [a _n ,b _n ] that contains a root of the equation and whose lengthb _n –a _n is smaller than ?. Numerical experiments indicate that the new algorithm performs very well in practice.     

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.     

Deterministic Lindenmayer languages,nonterminals and homomorphisms

Lindenmayer systems are a class of parallel rewriting systems originally introduced to model the growth and development of filamentous organisms. Families of languages generated by deterministic Lindenmayer systems (i.e., those in which each string has a unique successor) are investigated. In particular, the use of nonterminals, homomorphisms, and the combination of these are studied for deterministic Lindenmayer systems using one-sided context (D1Ls) and two-sided context (D2Ls). Languages obtained from Lindenmayer systems by the use of nonterminals are called extensions. Typical results are: The closure under letter-to-letter homomorphism of the family of extensions of D1L languages is equal to the family of recursively enumerable languages, although the family of extensions of D1L languages does not even contain all regular languages. Let P denote the restriction that the system does not rewrite a letter as the empty word. The family of extensions of PD2L languages is equal to the family of languages accepted by deterministic linear bounded automata. The closure under nonerasing homomorphism of the family of extensions of PD1L languages does not even contain languages like {a₁,a₂,?, a_n}¹--{λ}, n?2 . The closure of the family of PD1L languages under homomorphisms which map a letter either to itself or to the empty word is equal to the family of recursively enumerable languages. Strict inclusion results follow from necessary conditions for a language to be in one of the considered families. By stating the results in their strongest form, the paper contains a systematic classification of the effect of nonterminals, letter-to-letter homomorphisms, nonerasing homomorphisms and homomorphisms for all the basic types of deterministic Lindenmayer systems using context.     

Truncations of infinite matrices and algebraic series associated with some of grammars

We consider an algebraic system over $\text{R}$[x] of the form X = a₀(x)X^k+ a_k1(x)X+a_k(x), where a₀(x) and a_k(x) are in x$\text{R}$[x] and a_k?1(x) is in x$\text{R}$. Let A be the infinite incidence matrix associated with the algebraic system. Then we prove that the eigenvalues of northwest corner truncations of A are dense in some algebraic curves.Using this we get a result on positive algebraic series. We consider the case that the coefficients of a₁(x)(i = 0,…,k?1, k) are positive. The algebraic series generated by the algebraic system may be viewed as a function in the complex variable x. Then by the above fact we prove that the radius of convergence of the function equals the least positive zero of the modified discriminant of the system.As an application to context free languages we show a procedure for calculating the entropy of some one counter languages. Other applications to Dyck languages and the Lukasiewicz language are also described.