An NC algorithm for recognizing tree adjoining languages

A parallel algorithm is presented for recognizing the class of languages generated by tree adjoining grammars, a tree rewriting system which has applications in natural language processing. This class of languages is known to properly include all context-free languages; for example, the noncontext-free sets {a ⁿ b ⁿ c ⁿ } and {ww} are in this class. It is shown that the recognition problem for tree adjoining languages can be solved by a concurrent read, concurrent write parallel random-access machine (CRCW PRAM) inO(logn) time using polynomially many processors. Thus, the class of tree adjoining languages is inAC ¹ and hence inNC. This extends a previous result for context-free languages.This research was supported in part by NSF Grants IRI 92-96249, MCS 82-19116-CER, MCS 82-07294, DCR 84-10413, MCS 83-05221, ARO Grant DAA29-84-9-0027, DARPA Grant N00014-85-K-0018, and by the New Jersey Institute of Technology under Grant Nos. 421690 and 211665.     

Bounded underapproximations

We show a new and constructive proof of the following language-theoretic result: for every context-free language L, there is a bounded context-free language L′⊆L which has the same Parikh (commutative) image as L. Bounded languages, introduced by Ginsburg and Spanier, are subsets of regular languages of the form w₁^*w₂^*?w_m^*w_{1}^{*}w_{2}^{*}\cdots w_{m}^{*} for some w ₁,…,w _m ∈Σ ^∗. In particular bounded context-free languages have nice structural and decidability properties. Our proof proceeds in two parts. First, we give a new construction that shows that each context free language L has a subset L _N that has the same Parikh image as L and that can be represented as a sequence of substitutions on a linear language. Second, we inductively construct a Parikh-equivalent bounded context-free subset of L _N .     

Fast Algorithms for the Density Finding Problem

We study the problem of finding a specific density subsequence of a sequence arising from the analysis of biomolecular sequences. Given a sequence A=(a ₁,w ₁),(a ₂,w ₂),…,(a _n ,w _n ) of n ordered pairs (a _i ,w _i ) of numbers a _i and width w _i >0 for each 1≤i≤n, two nonnegative numbers ℓ, u with ℓ≤u and a number δ, the Density Finding Problem is to find the consecutive subsequence A(i ^*,j ^*) over all O(n ²) consecutive subsequences A(i,j) with width constraint satisfying ℓ≤w(i,j)=∑ _r=i ^j w _r ≤u such that its density is closest to δ. The extensively studied Maximum-Density Segment Problem is a special case of the Density Finding Problem with δ=∞. We show that the Density Finding Problem has a lower bound Ω(nlog n) in the algebraic decision tree model of computation. We give an algorithm for the Density Finding Problem that runs in optimal O(nlog n) time and O(nlog n) space for the case when there is no upper bound on the width of the sequence, i.e., u=w(1,n). For the general case, we give an algorithm that runs in O(nlog ² m) time and O(n+mlog m) space, where and w _min=min  _r=1 ⁿ w _r . As a byproduct, we give another O(n) time and space algorithm for the Maximum-Density Segment Problem. Grants NSC95-2221-E-001-016-MY3, NSC-94-2422-H-001-0001, and NSC-95-2752-E-002-005-PAE, and by the Taiwan Information Security Center (TWISC) under the Grants NSC NSC95-2218-E-001-001, NSC95-3114-P-001-002-Y, NSC94-3114-P-001-003-Y and NSC 94-3114-P-011-001.     

The Fully Polynomial Approximation Algorithm for the 0-1 Knapsack Problem

A modified fast approximation algorithm for the 0-1 knapsack problem with improved complexity is presented, based on the schemes of Ibarra, Kim and Babat. By using a new partition of items, the algorithm solves the n -item 0-1 knapsack problem to any relative error tolerance ε > 0 in the scaled profit space P ^* /K = O ( 1/ ε ^1+δ ) with time O(n log(1/ ε )+1/ ε^{2+2δ}) and space O(n +1/ ɛ^{2+δ}), where P^{*} and b are the maximal profit and the weight capacity of the knapsack problem, respectively, K is a problem-dependent scaling factor, δ={α}/(1+α) and α=O( log b ). This algorithm reduces the exponent of the complexity bound in [5].     

