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.     

An informal introduction to a high level language with applications to interval mathematics

The main problem of interval computations is as follows:given sets of possible valuesX _i for variablesx _i, and an algorithmf:R ⁿ → R, to.estimate the rangef(X ₁, ..,X _n ) of the possible values off(x ₁, ...,x _n ). In many real-life, situations setsX _i are not intervals. To handle such problems, it is desirable to add set data type and operations with sets to a programming language. it is well known that the entire mathematics can be formulated in terms of sets. So, if we already have a set as a data type, why have anything else. The main reason, is that expression in terms of sets is often clumsy. To avoid this clumsiness, it has been suggested to use not only sets, but alsobags (multisets), in which an element can have multiple occurrences. Bags are used in many areas of Computer Science, and recently, several languages have appeared that use the bag as a basic data type. In this paper, we explain the main ideas behind bag languages, and we also show:

· that bag languages are naturally parallelizable, thus leading to a parallelization of the coresponding generalized interval computations;

· and that bag languages can be also helpfully applied to traditional interval computations (where setsX _i are intervals).

     

A generalization of the Schützenberger product of finite monoids

For each n?1, an n-ary product ? on finite monoids is constructed. This product has the following property: Let Σ be a finite alphabet and Σ¹ the free monoid generated by Σ. For i = 1, …,n, let A_i be a recognizable subset of Σ¹, M(A_i) the syntactic monoid of A_n and M(A₁?A_n) the syntactic monoid of the concatenation product A₁?A_n. Then M(A₁?A_n)< ? (M(A₁),…,M(A_n)). The case n = 2 was studied by Schützenberger. As an application of the generalized product, I prove the theorem of Brzozowski and Knast that the dot-depth hierarchy of star-free sets is infinite.     

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].)     

A novel look-ahead optimization strategy for trie-based approximate string matching

This paper deals with the problem of estimating a transmitted string X ^* by processing the corresponding string Y, which is a noisy version of X ^*. We assume that Y contains substitution, insertion, and deletion errors, and that X ^* is an element of a finite (but possibly, large) dictionary, H. The best estimate X ⁺ of X ^*, is defined as that element of H which minimizes the generalized Levenshtein distance D(X, Y) between X and Y such that the total number of errors is not more than K, for all X ∈H. The trie is a data structure that offers search costs that are independent of the document size. Tries also combine prefixes together, and so by using tries in approximate string matching we can utilize the information obtained in the process of evaluating any one D(X _i , Y), to compute any other D(X _j , Y), where X _i and X _j share a common prefix. In the artificial intelligence (AI) domain, branch and bound (BB) schemes are used when we want to prune paths that have costs above a certain threshold. These techniques have been applied to prune, for example, game trees. In this paper, we present a new BB pruning strategy that can be applied to dictionary-based approximate string matching when the dictionary is stored as a trie. The new strategy attempts to look ahead at each node, c, before moving further, by merely evaluating a certain local criterion at c. The search algorithm according to this pruning strategy will not traverse inside the subtrie(c) unless there is a “hope” of determining a suitable string in it. In other words, as opposed to the reported trie-based methods (Kashyap and Oommen in Inf Sci 23(2):123–142, 1981; Shang and Merrettal in IEEE Trans Knowledge Data Eng 8(4):540–547, 1996), the pruning is done a priori before even embarking on the edit distance computations. The new strategy depends highly on the variance of the lengths of the strings in H. It combines the advantages of partitioning the dictionary according to the string lengths, and the advantages gleaned by representing H using the trie data structure. The results demonstrate a marked improvement (up to 30% when costs are of a 0/1 form, and up to 47% when costs are general) with respect to the number of operations needed on three benchmark dictionaries.     

An Efficient Algorithm for the k-Pairwise Disjoint Paths Problem in Hypercubes

