Diagnostics on LALR(k) conflicts based on a method for LR(k) Testing

A user of an LALR(k) parser generator system may have difficulties in understanding how a given LALR(k) conflict is generated. This is especially difficult if the conflict does not correspond to an LR(k) conflict.A practical method for giving informative diagnostics on LALR(k) conflicts is presented. The diagnostics distinguish between those LALR(k) conflicts that correspond to LR(k) conflicts and those that do not. As a side effect the user is thus informed whether or not his grammar is in fact LR(k) despite not being LALR(k).The method is based on an algorithm for testing LR(k)-ness using the LR(0) machine supplied with LALR(k) lookahead sets. This algorithm is presented and its correctness is proved.     

Competitive Parallel Disk Prefetching and Buffer Management

We provide a competitive analysis framework for online prefetching and buffer management algorithms in parallel I/O systems, using a read-once model of block references. This has widespread applicability to key I/O-bound applications such as external merging and concurrent playback of multiple video streams. Two realistic lookahead models, global lookahead and local lookahead, are defined. Algorithms NOM and GREED, based on these two forms of lookahead are analyzed for shared buffer and distributed buffer configurations, both of which occur frequently in existing systems. An important aspect of our work is that we show how to implement both of the models of lookahead in practice using the simple techniques of forecasting and flushing.Given a D-disk parallel I/O system and a globally shared I/O buffer that can hold up to M disk blocks, we derive a lower bound of on the competitive ratio of any deterministic online prefetching algorithm with O(M) lookahead. NOM is shown to match the lower bound using global M-block lookahead. In contrast, using only local lookahead results in an Ω(D) competitive ratio. When the buffer is distributed into D portions of M/D blocks each, the algorithm GREED based on local lookahead is shown to be optimal, and NOM is within a constant factor of optimal. Thus we provide a theoretical basis for the intuition that global lookahead is more valuable for prefetching in the case of a shared buffer configuration, whereas it is enough to provide local lookahead in the case of a distributed configuration. Finally, we analyze the performance of these algorithms for reference strings generated by a uniformly-random stochastic process and we show that they achieve the minimal expected number of I/Os. These results also give bounds on the worst-case expected performance of algorithms which employ randomization in the data layout.     

Computation Models for Parameterized Complexity

A parameterized computational problem is a set of pairs (x, k), where k is a distinguished item called “parameter”. FPT is the class of fixed-parameter tractable problems: for any fixed value of k, they are solvable in time bounded by a polynomial of degree α, where α is a constant not dependent on the parameter. In order to deal with parameterized intractability, Downey and Fellows have introduced a hierarchy of classes W[l] ? W[2] ? ? containing likely intractable parameterized problems, and they have shown that such classes have many natural, complete languages. In this paper we analyze several variations of the halting problem for nondeterministic Turing machines with parameterized time, and we show that its parameterized complexity strongly depends on some resources like the number of tapes, head and internal states, and on the size of the alphabet. Notice that classical polynomial-time complexity fails in distinguishing such features. As byproducts, we show that parameterized complexity is a useful tool for the study of the intrinsic power of some computational models, and we underline the different “computational powers” of some levels of the parameterized hierarchy.     

Stability of control systems with a moving optimization interval for a class of nonlinear plants

We investigate the stability of the control system with a moving optimization interval for a nonlinear discrete dynamic plant with additive controls. Sufficient stability conditions are derived for a control system with an arbitrary finite lookahead interval.Translated from Vychislitel'naya i Prikladnaya Matematika, No. 63, pp. 116–118, 1987.     

Generation of the Exact Distribution and Simulation of Matched Nucleotide Sequences on a Phylogenetic Tree