Improved computation of plane Steiner Minimal Trees

ASteiner Minimal Tree (SMT) for a given setA = {a ₁,...,a _n } in the plane is a tree which interconnects these points and whose total length, i.e., the sum of lengths of the branches, is minimum. To achieve the minimum, the tree may contain other points (Steiner points) besidesa ₁,...,a _n . Various improvements are presented to an earlier computer program of the authors for plane SMTs. These changes have radically reduced machine times. The existing program was limited in application to aboutn = 30, while the innovations have facilitated solution of many randomly generated 100-point problems in reasonable processing times.This work was supported by the Canadian Natural Sciences and Engineering Council under Grant Numbers A-7544 and A-7558.     

Lower Bounds for Agnostic Learning via Approximate Rank

We prove that the concept class of disjunctions cannot be pointwise approximated by linear combinations of any small set of arbitrary real-valued functions. That is, suppose that there exist functions f₁, ?, f_r\phi_{1}, \ldots , \phi_{r} : {− 1, 1}ⁿ → \mathbbR{\mathbb{R}} with the property that every disjunction f on n variables has $\|f - \sum\nolimits_{i=1}^{r} \alpha_{i}\phi _{i}\|_{\infty}\leq 1/3$\|f - \sum\nolimits_{i=1}^{r} \alpha_{i}\phi _{i}\|_{\infty}\leq 1/3 for some reals a₁, ?, a_r\alpha_{1}, \ldots , \alpha_{r}. We prove that then $r \geq exp \{\Omega(\sqrt{n})\}$r \geq exp \{\Omega(\sqrt{n})\}, which is tight. We prove an incomparable lower bound for the concept class of decision lists. For the concept class of majority functions, we obtain a lower bound of W(2ⁿ/n)\Omega(2^{n}/n) , which almost meets the trivial upper bound of 2ⁿ for any concept class. These lower bounds substantially strengthen and generalize the polynomial approximation lower bounds of Paturi (1992) and show that the regression-based agnostic learning algorithm of Kalai et al. (2005) is optimal.     

Batch scheduling of step deteriorating jobs

In this paper we consider the problem of scheduling n jobs on a single machine, where the jobs are processed in batches and the processing time of each job is a step function depending on its waiting time, which is the time between the start of the processing of the batch to which the job belongs and the start of the processing of the job. For job i, if its waiting time is less than a given threshold value D, then it requires a basic processing time a _i ; otherwise, it requires an extended processing time a _i +b _i . The objective is to minimize the completion time of the last job. We first show that the problem is NP-hard in the strong sense even if all b _i are equal, it is NP-hard even if b _i =a _i for all i, and it is non-approximable in polynomial time with a constant performance guarantee Δ<3/2, unless . We then present O(nlog n) and O(n ^3F−1log n/F ^F ) algorithms for the case where all a _i are equal and for the case where there are F, F≥2, distinct values of a _i , respectively. We further propose an O(n ²log n) approximation algorithm with a performance guarantee for the general problem, where m ^* is the number of batches in an optimal schedule. All the above results apply or can be easily modified for the corresponding open-end bin packing problem.     

Time-Space Tradeoff in Derandomizing Probabilistic Logspace

