Iterative methods for ill-conditioned Toeplitz matrices

In this paper we study the use of the Sine Transform for preconditioning linear Toeplitz systems. We consider Toeplitz matrices with a real generating function that is nonnegative with only a small number of zeros. Then we can define a preconditioner of the formS _n ΛS _n whereS _n is the matrix describing the discrete Sine transform and Λ is a diagonal matrix. If we have full knowledge aboutf then we can show that the preconditioned system is of bounded condition number independly ofn. We can obtain the same result for the case that we know only the position and order of the zeros off. If we only know the matrix and its coefficientst _j , we present Sine transform preconditioners that show in many examples the same numerical behaviour.     

Crown graphs and subdivision of ladders are odd graceful

A graph G of size q is odd graceful, if there is an injection φ from V(G) to {0, 1, 2, …, 2q?1} such that, when each edge xy is assigned the label or weight |f(x)?f(y)|, the resulting edge labels are {1, 3, 5, …, 2q?1}. This definition was introduced in 1991 by Gnanajothi [3], who proved that the graphs obtained by joining a single pendant edge to each vertex of C _n are odd graceful, if n is even. In this paper, we generalize Gnanajothi's result on cycles by showing that the graphs obtained by joining m pendant edges to each vertex of C _n are odd graceful if n is even. We also prove that the subdivision of ladders S(L _n ) (the graphs obtained by subdividing every edge of L _n exactly once) is odd graceful.     

Lower Bounds on the Randomized Communication Complexity of Read-Once Functions

We prove lower bounds on the randomized two-party communication complexity of functions that arise from read-once boolean formulae. A read-once boolean formula is a formula in propositional logic with the property that every variable appears exactly once. Such a formula can be represented by a tree, where the leaves correspond to variables, and the internal nodes are labeled by binary connectives. Under certain assumptions, this representation is unique. Thus, one can define the depth of a formula as the depth of the tree that represents it. The complexity of the evaluation of general read-once formulae has attracted interest mainly in the decision tree model. In the communication complexity model many interesting results deal with specific read-once formulae, such as DISJOINTNESS and TRIBES. In this paper we use information theory methods to prove lower bounds that hold for any read-once formula. Our lower bounds are of the form n(f)/c^d(f), where n(f) is the number of variables and d(f) is the depth of the formula, and they are optimal up to the constant in the base of the denominator.     

Succinct representation of regular languages by boolean automata

Boolean automata are a generalization of finite automata in the sense that the ‘next state’, i.e. the result of the transition function given a state and a letter, is not just a single state (deterministic automata) or a union of states (nondeterministic automata) but a boolean function of states. Boolean automata accept precisely regular languages; furthermore they correspond in a natural way to certain language equations as well as to sequential networks. We investigate the succinctness of representing regular languages by boolean automata. In particular, we show that for every deterministic automaton A with m states there exists a boolean automaton with [log₂m] states which accepts the reverse of the language accepted by A (m≥1). We also show that for every n≥1 there exists a boolean automation with n states such that the smallest deterministic automaton accepting the same language has 2⁽²ⁿ⁾ states; moreover this holds for an alphabet with only two letters.     

Six Synthesis Methods for Reversible Logic

The (2 ^w )! reversible transformations on w wires, i.e. reversible logic circuits with w inputs and w outputs, together with the action of cascading, form a group, isomorphic to the symmetric group S ₂ ^w . Therefore, we investigate the group S _n as well as one of its subgroups isomorphic to S _n/2 × S _n/2. We then consider the left cosets, the right cosets, and the double cosets generated by the subgroup. Each element of a coset can function as the representative of the coset. The coset can then be considered as the set of all group elements that differ from the representative by merely multiplying (either to the left or to the right or to both sides) by an arbitrary element of the subgroup. Different choices of the coset space and different choices of the coset representatives lead to six different syntheses for implementing an arbitrary reversible logic operation into hardware. Evaluation of all six methods, by means of three different cost functions (gate cost, switch cost, and quantum cost), leads to a best choice.     

More on the controllability of linear time-invariant systems