A graph G(V, E) (|V|⩾2k) satisfies property A_k if, given k pairs of distinct nodes (s₁, t₁), …, (s_k, t_k) of V(G), there are k mutually node-disjoint paths, one connecting s_i and t_i for each i, 1⩽i⩽k. A necessary condition for any graph to satisfy A_k is that it is (2k−1)-connected. Hypercubes are important interconnection topologies for parallel computation and communication networks. It has been known that hypercubes of dimension n (which are n-connected) satisfy A_⌈n/2⌉. In this paper we give an algorithm which, given k=⌈n/2⌉ pairs of distinct nodes (s₁, t₁), …, (s_k, t_k) in the n-dimensional hypercube, finds the k disjoint paths of length at most n+⌈log n⌉+1 in O(n² log* n) time.     

Communication Complexity of Sum-Type Functions Invariant under Translation

The communication complexity of a function f denotes the number of bits that two processors have to exchange in order to compute f(x, y), when each processor knows one of the variables x and y, respectively. In this paper the deterministic communication complexity of sum-type functions, such as the Hamming distance and the Lee distance, is examined. Here f: X × X → G, where X is a finite set and G is an Abelian group, and the sum-type function f_n:Xⁿ × Xⁿ → G is defined by f_n((x₁, ..., x_n), (y₁, ..., y_n)) = Σⁿ_i=1f(x_i, y_i) Since the functions examined are also translation-invariant, their function matrices are simultaneously diagonalizable and the corresponding eigenvalues can be calculated. This allows to apply a rank lower bound for the communication complexity. The best results are obtained for G = /2 . For prime numbers |X| in this case the communication complexity of all non-trivial sum-type functions is determined exactly. Exact results are also obtained for the parity of the Hamming distance and the parity of the Lee distance. For the Hamming distance and the Lee distance exact results are only obtained for special parameters n and |X|.     

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 Δ.     

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.     

On Reversible Cascades in Scale-Free and Erdős-Rényi Random Graphs

Consider the following cascading process on a simple undirected graph G(V,E) with diameter Δ. In round zero, a set S?V of vertices, called the seeds, are active. In round i+1, i∈?, a non-isolated vertex is activated if at least a ρ∈(0,1] fraction of its neighbors are active in round i; it is deactivated otherwise. For k∈?, let min-seed^(k)(G,ρ) be the minimum number of seeds needed to activate all vertices in or before round k. This paper derives upper bounds on min-seed^(k)(G,ρ). In particular, if G is connected and there exist constants C>0 and γ>2 such that the fraction of degree-k vertices in G is at most C/k ^γ for all k∈?⁺, then min-seed^(Δ)(G,ρ)=O(?ρ ^γ?1|V|?). Furthermore, for n∈?⁺, p=Ω((ln(e/ρ))/(ρn)) and with probability 1?exp(?n ^Ω(1)) over the Erd?s-Rényi random graphs G(n,p), min-seed⁽¹⁾(G(n,p),ρ)=O(ρn).     

Interpolation on quadric surfaces with rational quadratic spline curves

Given a sequence of points {X_i}_i=1ⁿ on a regular quadric S: X^TAX = 0 ⊂ E^d, d ⩾ 3, we study the problem of constructing a G¹ rational quadratic spline curve lying on S that interpolates {X_i}_i=1ⁿ. It is shown that a necessary condition for the existence of a nontrivial interpolant is (X₁^TAX₂)(X_i^TAX_i+1) > 0, i = 1,2…,n − 1. Also considered is a Hermite interpolation problem on the quadric S: a biarc consisting of two conic arcs on S joined with G¹ continuity is used to interpolate two points on S and two associated tangent directions, a method similar to the biarc scheme in the plane (Bolton, 1975) or space (Sharrock, 1987). A necessary and sufficient condition is obtained on the existence of a biarc whose two arcs are not major elliptic arcs. In addition, it is shown that this condition is always fulfilled on a sphere for generic interpolation data.     

The twin domination number in generalized de Bruijn digraphs