Nucleotide sequences are often generated by Monte Carlo simulations to address complex evolutionary or analytic questions but the simulations are rarely described in sufficient detail to allow the research to be replicated. Here we briefly review the Markov processes of substitution in a pair of matching (homologous) nucleotide sequences and then extend it to k matching nucleotide sequences. We describe calculation of the joint distribution of nucleotides of two matching sequences. Based on this distribution, we give a method for simulation of the divergence matrix for n sites using the multinomial distribution. This is then extended to the joint distribution for k nucleotide sequences and the corresponding 4 ^k divergence array, generalizing Felsenstein (Journal of Molecular Evolution, 17, 368–376, 1981), who considered stationary, homogeneous and reversible processes on trees. We give a second method to generate matched sequences that begins with a random ancestral sequence and applies a continuous Markov process to each nucleotide site as in Rambaut and Grassly (Computer Applications in the Biosciences, 13, 235–238, 1997); further, we relate this to an equivalent approach based on an embedded Markov chain. Finally, we describe an approximate method that was recently implemented in a program developed by Jermiin et al. (Applied Bioinformatics, 2, 159–163, 2003). The three methods presented here cater for different computational and mathematical limitations and are shown in an example to produce results close to those expected on theoretical grounds. All methods are implemented using functions in the S-plus or R languages.     

Approximation of singular series and automata

A constant of the form , where the product ranges over all sufficiently large primes p and h is rational, is an example of a singular series. We show that this type of singular series can be expanded in the form , where ζ denotes the zeta-function and e _k is an integer and use this to numerically approximate them. Gerhard Niklasch in an appendix describes how to obtain more than 1000 decimal accuracy. In some cases the coefficients $e_k$ turn out to be related to conjugacy classes of primitive words in cyclic languages. Received: 12 April 1999 / Revised version: 23 October 1999     

On stability of Hamilton‐connectedness under the 2‐closure in claw‐free graphs

It is easy to characterize chordal graphs by every k‐cycle having at least f(k) = k ? 3 chords. I prove new, analogous characterizations of the house‐hole‐domino‐free graphs using f(k) = 2?(k ? 3)/2?, and of the graphs whose blocks are trivially perfect using f(k) = 2k ? 7. These three functions f(k) are optimum in that each class contains graphs in which every k‐cycle has exactly f(k) chords. The functions 3?(k ? 3)/3? and 3k ? 11 also characterize related graph classes, but without being optimum. I consider several other graph classes and their optimum functions, and what happens when k‐cycles are replaced with k‐paths. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:137‐147, 2011     

Uniquelyk-arborable graphs

A graph is uniquelyk-arborable if its point-arboricity isk and there is only one acyclic partition of its point set intok subsets. Several properties of uniquelyk-arborable graphs are presented. One such property is that uniquelyk-arborable graphs are (k−1)-connected. Furthermore, it is shown that for any positive integerk there is a uniquelyk-arborable graph which is notk-connected.     

Disjunctive splittability of languages