This study shows that a controllable system [xdot] = Ax + Bu, where x is an n-vector, can be driven from an arbitrary initial condition x(0) = x₀ to an arbitrary final condition x(t_f = x_f by a polynomial control function of degree M = 2r + 1, where r = n ? rank (B), through a polynomial trajectory of degree M. A simple algorithm for finding u by solving a set of linear equations, the solution of which yields the polynomial coefficients, is given.     

Robustness of star graph network under link failure

The star graph is an attractive underlying topology for distributed systems. Robustness of the star graph under link failure model is addressed. Specifically, the minimum number of faulty links, f(n, k), that make every (n − k)-dimensional substar S_n−k faulty in an n-dimensional star network S_n, is studied. It is shown that f(n,1)=n+2. Furthermore, an upper bound is given for f(n, 2) with complexity of O(n³) which is an improvement over the straightforward upper bound of O(n⁴) derived in this paper.     

Uniqueness of reconstruction for Yager's t‐norm combination of probabilistic and possibilistic knowledge

Often, about the same real‐life system, we have both measurement‐related probabilistic information expressed by a probability measure P(S) and expert‐related possibilistic information expressed by a possibility measure M(S). To get the most adequate idea about the system, we must combine these two pieces of information. For this combination, R. Yager—borrowing an idea from fuzzy logic—proposed to use a t‐norm f_&(a,b) such as the product f_&(a,b)=a· b, i.e., to consider a set function f(S)=f_&(P(S),M(S)). A natural question is: can we uniquely reconstruct the two parts of knowledge from this function f(S)? In our previous paper, we showed that such a unique reconstruction is possible for the product t‐norm; in this paper, we extend this result to a general class of t‐norms. © 2011 Wiley Periodicals, Inc.     

Fault-free mutually independent Hamiltonian cycles of faulty star graphs

The star graph interconnection network has been recognized as an attractive alternative to the hypercube for its nice topological properties. Unlike previous research concerning the issue of embedding exactly one Hamiltonian cycle into an injured star network, this paper addresses the maximum number of fault-free mutually independent Hamiltonian cycles in the faulty star network. To be precise, let SG _n denote an n-dimensional star network in which f≤n?3 edges may fail accidentally. We show that there exist (n?2?f)-mutually independent Hamiltonian cycles rooted at any vertex in SG _n if n∈{3, 4}, and there exist (n?1?f)-mutually independent Hamiltonian cycles rooted at any vertex in SG _n if n≥5.     

Entropy of Operators or why Matrix Multiplication is Hard for Depth-Two Circuits

We consider unbounded fanin depth-2 circuits with arbitrary boolean functions as gates. We define the entropy of an operator f:{0,1} ⁿ →{0,1} ^m as the logarithm of the maximum number of vectors distinguishable by at least one special subfunction of f. Our main result is that every depth-2 circuit for f requires at least entropy(f) wires. This is reminiscent of a classical lower bound of Nechiporuk on the formula size, and gives an information-theoretic explanation of why some operators require many wires. We use this to prove a tight estimate Θ(n ³) of the smallest number of wires in any depth-2 circuit computing the product of two n by n matrices over any finite field. Previously known lower bound for this operator was Ω(n ²log n).     

New voting strategies designed for the classification of nucleic sequences

Biological macromolecules, i.e. DNA, RNA and proteins, are coded by strings, called primary structures. During the last decades, the number and the complexity of primary structures are growing exponentially. Analyzing this huge volume of data to extract pertinent knowledge is a challenging task. Data mining approaches can be helpful to reach this goal. In this paper, we present a new data mining approach, called Disclass, based on vote strategies to do classification of primary structures: Let f₁,f₂,...,f_n be families that represent, respectively, n samples of n sets S₁,S₂,...,S_n of primary structures. Let us consider now a new primary structure w that is assumed to belong to one of the n sets S₁,S₂,...,S_n. By using our data mining approach Disclass, the decision to assign the new primary structure w to one of the sets S₁,S₂,...,S_n is taken as follows: (i) During the first step, for each family f_i, 1in, we construct the ambiguously discriminant and minimal substrings (ADMS) associated with this family. Because the family f_i, 1in, is a sample of the set S_i, the obtained ADMS are considered also to be associated with the whole set S_i. During the classification process, the ADMS associated with the set S_i, that are approximate substrings of the new primary structure w, will vote with weighted voices for the set S_i. (ii) During the second step, we compute according to a vote strategy, the voice weights of the different ADMS, constructed during the first step. (iii) Finally, during the last step, the set that has the maximum weight of voices is the set to which we assign the new primary structure w.     

On affine (non)equivalence of Boolean functions

In this paper we construct a multiset S(f) of a Boolean function f consisting of the weights of the second derivatives of the function f with respect to all distinct two-dimensional subspaces of the domain. We refer to S(f) as the second derivative spectrum of f. The frequency distribution of the weights of these second derivatives is referred to as the weight distribution of the second derivative spectrum. It is demonstrated in this paper that this weight distribution can be used to distinguish affine nonequivalent Boolean functions. Given a Boolean function f on n variables we present an efficient algorithm having O(n2²ⁿ ) time complexity to compute S(f). Using this weight distribution we show that all the 6-variable affine nonequivalent bents can be distinguished. We study the subclass of partial-spreads type bent functions known as PS _ap type bents. Six different weight distributions are obtained from the set of PS _ap bents on 8-variables. Using the second derivative spectrum we show that there exist 6 and 8 variable bent functions which are not affine equivalent to rotation symmetric bent functions. Lastly we prove that no non-quadratic Kasami bent function is affine equivalent to Maiorana–MacFarland type bent functions.     

Diagonal polynomials for small dimensions

HereR andN denote respectively the real numbers and the nonnegative integers. Also 0 <n εN, ands(x) =x ₁+...+x _n when x = (x ₁,...,x _n) εR ⁿ. Adiagonal function of dimensionn is a mapf onN ⁿ (or any larger set) that takesN ⁿ bijectively ontoN and, for all x, y inN ⁿ, hasf(x) <f(y) whenevers(x) <s(y). We show that diagonalpolynomials f of dimensionn all have total degreen and have the same terms of that degree, so that the lower-degree terms characterize any suchf. We call two polynomialsequivalent if relabeling variables makes them identical. Then, up to equivalence, dimension two admits just one diagonal polynomial, and dimension three admits just two.     

Randomized function evaluation on a ring

LetR be a unidirectional asynchronous ring ofn identical processors each with a single input bit. Letf be any cyclic nonconstant function ofn boolean variables. Moran and Warmuth (1986) prove that anydeterministic algorithm that evaluatesf onR has communication complexity (n logn) bits. They also construct a family of cyclic nonconstant boolean functions that can be evaluated inO(n logn) bits by a deterministic algorithm.This contrasts with the following new results:

Diagonal polynomials and diagonal orders on multidimensional lattices

HereR andN denote the real numbers and the nonnegative integers, respectively. Alsos(x)=x ₁+···+x _n whenx=(x ₁, …,x _n) inR ⁿ. A mapf:R ⁿ →R is call adiagonal function of dimensionn iff|N ⁿ is a bijection ontoN and, for allx, y inN ⁿ, f(x)<f(y) whens(x)<s(y). Morales and Lew [6] constructed 2 ⁿ⁻² inequivalent diagonal polynomial functions of dimensionn for eachn>1. Here we use new combinatorial ideas to show that numberd _n of such functions is much greater than 2 ⁿ⁻² forn>3. These combinatorial ideas also give an inductive procedure to constructd _n+1 diagonal orderings of {1, …,n}.     

Algorithms for derivation of structurally stable Hamiltonian signed graphs

A graph S_p,q,n refers to a signed graph with p nodes and q edges with n being the number of negative edges. We introduce two theorems to facilitate identification of the complete set of balanced signed graph configurations for any p-node Hamiltonian signed graph in terms of p, q and n. This allows for the development of computational procedures to efficiently determine the structural stability of a signed graph. This is potentially useful for the planning and analysis of complex situations or scenarios which can be depicted as signed graphs. Through the application of the theorems, the state of balance of a signed graph structure or its affinity towards balance can be determined in a more time-efficient manner compared to any explicit enumeration algorithm.     

Improving bounds on link failure tolerance of the star graph

Determination of the minimum number of faulty links, f(n,k), that make every n-k-dimensional sub-star graph S_n-k faulty in an n-dimensional star network S_n, has been the subject of several studies. Bounds on f(n,k) have already been derived, and it is known that f(n,1)=n+2. Here, we improve the bounds on f(n,k). Specifically, it is shown that f(n,k)?(k+1)F(n,k), where F(n,k) is the minimum number of faulty nodes that make every S_n-k faulty in S_n. The complexity of f(n,k) is shown to be O(n²k) which is an improvement over the previously known upper bound of O(n³); this result in a special case leads to f(n,2)=O(n^↑2), settling a conjecture introduced in an earlier paper. A systematic method to derive the labels of the faulty links in case of f(n,1) is also introduced.     

Le trasformazioni razionali di una successione

Sommario Vengono studiate, in forma generale, le trasformazioni di una successione {S _n } che siano esprimibili mediante una funzione razionale dei terminiS _n . Si determinano le caratteristiche della nuova successione ottenuta e, in particolare, si trovano le condizioni perchè la nuova successione abbia lo stesso limite della {S _n } ed nna maggiore rapidità di convergenza.

---

For a given sequence {S _n }, the transformations that can be expressed by a rational function of the termsS _n , are studied in a general way. The characteristics of the new obtained sequence are determined together with the condition that the new sequence have the same limit of {S _n } and a greater rate of convergence.

     

A Property Tester for Tree-Likeness of Quartet Topologies

Property testing is a rapid growing field in theoretical computer science. It considers the following task: given a function f over a domain D, a property ℘ and a parameter 0<ε<1, by examining function values of f over o(|D|) elements in D, determine whether f satisfies ℘ or differs from any one which satisfies ℘ in at least ε|D| elements. An algorithm that fulfills this task is called a property tester. We focus on tree-likeness of quartet topologies, which is a combinatorial property originating from evolutionary tree construction. The input function is f _Q , which assigns one of the three possible topologies for every quartet over an n-taxon set S. We say that f _Q satisfies tree-likeness if there exists an evolutionary tree T whose induced quartet topologies coincide with f _Q . In this paper, we prove the existence of a set of quartet topologies of error number at least c((n) || 4)c{n\choose 4} for some constant c>0, and present the first property tester for tree-likeness of quartet topologies. Our property tester makes at most O(n ³/ε) queries, and is of one-sided error and non-adaptive.     

Edge-fault-tolerant bipancyclicity of Cayley graphs generated by transposition-generating trees

The Cayley graphs on the symmetric group plays an important role in the study of Cayley graphs as interconnection networks. Let Cay(S_n, B) be the Cayley graphs generated by transposition-generating trees. It is known that for any F?E(Cay(S_n, B)), if |F|≤n?3 and n≥4, then there exists a hamiltonian cycle in Cay(Sn, B)?F. In this paper, we show that Cay(S_n, B)?F is bipancyclic if Cay(S_n, B) is not a star graph, for n≥4 and |F|≤n?3.