This paper describes an incremental parser based on an adjoining operation. By using the operation, we can avoid the problem of infinite local ambiguity. This paper further proposes a restricted version of the adjoining operation, which preserves lexical dependencies of partial parse trees. Our experimental results showed that the restriction enhances the accuracy of the incremental parsing.

In this paper, a recognition algorithm for the class of tree languages generated by linear, monadic context-free tree grammars (LM-CFTGs) is proposed. LM-CFTGs define an important class of tree languages because LM-CFTGs are weakly equivalent to tree adjoining grammars (TAGs). The algorithm uses the CKY algorithm as a subprogram and recognizes whether an input tree can be derived from a given LM-CFTG in O(n4) time, where n is the number of nodes of the input tree.

This paper presents the analogical conception of Chomsky normal form and Greibach normal form for linear, monadic context-free tree grammars (LM-CFTGs). LM-CFTGs generate the same class of languages as four well-known mildly context-sensitive grammars. It will be shown that any LM-CFTG can be transformed into equivalent ones in both normal forms. As Chomsky normal form and Greibach normal form for context-free grammars (CFGs) play a very important role in the study of formal properties of CFGs, it is expected that the Chomsky-like normal form and the Greibach-like normal form for LM-CFTGs will provide deeper analyses of the class of languages generated by mildly context-sensitive grammars.

In this paper, we are concerned with a structural ambiguity problem of tree adjoining grammars (TAGs), which is an essential problem when we try to model consensus structures of given set of ribonucleic acid (RNA) secondary structures by TAGs. RNA secondary structures can be represented as strings with structural information, and TAGs have a descriptive capability of this kind of strings, what we call structure-annotated strings. Thus, we can model RNA secondary structures by TAGs. It is sufficient to use existing alignment methods for just computing the optimal alignment between RNA secondary structures. However, when we also want to model the resulting alignment by grammars, if we adopt these existing methods, then we may fail in modeling the alignment result by grammars. Therefore, it is important to introduce a new alignment method whose alignment results can be appropriately modeled by grammars. In this paper, we will propose an alignment method based on TAG's derivations each corresponding to a given RNA secondary structure. For an RNA secondary structure, there exist a number of derivations of TAGs which correspond to the structure. From the grammatical point of view, the property of TAGs drives us to the question how we should choose a derivation from these candidates in order to obtain an optimal alignment. This is the structural ambiguity problem of TAGs, which will be mainly discussed in this paper. For dealing with this problem appropriately, we will propose an edit distance between two structure-annotated strings, and then present an algorithm which computes an optimal alignment based on the edit distance.

There have been many arguments that the underlying structure of natural languages is beyond the descriptive capacity of context-free languages. A well-known example is tree adjoining grammars; less common are spine grammars, linear indexed grammars, head grammars, and combinatory categorial grammars. It is known that these models of grammars have the same generative power of string languages and fall into the class of mildly context-sensitive grammars. For an automaton, it is known that the class of languages accepted by transfer pushdown automata is exactly the class of linear indexed languages. In this paper, deterministic transfer pushdown automata is introduced. We will show that the language accepted by a deterministic transfer pushdown automaton is generated by an unambiguous spine grammar. Moreover, we will show that there exists an inherently ambiguous language.

Several grammars have been proposed for representing RNA secondary structure including pseudoknots such as simple linear tree adjoining grammar (sl-tag), extended sl-tag (esl-tag) and RNA pseudoknot grammar (rpg). The main purpose of this paper is to compare the generative power of these grammars by identifying them as subclasses of multiple context-free grammars (mcfg). Specifically, it is shown that the class of languages generated by esl-tag (ESL-TAL) properly includes the class of languages generated by sl-tag (SL-TAL) and the class of languages generated by cfg. Also, we show that the class of languages generated by rpg coincides with the class of languages generated by mcfg with dimension one or two and rank one or two. Furthermore, it is shown that SL-TAL is a full trio and ESL-TAL is a substitution closed full AFL.