Decompositions of languages over a finite alphabetX are investigated. Let T be a class of languages overX satisfying the following condition: (#) T contains at least one dense language, and every dense subset of an element in T is again in T. A language is said to be DT-splittable if it is a disjoint union of infinitely many discrete disjunctive languages in T which are locally finite of rank 1. It is shown that a language is DT-splittable if and only if it is a union of dense languages in T. The class P of all prefix codes satisfies the condition (#). DP-splittability of languages is investigated in detail. A language A is said to besemi-DT-splittable if A\F is DT-splittable for some finite languageF. Semi-DP-splittability is investigated. Semi-DP-splittability of catenations of languages is also studied.     

Semiample and k-ample vector bundles

Abstract

The main result of this paper is that tensor products of semiample vector bundles over compact complex manifolds are semiample. An easy proof yields the analogous result for direct sums. We also show that tensor products of semiample vector bundles with k-ample vector bundles in the sense of Sommese are k-ample. On the other hand, we show that it is not generally true that tensor products of nef and k-ample vector bundles for positive k are still k-ample. Results of Sommese on k-ampleness are consequently strengthened. As an application of our main theorem we extend to k-ample the vanishing theorem of Ein-Lazarsfeld.     

Onk-order harmonic new better than used in expectation distributions

Summary Definitions ofk-HNBUE andK-HNWUE are introduced and the relationship with other class of life distributions is studied. Various closure properties ofk-HNBUE (k-HNWUE) are proved. Finally bounds on the moments and survival function ofk-HNBUE (k-HNWUE) are given. This research was supported by the ONR Grant N00014-78-C-0655.     

Twisted Planes

Let k be a commutative ring. We find and characterize a new family of twisted planes (i.e., associative unitary k-algebra structures on the k-module k[X, Y], having k[X] and k[Y] as subalgebras). Similar results are obtained for the k-module of two variables power series k[[X, Y]].     

A common generalization of line graphs and clique graphs

Both the line graph and the clique graph are defined as intersection graphs of certain families of complete subgraphs of a graph. We generalize this concept. By a k-edge of a graph we mean a complete subgraph with k vertices or a clique with fewer than k vertices. The k-edge graph Δ_k(G) of a graph G is defined as the intersection graph of the set of all k-edges of G. The following three problems are investigated for k-edge graphs. The first is the characterization problem. Second, sets of graphs closed under the k-edge graph operator are found. The third problem is the question of convergence: What happens to a graph if we take iterated k-edge graphs?     

Short maximal chains in the lattice of clones over a finite set

Let ??_k (3 ≦ k < ?₀) denote the lattice of clones of finitary operations on a k-element set. One interesting characteristic of the uncountable lattice ??_k is the minimum l_k of the cardinalities of maximal chains in ??_k. It is known that for k prime l_k = 5. In this paper the 5-element maximal chains contained in ??_k are investigated. It is proved that for k composite l_k ≧ 6 while for k prime there are exactly (k–2)! (k + 4) 5-element maximal chains in ??_k, each closely related to a group operation.     

k-systems, k-networks and k-covers

The concepts of k-systems, k-networks and k-covers were defined by A. Arhangel’skii in 1964, P. O’Meara in 1971 and R. McCoy, I. Ntantu in 1985, respectively. In this paper the relationships among k-systems, k-networks and k-covers are further discussed and are established by mk-systems. As applications, some new characterizations of quotients or closed images of locally compact metric spaces are given by means of mk-systems.     

Dense trees: a new look at degenerate graphs

Dense trees are undirected graphs defined as natural extensions of trees. They are already known in the realm of graph coloring under the name of k-degenerate graphs. For a given integer k1, a k-dense cycle is a connected graph, where the degree of each vertex is greater than k. A k-dense forest F=(V,E) is a graph without k-dense cycles as subgraphs. If F is connected, then is a k-dense tree. 1-dense trees are standard trees. We have |E|k|V|−k(k+1)/2. If equality holds F is connected and is called a maximal k-dense tree. k-trees (a subfamily of triangulated graphs) are special cases of maximal k-dense trees.We review the basic theory of dense trees in the family of graphs and show their relation with k-trees. Vertex and edge connectivity is thoroughly investigated, and the role of maximal k-dense trees as “reinforced” spanning trees of arbitrary graphs is presented. Then it is shown how a k-dense forest or tree can be decomposed into a set of standard spanning trees connected through a common “root” of k vertices. All sections include efficient construction algorithms. Applications of k-dense trees in the fields of distributed systems and data structures are finally indicated.     

A parametric <Emphasis Type="Italic">k</Emphasis>-means algorithm

The k points that optimally represent a distribution (usually in terms of a squared error loss) are called the k principal points. This paper presents a computationally intensive method that automatically determines the principal points of a parametric distribution. Cluster means from the k-means algorithm are nonparametric estimators of principal points. A parametric k-means approach is introduced for estimating principal points by running the k-means algorithm on a very large simulated data set from a distribution whose parameters are estimated using maximum likelihood. Theoretical and simulation results are presented comparing the parametric k-means algorithm to the usual k-means algorithm and an example on determining sizes of gas masks is used to illustrate the parametric k-means algorithm.     

Graphs G for which both G and G¯ are Contraction Critically k-Connected

 An edge of a k-connected graph is said to be k-contractible if the contraction of the edge results in a k-connected graph. A k-connected graph with no k-contractible edge is called contraction critically k-connected. For k≥4, we prove that if both G and its complement Gˉ are contraction critically k-connected, then |V(G)|<k ^5/3+4k ^3/2. Received: October, 2001 Final version received: September 18, 2002 AMS Classification: 05C40     

On hamiltonian cycles in the prism over the odd graphs

The Kneser graph K(n, k) has as its vertex set all k‐subsets of an n‐set and two k‐subsets are adjacent if they are disjoint. The odd graph O_k is a special case of Kneser graph when n = 2k + 1. A long standing conjecture claims that O_k is hamiltonian for all k>2. We show that the prism over O_k is hamiltonian for all k even. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:177‐188, 2011