1,721,139 research outputs found
Trading Independent for Synchronized Parallelism in Finite Copying Parallel Rewriting Systems
No full textThe so-called family of finite copying parallel rewriting systems is considered in this work, including well-known generative devices and transducers as for instance the deterministic tree-walking transducers, the string generating context-free hypergraph grammars, and the multiple context-free grammars. Two parameters have been defined in the literature for all of the above systems, called the degree of synchronized parallelism and the degree of independent parallelism. When constant bounds are imposed on these parameters, the subclasses of languages generated by the above systems form a two-dimensional hierarchy. In this paper we investigate the interactions between these two parameters and establish new inclusion and separation results for subclasses of the hierarchy. More precisely, for a full half of the hierarchy we provide necessary and sufficient conditions to determine when a language subclass defined by an integer bound ofron the degree of independent parallelism is included in, includes, or is incomparable with a subclass defined by a bound ofr−1 on the same parameter. This means that, in the given range, we can exactly determine which increase in the degree of synchronized parallelism must be taken in order to compensate for a reduction of one unit in the degree of independent parallelism. This solves a question left open in the literature
Tree Adjoining Grammar Parsing and Boolean Matrix Multiplication
No full textThe computational problem of parsing a sentence in a tree-adjoining language is investigated. An interesting relation is studied between this problem and the well-known computational problem of Boolean matrix multiplication: it is shown that any algorithm for the solution of the former problem can easily be converted into an algorithm for the solution of the latter problem. This result bears on at least two important computational issues. First, we realize that a straightforward method that improves the known upper bound for tree-adjoining grammar parsing is hard to find. Second, we understand which features of the tree-adjoining grammar parsing problem are responsible for the claimed difficulty
Discovering subword associations in strings in time linear in the output size.
No full textGiven a text string x of n symbols and an integer constant d, we consider the problem of finding, for any pair (y,z) of subwords of x, the tandem index associated with the pair, which is defined as the number of times that y and z occur in tandem (i.e., with no intermediate occurrence of either one of them) within a distance of d symbols of x. Although in principle there might be O(n^4) distinct subword pairs in x, it is seen that it suffices to consider a family of only O(n^2) such pairs, with the property that for any neglected pair (y',z') there exists a corresponding pair (y,z) contained in our family such that: (i) y' is a prefix of y and z' is a prefix of z; and (ii) the tandem index of (y',z') equals that of (y,z). The main contribution of the paper consists of an algorithm showing that the computation of all non-zero tandem indices for a string can be carried out optimally in time and space linear in the size of the output
- …
