Deforestation is a well-known program transformation technique which eliminates intermediate data structures that are passed between functions. One of its weaknesses is the inability to deforest programs using accumulating parameters. We show how certain kinds of intermediate lists produced by accumulating parameters can be deforested. In this paper we introduce an accumulative variant of foldr, called rdlof, and show the composition of functions defined by foldr and rdlof. As a simplified instance of foldr and rdlof, we then examine dmap, an accumulative extension of map, and give the corresponding fusion rules. While the associated composition rules cannot capture all deforestation problems, they can handle accumulator fusion of fold- and map-style functions in a simple manner. The rules for accumulator fusion presented here can also be viewed as a restricted composition scheme for attribute grammars, which in turn may help us to bridge the gap between the attribute and functional worlds.

A uniquely parsable unification grammar (UPUG) is a formal grammar with the following features: (1) parsing is performed without backtracking, and (2) each nonterminal symbol can have arguments, and derivation and parsing processes accompany unification of terms as in Prolog (or logic programming). We newly introduce a uniquely parallel parsable unification grammar (UPPUG) by extending the framework of a UPUG so that parallel parsing is also possible. We show that, in UPPUG, parsing can be done without backtracking in both cases of parallel and sequential reductions. We give examples of UPPUGs where a given input string can be parsed in sublinear number of steps of the length of the input by parallel reduction.

A uniquely parsable grammar (UPG) introduced by Morita et al. is a kind of generative grammar, in which parsing can be performed without backtracking. It is known that UPGs and their three subclasses form the "deterministic Chomsky hierarchy. " In this paper, we introduce three kinds of normal forms for UPGs, i.e., Type-0, Type-1 and Type-2 UPGs by restricting the forms of rules to very simple ones. We show that the upper three classes in the deterministic Chomsky hierarchy can be exactly characterized by the three types of UPGs.

This paper proposes the binary second-order recurrent neural networks (BSRNN) equivalent to the modified finite automata (MFA) and presents the learning algorithm to construct the stable BSRNN for inferring regular grammar. This network combines two trends; one is to transform strings of a regular grammar into a recurrent neural network through training with no restriction of the number of neurons, the number of strings, and the length of string and the other is to directly transform itself into a finite automaton. Since neurons in the BSRNN employ a hard-limiter activation functions, the proposed BSRNN can become a good alternative of hardware implementation for regular grammars and finite automata as well as grammatical inference.

In literature, many methods have been presented for enumerating binary trees (full binary trees) and regular k-ary trees, while no one for enumerating arbitrary trees or arbitrary k-ary trees. It is proposed in 1997 using a context-free grammar GBT (GFBT) to code binary trees (full binary trees) for enumerating them. In this paper, we use another grammar GT (GTk) to code arbitrary trees (arbitrary k-ary trees) for enumerating them. The properties of words of Ln(GT) (Ln(GTk)) are discussed in depth, including necessary and sufficient conditions for a word, prefix and suffix of Ln(GT) (Ln(GTk)), and efficient algorithms are given and analyzed for the enumeration of words of Ln(GT) (Ln(GTk)).

This paper proposes the UGLR parser as an extension of the GLR parser. A UGLR parser is powerful enough to parse deterministically any phrase structure language if it is in the class of recursive languages and can parse any context free language as fast as the conventional GLR parser. Natural language processing often requires a parser for languages belonging to classes larger than that of context free languages, and the proposed parser is useful for this purpose.

In this paper, we propose an efficient method of constructing states in bottom-up tree pattern matching with dynamic programming technique for optimal code generation. This method can be derived from precomputing the analysis which is needed for constructing states. The proposed scheme is more efficient than other scheme because we can avoid unfruitful tests in constructing states at compile time. Furthermore, the relevant analyses needed for this proposal are largely achieved at compile-compile time, which secures actual efficiency at compile time.