Nisan showed that any randomized logarithmic space algorithm (running in polynomial time and with two-sided error) can be simulated by a deterministic algorithm that runs simultaneously in polynomial time and Θ(log² n) space. Subsequently Saks and Zhou improved the space complexity and showed that a deterministic simulation can be carried out in space Θ(log^1.5n). However, their simulation runs in time n^{Θ(log^{0.5}n)}. We prove a time--space tradeoff that interpolates these two simulations. Specifically, we prove that, for any 0 ≤ α ≤ 0.5, any randomized logarithmic space algorithm (running in polynomial time and with two-sided error) can be simulated deterministically in time n^{O(log^{0.5-α}n)} and space O(log^{1.5+α}n). That is, we prove that BPL ⊆ DTISP[n^{O(log^{0.5-α}n)}, O(log^1.5+αn)].     

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.     

A strong pumping lemma for context-free languages

A context-free language is shown to be equivalent to a set of sentences describable by sequences of strings related by finite substitutions on finite domains, and vice-versa. As a result, a necessary and sufficient version of the Classic Pumping Lemma is established. This result provides a guaranteed method of proving that a language is not context-free when such is the case. An example is given of a language which neither the Classic Pumping Lemma nor Parikh's Theorem can show to be non-context-free, although Ogden's Lemma can. The main result also establishes {aⁿba^mn} as a language which is not in the Boolean closure of deterministic context-free languages.     

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.

     

Sub-Constant Error Probabilistically Checkable Proof of Almost-Linear Size

We show a construction of a PCP with both sub-constant error and almost-linear size. Specifically, for some constant 0 < α < 1, we construct a PCP verifier for checking satisfiability of Boolean formulas that on input of size n uses log n+O((log n)^1-a)\log\, n+O((\log\, n)^{1-\alpha}) random bits to make 7 queries to a proof of size n·2^{O((log n)1-a)}n·2^{O((\log\, n)^{1-\alpha})}, where each query is answered by O((log n)^1-a)O((\log\, n)^{1-\alpha}) bit long string, and the verifier has perfect completeness and error 2^{-W((log n)a)}2^{-\Omega((\log\, n)^{\alpha})}.     

A random riemann zeta function and intersymbol interference

The probability density function (PDF) of z = Σa_nn^?α with n = 1,2,…∞ is considered where {a_n} are independent, identically distributed, zero mean random variables with equally likely values of ± 1. For $\text{1}\text{2}\text{< α ? 1}$ the series diverges; for 1 < α∞ the series converges. For the second situation, the associated characteristic function is bandlimited and we employ a sampling expansion to evaluate the PDF. Both cumulants and moments of z are evaluated. The error probability associated with the sequence is glen considered.     

Quantitative Separation Logic and Programs with Lists