Let G=(V,A) be a digraph. A set T of vertices of G is a twin dominating set of G if for every vertex v∈V?T, there exist u,w∈T (possibly u=w) such that arcs (u,v),(v,w)∈A. The twin domination numberγ^∗(G) of G is the cardinality of a minimum twin dominating set of G. In this paper we investigate the twin domination number in generalized de Bruijn digraphs GB(n,d). For the digraphs GB(n,d), we first establish sharp bounds on the twin domination number. Secondly, we give the exact values of the twin domination number for several types of GB(n,d) by constructing minimum twin dominating sets in the digraphs. Finally, we present sharp upper bounds for some special generalized de Bruijn digraphs.     

Empirical Bayes estimation of the scale parameter in a Pareto distribution

Let f(xθ) = αθ^αx^−(α+1)I(x>θ) be the pdf of a Pareto distribution with known shape parameter α>0, and unknown scale parameter θ. Let {(X_i, θ_i)} be a sequence of independent random pairs, where X_i's are independent with pdf f(xα_i), and θ_i are iid according to an unknown distribution G in a class of distributions whose supports are included in an interval (0, m), where m is a positive finite number. Under some assumption on the class and squared error loss, at (n + 1)th stage we construct a sequence of empirical Bayes estimators of θ_n+1 based on the past n independent observations X₁,…, X_n and the present observation X_n+1. This empirical Bayes estimator is shown to be asymptotically optimal with rate of convergence O(n^−1/2). It is also exhibited that this convergence rate cannot be improved beyond n^−1/2 for the priors in class .     

Moment inequalities for random variables in computational geometry

LetX ₁,...,X _n be independent identically distributedR ^d -valued random vectors, and letA _n =A(X ₁,...,X _n ) be a subset of {X ₁,...,X _n }, invariant under permutations of the data, and possessing the inclusion property (X ₁ ∈A _n impliesX ₁ ∈A _i for alli≤n). For example, the convex hull, the collection of all maximal vectors, the set of isolated points and other structures satisfy these conditions. LetN _n be the cardinality ofA _n . We show that for allp≥1, there exists a universal constantC _p >0 such thatE(N _n ^p )≤C _p max (1,E ^p ) where . This complements Jensen's lower bound for thep-th moment:E(N _n ^p )≥E ^p (N _n ). The inequality is applied to the expected time analysis of algorithms in computational geometry. We also give necessary and sufficient conditions onE(N _n ) for linear expected time behaviour of divide-and-conquer methods for findingA _n .     

Integrability,degenerate centers,and limit cycles for a class of polynomial differential systems

We consider the class of polynomial differential equations x˙ P_n(x,y)+P_n+1(x,y)+P_n+2(x,y), y˙=Q_n(x,y)+Q_n+1(x,y)+Q_n+2(x,y), for n ≥ 1 and where P_i and Q_i are homogeneous polynomials of degree i These systems have a linearly zero singular point at the origin if n > 2. Inside this class, we identify a new subclass of Darboux integrable systems, and some of them having a degenerate center, i.e., a center with linear part identically zero. Moreover, under additional conditions such Darboux integrable systems can have at most one limit cycle. We provide the explicit expression of this limit cycle.     

On multiplication in algebraic extension fields

In this paper we characterize all algorithms for obtaining the coefficients of (Σ^n?1_i=0x_iuⁱ)(Σ^n?1_i=0y_iuⁱ) mod P(u), where P(u) is an irreducible po lynomial of degree n, which use 2n ? 1 multiplications. It is shown that up to equivalence, all such algorithms are obtainable by first obtaining the coefficients of the product of two polynomials, and then reducing modulo the irreducible polynomial.     

Binding number and Hamiltonian (g,f)-factors in graphs II

