Extended linear macro grammars,iteration grammars,and register programs

Summary Extended macro grammars (of the linear basic type only) are introduced as a generalization of those in [5], and it is shown that they have the same language generating power as (parallel) iteration grammars. In particular the IO and OI versions of extended macro grammars correspond to the deterministic and the (usual) nondeterministic iteration grammars respectively. Hence iterated substitution can be formulated using extended macro grammars.A nondeterministic register program without tests may be viewed as a macro grammar. IO-extension of this macro grammar corresponds to the use of nonrecursive function procedures in the register program. OI-extended macro grammars correspond to register programs which compute on sets. Hence these features of register programs can be investigated by means of (extended) parallel rewriting systems.The work of the first author has been supported by the Netherlands Organization for the Advancement of Pure Research (Z.W.O.).     

Tree controlled grammars

Languages are studied which can be generated by context-free grammars under a single simple restriction which must be satisfied by its derivation trees. Using tree controlled grammars (TC grammars for short) all unambigous and some inherently ambigous context-free languages, and also some non context-free languages can be parsed in timeO(n ²). The classes of regular, linear, context-free, EOL, ETOL and type 0 languages can be characterized in a natural manner using TC grammars. A context-free generator for all type 0 languages is exhibited. Some normal forms for TC grammars are established but it is shown that many common normal forms (e. g. Greibach normal form) cannot be obtained for TC grammars in general.     

Time-bounded controlled bidirectional grammars

We study regularly controlled bidirectional (RCB) grammars from the viewpoint of time-bounded grammars. RCB-grammars are context-free grammars of which the rules can be used in a productive and in a reductive fashion, while the application of these rules is controlled by a regular language. Several modes of derivation can be distinguished for this kind of grammar. A time bound on such a grammar is a measure of its derivational complexity. For some families of time bounds and for some modes of derivation we establish closure properties and a normal form theorem. In addition parsing algorithms are given for some modes of derivation. We conclude with considering generalizations with respect to the family of control languages and the family of bounding functions..     

Direction controlled programmed grammars

Summary A generalization of the notion of a context-free grammar is presented here. It is based on the notion of a programmed grammar. When the underlying context-free rules do not contain erasing, the class of languages obtained is identical with the class of context-sensitive languages. With underlying context-free rules containing erasing one obtains the class of recursively enumerable languages.The author is indebted to Drs. T. A. Zoethout for very useful discussions concerning this paper.     

Tradeoff lower lounds for stack machines

A space-bounded Stack Machine is a regular Turing Machine with a read-only input tape, several space-bounded read-write work tapes, and an unbounded stack. Stack Machines with a logarithmic space bound have been connected to other classical models of computation, such as polynomial-time Turing Machines (P) (Cook in J Assoc Comput Mach 18:4–18, 1971) and polynomial size, polylogarithmic depth, bounded fan-in circuits (NC) e.g., Borodin et al. (SIAM J Comput 18, 1989). In this paper, we present significant new lower bounds and techniques for Stack Machines. This comes in the form of a trade-off lower bound between space and number of passes over the input tape. Specifically, we give an explicit permuted inner product function such that any Stack Machine computing this function requires either ${\Omega (N^{1/4 - \epsilon})}$ space or ${\Omega (N^{1/4 - \epsilon})}$ number of passes for every constant ${\epsilon > 0}$ , where N is the input size. In the case of logarithmic space Stack Machines, this yields an unconditional ${\Omega (N^{1/4 - \epsilon})}$ lower bound for the number of passes. To put this result in perspective, we note that Stack Machines with logarithmic space and a single pass over the input can compute Parity, Majority, as well as certain languages outside NC. The latter follows from Allender (J Assoc Comput Mach 36:912–928, 1989), conditional on the widely believed complexity assumption that PSPACE ${\subsetneq}$ EXP. Our technique is a novel communication complexity reduction, thereby extending the already wide range of models of computation for which communication complexity can be used to obtain lower bounds. Informally, we show that a k-player number-in-hand (NIH) communication protocol for a base function f can efficiently simulate a space- and pass-bounded Stack Machine for a related function F, which consists of several “permuted” instances of f, bundled together by a combining function h. Trade-off lower bounds for Stack Machines then follow from known communication complexity lower bounds. The framework for this reduction was given by Beame & Huynh-Ngoc (2008), who used it to obtain similar trade-off lower bounds for Turing Machines with a constant number of pass-bounded external tapes. We also prove that the latter cannot efficiently simulate Stack Machines, conditional on the complexity assumption that E ${\not \subset}$ PSPACE. It is the treatment of an unbounded stack which constitutes the main technical novelty in our communication complexity reduction.     

Nonterminal complexity of tree controlled grammars

This paper studies the nonterminal complexity of tree controlled grammars. It is proved that the number of nonterminals in tree controlled grammars without erasing rules leads to an infinite hierarchy of families of tree controlled languages, while every recursively enumerable language can be generated by a tree controlled grammar with erasing rules and at most nine nonterminals.     

Size,index, and context-sensitivity of controlled partition grammars

Controlled partition grammars (CPGs) were designed to apply to certain needs of linguists. General CPGs generate exactly all context-sensitive languages. CPGs have two parameters:size andindex. The partition index of CPGs can be bounded by two, while CPGs with partition index one generate exactly the class of context-free languages. The size (of the partition blocks) of CPGs can be bounded by two, while CPGs of size one generate a class of languages properly contained in the class of contextsensitive languages. If one can eliminate recursive productions of the formAB in a CPG then deterministic and nondeterministic lba's are equivalent.This author was supported in part by NSF Grant No. MCS 76-10076.This author was supported in part by NSF Grant No. MCS 75-22557.     