This paper presents an extension of a decidable fragment of Separation Logic for singly-linked lists, defined by Berdine et al. (2004). Our main extension consists in introducing atomic formulae of the form ls ^k (x, y) describing a list segment of length k, stretching from x to y, where k is a logical variable interpreted over positive natural numbers, that may occur further inside Presburger constraints. We study the decidability of the full first-order logic combining unrestricted quantification of arithmetic and location variables. Although the full logic is found to be undecidable, validity of entailments between formulae with the quantifier prefix in the language $^* {$_\mathbbN, "_\mathbbN}^*\exists^* \{\exists_{\bf \mathbb{N}}, \forall_{\bf \mathbb{N}}\}^* is decidable. We provide here a model theoretic method, based on a parametric notion of shape graphs. We have implemented our decision technique, providing a fully automated framework for the verification of quantitative properties expressed as pre- and post-conditions on programs working on lists and integer counters.     

Parameterization of the chlorophyll a-specific in vivo light absorption coefficient covering estuarine,coastal and oceanic waters

We evaluated models predicting the spectral chlorophyll-a (Chl a)-specific absorption coefficient (a* _ph (λ)) from Chl a concentration [Chl a] on the basis of 465 phytoplankton absorption spectra collected in estuarine, coastal and oceanic waters. A power model on ln-transformed data provided the best model fit compared to a power model on non-transformed data previously applied to parameterize the relationship between a* _ph (λ) and [Chl a]. The variation in a* _ph (λ) was parameterized over four orders of magnitude in [Chl a] (0.01-100 mg Chl a m^?3) producing a 13-fold range in a* _ph (0.19 to 0.015 m² mg^?1 Chl a) at 440 nm, the peak absorption of Chl a in the blue part of the spectrum. The variations in the modelled a* _ph spectra were within realistic predictions of a* _ph (λ) and the model satisfactorily reproduced the spectral flattening with increasing [Chl a]. The parameterization of a* _ph (λ) confirmed the indirect dependency of a* _ph (λ) on [Chl a] through co-variations between [Chl a] with pigment packaging and pigment composition. Although pigment packaging determined the spectral flattening, analysis of absorption ratios revealed a systematic change in pigment composition with profound influence on the variability of a* _ph in the 440 to 495 nm region. Modelled spectra deviated by approximately 20% from the measured spectra on average and model accuracy was independent of [Chl a]. Although the model cannot fully replace spectral measurements of phytoplankton absorption, it does permit realistic reconstructions of a* _ph (λ) from simple measurements of [Chl a] sampled in estuarine, coastal and oceanic waters.     

On covering problems of codes

LetC be a binary code of lengthn (i.e., a subset of {0, 1} ⁿ ). TheCovering Radius of C is the smallest integerr such that each vector in {0, 1} ⁿ is at a distance at mostr from some code word. Our main result is that the decision problem associated with the Covering Radius of arbitrary binary codes is NP-complete. This result is established as follows. TheRadius of a binary codeC is the smallest integerr such thatC is contained in a radius-r ball of the Hamming metric space 〈{0, 1} ⁿ ,d〉. It is known [K] that the problems of computing the Radius and the Covering Radius are equivalent. We show that the 3SAT problem is polynomially reducible to the Radius decision problem. A central tool in our reduction is a metrical characterization of the set ofdoubled vectors of length 2n: {v=(v ₁ v ₂ …v _2n ) | ∀i:v _2i =v _2i−1}. We show that there is a setY ⊂ {0, 1}²ⁿ such that for everyv ε {0, 1}²ⁿ :v is doubled iffY is contained in the radius-n ball centered atv; moreover,Y can be constructed in time polynomial inn.     

Lanczos <Emphasis Type="Italic">τ</Emphasis>-method regularization algorithm and its algebraic-programming implementation

An algebraic algorithm is developed for computing an algebraic polynomial y _n of order n ∈ N in computer algebra systems. This polynomial is the optimal approximation of the solution y = y(x), x ∈ [a,b], to a system of linear differential equations with polynomial coefficients and initial conditions at a regular singular zero point of this equation in a space C_{[ a,b ]}^k C_{\left[ {a,b} \right]}^k .     

Markov games with unknown random state‐actions‐dependent discount factors: Empirical estimation

The work deals with a class of discrete‐time zero‐sum Markov games under a discounted optimality criterion with random state‐action‐dependent discount factors of the form , where x_n,a_n,b_n, and ξ_n+1 are the state, the actions of players, and a random disturbance at time n, respectively, taking values in Borel spaces. The one‐stage payoff is assumed to be possibly unbounded. In addition, the process {ξ_n} is formed by observable, independent, and identically distributed random variables with common distribution θ, which is unknown to players. By using the empirical distribution to estimate θ, we introduce a procedure to approximate the value V^? of the game; such a procedure yields construction schemes of stationary optimal strategies and asymptotically optimal Markov strategies.     

Ein kubisch konvergentes Einschließungsverfahren zur Inversion positiver Elemente

The iteration $$y_{n + 1} = \sup (y_n ,x_n + x_n (e - ax_n )),x_{n + 1} = \inf (x_n ,x_n + y_{n + 1} (e - ax_n ))$$ generating sequences (x _n ) and (y _n ) is considered in normed, partially ordered rings. Under certain conditions it is shown, that the inversea ^?1 of an elementa≧0 is monotonously enclosed and that both sequences converge toa ^?1 with the order three.