Parallel multiple context-free grammar (PMCFG) and multiple context-free grammar (MCFG) were introduced to denote the syntax of natural languages. By the known fastest algorithm, the recognition problem for multiple context-free language (MCFL) and parallel multiple context-free language (PMCFL) can be solved in O(ne) time and O(ne+1) time, respectively, where e is a constant which depends only on a given MCFG or PMCFG. In this paper, we propose the following two algorithms. (1) An algorithm which reduces the recognition problem for MCFL to the boolean matrices multiplication problem. (2) An algorithm which reduces the recognition problem for PMCFL to the recognition problem for MCFL. The time complexity of these algorithms is O(ne-3i+1 M(ni)) where e and i are constants which depend only on a given MCFG or PMCFG, and M(k) is the time needed for multiplying two k k boolean matrices. The proposed algorithms are faster than the known fastest algorithms unless e=e, i=1 for MCFG, and e=e, i=0 for PMCFG.

This paper studies the ambiguity reduction ability of a probabilistic context-free grammar. We theoretically analyze a common behavior of any probabilistic context-free grammar. Moreover, we confirm by experiments that a probabilistic context-free grammar learnt from Japanese corpus has the ambiguity reduction ability as expected by the theoretical analysis.

In this paper, we propose an extension of finite state tree automaton, called tree automaton with tree memory (TTA), and also define structure composing TTA (SC-TTA) and backward deterministic TTA (BD-TTA) as subclasses of TTA. We show that the classes of yield languages accepted by TTAs, SC-TTAs and BD-TTAs are equal to the class of recursively enumerable languages, the class of languages generated by tree-to-string finite state translation systems (TSFSTSs) and the class of languages generated by deterministic TSFSTSs, respectively. As a corollary, it is shown that the yield language accepted by an SC-TTA (resp. a BD-TTA) is linear space (resp. polynomial time) recognizable.

In this paper, we introduce a parallel algorithm for parsing context-free languages. Our algorithm can handle arbitrary context-free grammars since it is based on Earley's algorithm. Our algorithm can operate on any loosely coupled multiprocessor which can provide a topology of a one-way ring. Our algorithm uses p processors to parse an input string of length n where 1 p n. It is shown that our algorithm requires O(n3/p) time. The algorithm uses a simple job allocation strategy. However, it achieves high load balancing and uses the processors efficiently.

String grammars (languages) have been extensively studied from 60's. On the other hand, the transformational grammar, proposed by N. Chomsky, contains the transformation from the set of derivation trees of context-free language to the surface set. And the grammar regarded a tree as an input sentence to some transducer. After that from latter half of 60's, the studies of acceptors, transducers, and so on, whose input is a tree, have been studied extensively. And recently some pushdown tree automata were introduced, and their fundamental properties and some other various properties were investigated [11]-[17]. Furthermore, a top-down pushdown tree transducer (t-PDTT for short), which is an extension of a top-down pushdown automaton (t-PDTA for short), was introduced and its fundamental properties were investigated [19]. In this paper, we define the various subclasses of context-free tree grammar (CFTG for short) by the combination of variables contained in the rules. Furthermore, we consider a monadic case of CFTG which is a special case of CFTG. Based on these definitions, we classify the subclasses of CFTG, and we investigate some inclusion properties of subclasses of CFTL (where CFTL indicates the class of context-free tree languages).

We propose a parallel parsing algorithm based on Earley's method, which works in O(log2n) time using O(n4.752) processors on CREW PRAM. This algorithm runs with less number of precessors compared with previously proposed W. Rytter's algorithm.

For the purpose of automatic speech recognition, language models (LMs) are used to predict possible succeeding words for a given partial word sequence and thereby to reduce the search space. In this paper several kinds of stochastic language models (SLMs) are evaluated-bigram, trigram, hidden Markov model (HMM), bigram-HMM, stochastic context-free grammar (SCFG) and hand-written Bunsetsu Grammar. To compare the predictive power of these SLMs, the evaluation was conducted from two points of views: (1) relationship between the number of model parameters and entropy, (2) predictive rate of succeeding part of speech (POS) and succeeding word. We propose a new type of bigram-HMM and compare it with the other models. Two kinds of approximations are tried and examined through experiments. Results based on both of English Brown-Corpus and Japanese ATR dialog database showed that the extended bigram-HMM had better performance than the others and was more suitable to be a language model.