Matrix and finite element stack machines for structural engineering computations with units

Despite the well known benefits of physical units, matrices, and matrix algebra in engineering computations, most engineering analysis packages are essentially dimensionless. This paper describes the design and implementation of matrix and finite element stack machines for Aladdin, a new computational environment that embeds units inside matrix and finite element calculations. Functionality of the Aladdin stack machine is illustrated by working step by step through the setup and execution of three examples: (1) Parsing and stack machine execution for x = 2 in; (2) Deflection analysis of a cantilever beam, and (3) Rollup maneuver for a long cantilever beam.     

Apex graph grammars and attribute grammars

Summary Apex graph grammars are a particular type of directed node-label controlled (DNLC) graph grammars: the embedding edges are established between terminal nodes only. Apex graph grammars, slightly generalized, can generate the sets of dependency graphs of attribute grammars. The other way around, every apex graph language can be obtained from such a dependency graph language by a graph replacement (which is an operation analogous to a string homomorphism).     

Optimal probabilistic evaluation functions for search controlled bystochastic context-free grammars

The possibility of using stochastic context-free grammars (SCFG's) in language modeling (LM) has been considered previously. When these grammars are used, search can be directed by evaluation functions based on the probabilities that a SCFG generates a sentence, given only some words in it. Expressions for computing the evaluation function have been proposed by Jelinek and Lafferty (1991) for the recognition of word sequences in the case in which only the prefix of a sequence is known. Corazza et al. (1991) have proposed methods for probability computation in the more general case in which partial word sequences interleaved by gaps are known. This computation is too complex in practice unless the lengths of the gaps are known. This paper proposes a method for computing the probability of the best parse tree that can generate a sentence only part of which (consisting of islands and gaps) is known. This probability is the minimum possible, and thus the most informative, upper-bound that can be used in the evaluation function. The computation of the proposed upper-bound has cubic time complexity even if the lengths of the gaps are unknown. This makes possible the practical use of SCFG for driving interpretations of sentences in natural language processing     

Extended least squares support vector machines for ordinal regression

We extend LS-SVM to ordinal regression, which has wide applications in many domains such as social science and information retrieval where human-generated data play an important role. Most current methods based on SVM for ordinal regression suffer from the problem of ignoring the distribution information reflected by the samples clustered around the centers of each class. This problem would degrade the performance of SVM-based methods since the classifiers only depend on the scattered samples on the border which induce large margin. Our method takes the samples clustered around class centers into account and has a competitive computational complexity. Moreover, our method would easily produce the optimal cut-points according to the prior class probabilities and hence may obtain more reasonable results when the prior class probabilities are not the same. Experiments on simulated datasets and benchmark datasets, especially on the real ordinal datasets, demonstrate the effectiveness of our method.     

One-sided forbidding grammars and selective substitution grammars

In one-sided forbidding grammars, the set of rules is divided into the set of left forbidding rules and the set of right forbidding rules. A left forbidding rule can rewrite a non-terminal if each of its forbidding symbols is absent to the left of the rewritten symbol in the current sentential form, while a right forbidding rule is applied analogically except that this absence is verified to the right. Apart from this, they work like ordinary forbidding grammars. As its main result, this paper proves that one-sided forbidding grammars are equivalent to selective substitution grammars. This equivalence is established in terms of grammars with and without erasing rules. Furthermore, this paper proves that one-sided forbidding grammars in which the set of left forbidding rules coincides with the set of right forbidding rules characterize the family of context-free languages. In the conclusion, the significance of the achieved results is discussed.     

From controlled dynamical systems to context-dependent grammars: A connectionist approach

Formal language techniques may be used to study controlled dynamical systems and lead to a formulation in terms of context-dependent grammars. Using automata as basic units we obtain an on-line implementation of the grammars. The implementation has a hierarchical structure, the lowest level dealing with the identification of alphabet symbols (terminal and non-terminal), and the other with the establishment of the grammar productions. The method provides an automatic construction of the automata network from the experimental data. In particular, the parallel-processing capabilities of automata networks improves the performance of grammar-based models for control and anomaly detection in electromechanical devices of industrial relevance. One such example is presented.     

A characterization of context-free string languages by directed node-label controlled graph grammars

Summary Directed node-label controlled graph grammars (DNLC grammars) are sequential graph rewriting systems. In a direct derivation step of a DNLC grammar a single node is rewritten. Both the rewriting of a node and the embedding of a daughter graph in a host graph are controlled by the labels of nodes only. We study the use of those grammars to define string languages. In particular we provide a characterization of the class of context-free string languages in terms of DNLC grammars.     

A comparison of boundary graph grammars and context-free hypergraph grammars

Context-free hypergraph grammars and boundary graph grammars of bounded nonterminal degree have the same power, both for generating sets of graphs and for generating sets of hypergraphs. Arbitrary boundary graph grammars have more graph generating power than context-free hypergraph grammars, but they have the same hypergraph generating power. To obtain these results, several normal forms for boundary graph grammars are given. It is also shown that the class of boundary graph languages is closed under the operation of edge contraction, where the label of the edge indicates whether or not the edge should be contracted.