A (g, f)-factor F of a graph G is called a Hamiltonian (g, f)-factor if F contains a Hamiltonian cycle. For a subset X of V(G), let N _G (X)= gcup _x∈X N _G (x). The binding number of G is defined by bind(G)=min{| N _G (X) |/| X|| ?≠X?V(G), N _G (X)≠V(G)}. Let G be a connected graph of order n, 3≤a≤b be integers, and b≥4. Let g, f be positive integer-valued functions defined on V(G), such that a≤g(x)≤f(x)≤b for every x∈V(G). Suppose n≥(a+b?4)²/(a?2) and f(V(G)) is even, we shall prove that if bind(G)>((a+b?4)(n?1))/((a?2)n?(5/2)(a+b?4)) and for any independent set X?V(G), N _G (X)≥((b?3)n+(2a+2b?9)| X|)/(a+b?5), then G has a Hamiltonian (g, f)-factor.     

An SDP Primal-Dual Algorithm for Approximating the Lovász-Theta Function

The Lovász ?-function (Lovász in IEEE Trans. Inf. Theory, 25:1–7, 1979) of a graph G=(V,E) can be defined as the maximum of the sum of the entries of a positive semidefinite matrix X, whose trace Tr(X) equals 1, and X _ij =0 whenever {i,j}∈E. This function appears as a subroutine for many algorithms for graph problems such as maximum independent set and maximum clique. We apply Arora and Kale’s primal-dual method for SDP to design an algorithm to approximate the ?-function within an additive error of δ>0, which runs in time $O(\frac{\vartheta ^{2} n^{2}}{\delta^{2}} \log n \cdot M_{e})$ , where ?=?(G) and M _e =O(n ³) is the time for a matrix exponentiation operation. It follows that for perfect graphs G, our primal-dual method computes ?(G) exactly in time O(? ² n ⁵logn). Moreover, our techniques generalize to the weighted Lovász ?-function, and both the maximum independent set weight and the maximum clique weight for vertex weighted perfect graphs can be approximated within a factor of (1+?) in time O(? ^?2 n ⁵logn).     

On n-Dimensional Sequences. I

Let R be a commutative ring and let n ≥ 1. We study Γ(s), the generating function and Ann(s), the ideal of characteristic polynomials of s, an n-dimensional sequence over R .We express f(X₁,…,X_n) · Γ(s)(X^-1₁,…,X^-1_n) as a partitioned sum. That is, we give (i) a 2ⁿ-fold "border" partition (ii) an explicit expression for the product as a 2ⁿ-fold sum; the support of each summand is contained in precisely one member of the partition. A key summand is βo(f, s), the "border polynomial" of f and s, which is divisible by X₁ … X_n.We say that s is eventually rectilinear if the elimination ideals Ann(s)∩R[X_i] contain an f_i (X_i) for 1 ≤ i ≤ n. In this case, we show that Ann(s) is the ideal quotient ($\text{∑}{}^{\mathrm{n}}{}_{\mathrm{i}}\text{=1(fi) : βo(f, s)/(X}{}_1\text{… X}{}_{\mathrm{n}}\text{)}$).When R and R[[X₁, X₂ ,…, X_n]] are factorial domains (e.g. R a principal ideal domain or F [X₁,…, X_n]), we compute the monic generator γ_i of Ann(s) ∩ R[X_i] from known f_i ϵ Ann(s) ∩ R[X_i] or from a finite number of 1-dimensional linear recurring sequences over R. Over a field F this gives an O($\text{∏}{}_{\mathrm{n}}{}^{\mathrm{i}}\text{=1 δγ}{}^3{}_{\mathrm{i}}$) algorithm to compute an F-basis for Ann(s).     

On the RAS-algorithm

Given a nonnegative real (m, n) matrixA and positive vectorsu, v, then the biproportional constrained matrix problem is to find a nonnegative (m, n) matrixB such thatB=diag (x) A diag (y) holds for some vectorsx ∈ ? ^m andy ∈ ? ⁿ and the row (column) sums ofB equalu _i (v _j )i=1,...,m(j=1,..., n). A solution procedure (called the RAS-method) was proposed by Bacharach [1] to solve this problem. The main disadvantage of this algorithm is, that round-off errors slow down the convergence. Here we present a modified RAS-method which together with several other improvements overcomes this disadvantage.