We present two efficient attribute evaluator construction methods for a wide subclass of L-attributed grammars by enumeration of attributed items during one-pass bottom-up parsing. We have already proposed a construction method of a parser/evaluator for the subclass of L-attributed grammar. However the evaluator produced by our previous method uses a great number of attributed items to evaluate all attributes of a given input string. In this paper we propose two generalized methods to reduce the number of attributed itmes used in attribute evaluation. Our methods allow us to evaluate all attributes taking advantage of the use of available lookahead information.

We introduce a generalized cln grammar (gclng), a generalization of a completely linearly nested context-free grammar (clncfg), of which variables are partitioned linearly and each rule satisfies similar conditions as those of clncfg related to its partition. We show that the class of languages generated by gclng's coincides with the class of quasi-rational languages, and consider the inclusion relations between languages generated by gclng's and those generated by clncfg's.

Lexical-functional grammars (lfg's) were introduced to define the syntax of natural languages. In lfg's, a finite set of attribute-value pairs called an f-structure is associated with each internal node in a derivation tree. For efficient parsing, some subclasses of lfg's were proposed. However, these subclasses have been shown to generate at least one -complete language. In this paper, we introduce a subclass of lfg's called pd-lfg's. In pd-lfg's, an f-structure forms a pushdown stack. For a node v in a derivation tree and at most one specified child vi of v, the f-structure of vi is obtained by performing a specified pushdown stack operation on the f-structure of v. We prove the equivalence of the generative capacity of modified head grammars (mhg's) and that of pd-lfg's. Since the languages generated by mhg's are known to be recognizable in O(n6) time, the languages generated by pd-lfg's can be recognized in O(n6) time.

Tomita's parsing method (GLR) is a practical and successful parsing method for natural language. However, one difficulty in the GLR is that interleaved constraint processing of syntax and semantics in parallel is not trivial during parsing, because it uses the precompiled table for a fast real-time parsing. In this paper, we present a method which makes the GLR adaptable to interleaved parsing while making some limitation on its generality. For interleaved parsing, the conflicts of the LR parsing table must be resolved at the parse time. The shift-reduce conflict among the above conflicts is the most serious one for interleaved parsing because of the lack of knowledge for the conflict resolution at the parse time. Therefore, we concentrate on resolving a shift-reduce conflict by introducing a grammar which is called a shift-first LR (k) grammar. Our method for this is that the conflict resolution is delayed by the shift-first strategy which makes an unconditional choice of shift actions in the case of a shift-reduce conflict. Then, a delayed resolution that resolves the conflict, is made. Depending on the decision of the resolution, the pseudo parsing, which parses symbols in the LR parser stack, proceeds. Our experiments showed that our parser is efficient while attaining the interleaved parsing at real time.

As a generalization of the tree automaton, tree automata with various types of memory are introduced and their relation to context-free grammars with memory is studied. Relations between computation trees of tree automata with memory and derivation trees of context-free grammars with memory are established, and as a consequence, the languages generated by context-free grammars with memory are characterized in terms of the sets of trees recognizable by tree automata with memory. Also various types of traversal of labeled trees recognizable by tree automata with memory are considered.

Finite state translation systems (fsts') are a widely studied computational model in the area of tree automata theory. In this paper, the string generating capacities of fsts' and their subclasses are studied. First, it is shown that the class of string languages generated by deterministic fsts' equals to that of parallel multiple context-free grammars, which are an extension of context-free grammars. As a corollary, it can be concluded that the recognition problem for a deterministic fsts is solvable in O(ne1)-time, where n is the length of an input word and e is a constant called the degree of the deterministic fsts'. In contrast to the latter fact, it is also shown that nondeterministic monadic fsts' with state-bound 2 can generate an NP-complete language.