The RORIC-LING Bulletin

months 1 - 6

General Questions

From the way you are asking your question it is not clear to us whether you refer to a specific paper, program etc. that our Regional Information Center has displayed on the web or to the objectives of the entire project. That is why we are taking the liberty to answer you from a very broad perspective. If you will feel the need for certain details or for further clarifications, please don't hesitate to contact us once again.

The main objective of the BALRIC-LING project is to raise the awareness concerning the potential of the most advanced Human Language Technologies (HLT) and the possible scientific and industrial applications of the corresponding linguistic resources. Raising this awareness is necessary especially in the Balkans, where the fields of Natural Language Processing and Computational Linguistics are less known. Since HLT is a rather broad field, BALRIC-LING will focus on four topics only: word-centered linguistic resources, corpora and tagging, relevant supporting tools and possible advanced HLT usages of the first two.

In order to raise the awareness concerning these topics especially in Bulgaria and Romania, within the BALRIC-LING project two Regional Information Centers have been created in these countries. The Romanian Regional Information Center is called RORIC-LING and it will concentrate on the topics mentioned in the center's web page, that corresponding to the web address you have subscribed from.

An issue of great interest now-days is that of creating linguistic resources in general, corpora in particular, since, without these, advanced HLT applications can not exist. Within the first discussed topic, RORIC offers an annotation tool for corpus creation, which can be used within the formal framework of Dependency Grammars. Its value resides mainly in the fact that it is language independent. Many examples (annotated texts) of using this tool in the case of the Romanian language are offered, since this is of special interest to users in our country.

The other project partners will refer to different topics, all within the general themes previously mentioned. In order to find out more details about the BALRIC-LING project and to visit the web pages of the other project partners, you can visit the project home page at
                                               http://www.lml.bas.bg
from where you must choose BALRIC-LING. Thank you for subscribing and for your interest in our project.

In our view it is only necessary to understand the concepts and the theory that we have already presented on the web. If you will ever need or wish to apply these linguistic theories in connection with a given language, in the framework of various NLP applications (for instance parsing), like we have already done for Romanian, you will need to ask for linguistic guidance. Linguists will provide the necessary information concerning the application of the general theory with respect to a specific language. In order to find out more concerning the various possible computer science type applications of these theories, we recommend that you look over the virtual bulletin that will be published by us on the web, at the end of February.

Thank you for subscribing and for your interest in our project. The project will not involve a text processing procedure, at least not at this early stage. BALRIC-LING is mainly an awareness project having as main objective to raise the awareness concerning HLT mainly in the Balkan area. The first part of the project focuses on word-centered linguistic resources, corpora and tagging, relevant supporting tools. In case the project will be prolongued future topics might include a text processing procedure, which most likely will not involve a classical Chomskian approach.

The connection between this part of the project and the last one will become obvious when we will focus on establishing a theoretical specification for a morphological model for Romanian. The second topic proposed by RORIC and referring to WordNet represents a completely different topic. Actually, the main goal of the virtual seminar organized by RORIC is that of taking into account essential topics which are not linked to one another but which all refer to some main aspects of language technology: word-centered linguistic resources and annotation; corpora and tagging; relevant supporting tools.

The BALRIC-LING project has started on Sept.1, 2001 and will go on for 18 months (unless it will be prolonged). It is funded by the European Commission.

The main objective of the BALRIC-LING project is to raise the awareness concerning the potential of the most advanced Human Language Technologies and the possible scientific and industrial applications of the corresponding linguistic resources. Raising this awareness is necessary especially in the Balkans, where the fields of Natural Language Processing and Computational Linguistics are less known. Since HLT is a rather broad field, BALRIC-LING will focus on four topics only: word-centered linguistic resources and annotations, corpora and tagging, relevant supporting tools and possible advanced HLT usages of the first two.

In order to raise the awareness concerning these topics especially in Bulgaria and Romania, within the BALRIC-LING project two Regional Information Centers have been created in these countries. The Romanian Regional Information Center is called RORIC-LING and it will concentrate on the topics mentioned in the center's web page, that corresponding to the web address you have subscribed from.

As of today you will find more details concerning the BALRIC-LING project in the RORIC-LING home page, as well.

The other project partners will refer to different topics, all within the general themes previously mentioned. Not all partners have loaded their web pages yet, but will do so soon. In order to find out more details about the BALRIC-LING project and to visit the web pages of the other project partners, you can visit the project home page at
                                             http://www.lml.bas.bg
from where you must choose BALRIC-LING.

The project does not refer only to the Balkan area, it addresses people dealing with HLT from everywhere. Also, it is not only for IT companies and IT people. The project tries to raise the general awareness concerning this field and we will be happy to answer questions coming from all those who are - or become - interested. Thank you for subscribing and for your interest in our project.

Questions Referring to Dependency Grammars and DGA

The XML format used by DGA is a very simple one, inspired by the XCES standard. The needs of the user can, however, vary a lot. Therefore, if the user requires a different format, he must write a XSLT by means of which the corpus is transformed from the XML format used by DGA into the required format. For instance, I use a XSLT that turns the texts annotated with DGA into the HTML format which allows viewing these texts on the web.

The main advantages of using DGA derive from the fact that it represents a tool which is language independent. Also, it was designed to be independent from the various formalisms related to Dependency Grammars. Other important advantages of DGA derive from its characteristics mentioned in the user manual: usage easiness, portability, conformity with up-to-date standards, flexibility.

As it is well known, there are two diametrically opposed methods of describing the syntactic structure of natural sentences: dependency (D-)trees and phrase-structure (PS-)trees. Obviously, combinations of the two methods are possible, with lines of compromise being drawn at different points; but there is no essentially distinct third possibility.

There are five major respects in which D-language is different from PS-language:

A first significant difference refers to constituency vs. relations. A PS-tree of a natural-language expression shows which items of the latter - wordforms or phrases - "go together" (i.e., combine) with which other items to form tight units of a higher order. A PS-tree reveals the structure of an expression in terms of groupings of its actual elements: maximal blocks, which consist of smaller blocks, which consist of still smaller blocks, etc. The PS- approach concentrates on constituency, the main logical operation in this approach being set inclusion (to "belong to a phrase" or "belong to a category"). Under the PS-approach, an actual sentence is, so to speak, cut into (generally two) major constituents, each of which is subsequently cut in its turn, etc. This approach thus favors the analytical viewpoint. A D-tree, on the other hand, shows which items are related to which other items and in what way. The D-approach concentrates on the relationships between ultimate syntactic units, i.e., wordforms. The main logical operation here is the establishing of binary relations. Under the D-approach, an actual sentence is, so to speak, built out of words, linked by dependencies. This approach thus favors the synthetic viewpoint.

Another difference between PS-language and D-language refers to the fact that, in a PS-tree, the syntactic class membership (i.e., categorization) of an item is specified as an integral part of the syntactic representation. Symbols like NP, VP, N, PP, etc. appear in PS-trees as labels on nodes. In other words, distributional properties of syntactic units (i.e., the traditional parts of speech and syntactic features, rechristened 'categorization' and 'subcategorization') are used as the main tool to express their syntactic roles. In a D-tree, on the other hand, the symbols representing the syntactic class membership and other syntactic properties of an item are not admitted as immediate elements of syntactic structure. (Such information is included in the dictionary, lexicon etc.).

A third important difference refers to terminals and non-terminals. In a PS-tree, most nodes are non-terminals: they represent syntactic groupings or phrases and do not correspond to the actual wordforms of the sentence under analysis. A D-tree, on the contrary, contains terminal nodes only; no abstract representation of groupings is needed.

The linear order of nodes generates another difference. In a PS-tree, nodes must be ordered linearly. The order is not necessarily that of the actual wordforms of the sentence, but some linear order is unavoidable. The PS-language is essentially linear. In a D-tree, on the other hand, the nodes are in no linear order at all. The linear order of wordforms in the sentence is an expressive means used by actual languages to encode something different from this order itself, namely syntactic relations, and therefore, linear order should not be present in syntactic structures. The D-language is essentially two-dimensional.Finally, a PS-tree does not specify the type of syntactic link existing between two items (and cannot do so, at least not in a natural and explicit way). A D-tree, on the other hand, puts particular emphasis on specifying in detail the type of any syntactic relation obtained between two related items.

A possible utilization of such a corpus would be that of performing syntactic analysis (parsing). This has already been done at the University of Bucharest, for Romanian, within the DBR-MAT project, funded by the Volkswagen Foundation.

The solution which was successfully chosen in the case of the Romanian language within the framework of the DBR-MAT project, for performing "dependency parsing", is of stochastic nature. It consists of associating a probability to each syntactic structure, and of choosing that syntactic structure which has the maximum associated probability corresponding to each given sentence. Assigning such a probability means finding a stochastic model, namely the most adequate one. According to this approach, in order to find the syntactic dependency structure of a given sentence it is not necessary to explicitly specify a Dependency Grammar. The grammar will be implicitly included in the parameters of the stochastic model, which, in turn, will be estimated by means of the linguistic data (namely of a corpus).

Within this framework one can say that finding a parsing algorithm means finding an algorithm having as input a sentence and as output the syntactic structure (S,D) of that sentence, where S=(T,P) and D have the same significance as that explained in the paper which is on the web. The stages of such an algorithm are: finding set T ("part of speech tagging"); finding set P (namely finding the dependency relations); finding set D (namely establishing the types of the dependencies). We will get back to you on how these sets were found, if you are interested in the stochastic aspects of this approach.

Yes, mainly because this approach is closer to the traditional way of performing syntactic analysis. This fact probably determines the Romanian linguists to feel much closer to this approach, which they have already successfully applied relatively to the Romanian language, by performing "dependency parsing", within the DBR-MAT project, which was funded by the Volkswagen Foundation (1996-1998).

The creation of such a corpus has been initiated now, within the BALRIC-LING project framework. The annotated texts which already exist on the web are part of this corpus and their number will increase in the near future.

Link Grammar is of dependency type but much more lexicalized. A formal grammatical system called a "link grammar" requires that a sequence of words is in the language of a link grammar if there is a way to draw links between words in such a way that (1) the local requirements of each word are satisfied, (2)the links do not cross, and (3) the words form a connected graph. The formalism is lexical and makes no explicit use of constituents and categories.

Link Grammars resemble Dependency Grammars and Categorial Grammars. There are also significant differences, the most important aspect being the fact that Link Grammars are much more lexicalized.

Syntactic parsing has been performed, within the formal framework of Dependency Grammars, using "Constraint Dependency Grammar" - CDG (Maruyama, 1990). Decision procedures for dependency parsing using graded constraints exist. CDG strictly separates possible structural descriptions from the correctness conditions for linguistic structures. CDG is weakly context-sensitive. In order to learn about CDG based algorithms, we recommend reading

Menzel,Wolfgang and Schroder,Ingo, "Decision procedures for dependency parsing using graded constraints", in: Sylvain Kahane si Alain Polguere, editors, "Proc. Coling - ACL Workshop on Processing of Dependency-based Grammars", pag. 78-87, Montreal, Canada, 1998.

As far as our group is concerned, we have performed dependency parsing using a stochastic approach. It consists of associating a probability to each syntactic structure, and of choosing that syntactic structure which has the maximum associated probability corresponding to each given sentence. Assigning such a probability means finding a stochastic model, namely the most adequate one. According to this approach, in order to find the syntactic dependency structure of a given sentence it is not necessary to explicitly specify a Dependency Grammar. The grammar will be implicitly included in the parameters of the stochastic model, which, in turn, will be estimated by means of the linguistic data (namely of a corpus).

Within this framework one can say that finding a parsing algorithm means finding an algorithm having as input a sentence and as output the syntactic structure (S,D) of that sentence, where S=(T,P) and D have the same significance as that explained in the paper which is on the web.

The stages of such an algorithm are: finding set T ("part of speech tagging"); finding set P (namely finding the dependency relations); finding set D (namely establishing the types of the dependencies).

Set T was found using an algorithm proposed by Ratnaparkhi in 1996. This algorithm is of stochastic nature and uses maximum entropy. Set P was also found by means of a stochastic algorithm, namely the algorithm proposed by Eisner, also in 1996. We have modified this algorithm by changing the stochastic model and by again using maximum entropy. The algorithm for finding set P represents an implementation of the Dynamic Programming Method with the aim of finding the most probable parse in a bottom-up manner. After determining sets T and P, finding set D is no longer a problem.

Within the framework of this linguistic theory specifying a Dependency Grammar means finding a set of constraints which can lead to establishing that certain syntactic structures are correct, while others are not. For instance, according to such constraints, it can be decided that certain words of a sentence may be head-words, while others may not. In other words, specifying a Dependency Grammar for a specific language means finding a set of rules which indicate what dependency relations are accepted in that language. This has not been done yet, for Romanian, therefore a Dependency Grammar for this language does not exist. Only specific dependency relations have been established, dependency relations which can be used for performing various tasks, such as dependency parsing.

The classical types of dependencies are those of type subject, object and complement. However, these dependencies can be further refined. For instance, in establishing the most frequent types of dependencies for Romanian we have, in most cases, considered the syntactic function (as in classical syntactic analysis) of the dependent. A table with the most frequent dependency relation types occurring in Romanian can be found in the paper which is now on the web and will be updated by RORIC at the end of February.

An example of how such a corpus can be used is that of performing stochastic parsing. Our group has already performed "dependency parsing" of Romanian sentences in a stochastic manner. According to this approach, in order to find the syntactic dependency structure of a given sentence it is not necessary to explicitly specify a Dependency Grammar. The grammar will be implicitly included in the parameters of the stochastic model, which, in turn, will be estimated by means of the linguistic data (namely of a corpus).

Within this framework one can say that finding a parsing algorithm means finding an algorithm having as input a sentence and as output the syntactic structure (S,D) of that sentence, where S=(T,P) and D have the same significance as that explained in the paper which is on the web. The stages of such an algorithm are: finding set T ("part of speech tagging"); finding set P (namely finding the dependency relations); finding set D (namely establishing the types of the dependencies).

Set T was found using an algorithm proposed by Ratnaparkhi in 1996. This algorithm is of stochastic nature and uses maximum entropy. Set P was also found by means of a stochastic algorithm, namely the algorithm proposed by Eisner, also in 1996. We have modified this algorithm by changing the stochastic model and by again using maximum entropy. The algorithm for finding set P represents an implementation of the Dynamic Programming Method with the aim of finding the most probable parse in a bottom-up manner. After determining sets T and P, finding set D is no longer a problem.

We recommend stochastic parsing based on Dependency Grammars since our group has already successfully performed it in the case of the Romanian language. According to this approach, in order to find the syntactic dependency structure of a given sentence it is not necessary to explicitly specify a Dependency Grammar. The grammar will be implicitly included in the parameters of the stochastic model, which, in turn, will be estimated by means of the linguistic data (namely of a corpus).

Within this framework one can say that finding a parsing algorithm means finding an algorithm having as input a sentence and as output the syntactic structure (S,D) of that sentence, where S=(T,P) and D have the same significance as that explained in the paper which is on the web. The stages of such an algorithm are: finding set T ("part of speech tagging"); finding set P (namely finding the dependency relations); finding set D (namely establishing the types of the dependencies).

Set T was found using an algorithm proposed by Ratnaparkhi in 1996. This algorithm is of stochastic nature and uses maximum entropy. Set P was also found by means of a stochastic algorithm, namely the algorithm proposed by Eisner, also in 1996. We have modified this algorithm by changing the stochastic model and by again using maximum entropy. The algorithm for finding set P represents an implementation of the Dynamic Programming Method with the aim of finding the most probable parse in a bottom-up manner. After determining sets T and P, finding set D is no longer a problem.

The main stages in the evolution of these types of grammars are the following:

1. Panini (2600 years ago, India) recognized, distinguished and classified semantic, syntactic and morphological dependencies.

2. The Arabic grammarians (1200 years ago, Iraq) recognized government and syntactic dependency structures.

3. The Latin grammarians (800 years ago) recognized 'determination' and dependency structures.

4. School grammars of English in Europe and U.S.A. taught sentence-analysis in terms of dependency, and the 'sentence diagramming' which has been popular since the late 19-th century (using a system invented in U.S.A.) is DG.

5. Lucien Tesniere (1930s France) developed a relatively formal and sophisticated theory of DG grammar for use in schools. This bottom-up approach is still widely used in Europe, and by Russians and slavists in U.S.A.

6. In 1933 Leonard Bloomfield in the U.S.A. developed a top-down approach: Immediate Constituent Analysis, which turned into PSG ('phrase-structure grammar').

The popularity of dependencies as a formal way of representing the syntactic structure of sentences has been constantly growing and has culminated with the work of Lucien Tesniere from 1959. In spite of this, however, at the beginning of the 30s, in North America, the 'immediate constituency' syntax started replacing the 'dependency syntax'. The first later turned into 'PS analysis' which determines the phrase-structure of a sentence. Rigorously stated by Leonard Bloomfield (Bloomfield 1933), but also by Wells in 1974 and Percival in 1976, the PS-type representation in syntax has been promoted with great energy by the structuralist school in the 30s, 40s and 50s. It became the only syntactic representation seriously taken into consideration by Noam Chomsky and the generative school which he founded at the end of the 50s.

Another class of grammars which provide an appropriate description of natural languages is that of Contextual Grammars, which also do not fit into the Chomsky hierarchy. Contextual Grammars were introduced by Solomon Marcus in 1969 as "intrinsic grammars" without auxiliary symbols, based only on the fundamental linguistic operation of inserting words into given phrases according to certain contextual dependencies. Contextual Grammars include contexts, i.e. pairs of words, associated with selectors (sets of words). A context can be adjoined to any associated selector element. In this way, starting from a finite set of words (axioms), the language is generated. It has been shown that this formalism provides an appropriate description of natural languages. It is only in 1999 that K. Harbusch presents a parser based on Contextual Grammars. Recent very encouraging results have determined researchers to concentrate on defining a Contextual Grammar for English. For more information on Contextual Grammars see:

1. S.Marcus, C.Martin-Vide, G.Paun. Contextual Grammars as Generative Models of Natural Languages. Computational Linguistics, 24(2), p. 245-274.

2. F.Hristea. Introducere in procesarea limbajului natural cu aplicatii in Prolog. Editura Universitatii din Bucuresti, 2000, p. 102-113 (in Romanian).

NO. Contextual Grammars represent a different class of grammars which provide an appropriate description of natural languages and which also do not fit into the Chomsky hierarchy. Contextual Grammars were introduced by Solomon Marcus in 1969 as "intrinsic grammars" without auxiliary symbols, based only on the fundamental linguistic operation of inserting words into given phrases according to certain contextual dependencies. Contextual Grammars include contexts (pairs of words), associated with selectors (sets of words). A context can be adjoined to any associated selector element. In this way, starting from a finite set of words (axioms), the language is generated. It has been shown that this formalism provides an appropriate description of natural languages. It is only in 1999 that K. Harbusch presents a parser based on Contextual Grammars. Recent very encouraging results have determined researchers to concentrate on defining a Contextual Grammar for English. For more information on Contextual Grammars see:

1. S.Marcus, C.Martin-Vide, G.Paun. Contextual Grammars as Generative Models of Natural Languages. Computational Linguistics, 24(2), p. 245-274.

2. F.Hristea. Introducere in procesarea limbajului natural cu aplicatii in Prolog. Editura Universitatii din Bucuresti, 2000, p. 102-113 (in Romanian).

Our group has performed "dependency parsing" using a stochastic approach. According to this approach, in order to find the syntactic dependency structure of a given sentence it is not necessary to explicitly specify a Dependency Grammar. The grammar will be implicitly included in the parameters of the stochastic model, which, in turn, will be estimated by means of the linguistic data (namely of a corpus).

Within this framework one can say that finding a parsing algorithm means finding an algorithm having as input a sentence and as output the syntactic structure (S,D) of that sentence, where S=(T,P) and D have the same significance as that explained in the paper which is on the web.

The stages of such an algorithm are: finding set T ("part of speech tagging"); finding set P (namely finding the dependency relations); finding set D (namely establishing the types of the dependencies).

Set T was found using an algorithm proposed by Ratnaparkhi in 1996. This algorithm is of stochastic nature and uses maximum entropy. Set P was also found by means of a stochastic algorithm, namely the algorithm proposed by Eisner, also in 1996. We have modified this algorithm by changing the stochastic model and by again using maximum entropy. The algorithm for finding set P represents an implementation of the Dynamic Programming Method with the aim of finding the most probable parse in a bottom-up manner. After determining sets T and P, finding set D is no longer a problem.

The answer to this question depends on what we mean by Generative Grammars. This is an extremely broad class of grammars within which various formalisms for describing natural language phenomena exist. Dependency Grammars have also been formalized in various ways.

That is why we shall try to answer the above question by viewing the issue from three different points of view, namely:

1. From a formal point of view. This point of view refers to the generative capacity of a specific class of grammars. In order to be considered adequate, a class of grammars must be sufficiently restrictive so that it does not allow the generation (description) of any type of language, but it must also be sufficiently powerful in order to allow the description of natural language phenomena. From this point of view we consider that the two mentioned classes of grammars are equivalent.

After having accepted the fact that natural language phenomena are too complex for the descriptive capacity of context independent grammars, the class of "mildly context-sensitive languages" has recently been taken into consideration. This class of languages is usually accepted as being sufficiently adequate for describing natural language and is generated by a variety of grammatical formalisms (considered independently and for various reasons):

K. Vijay-Shanker, D.J. Weir, The Equivalence of Four Extensions of Context-Free Grammar. Math. Systems Theory, 27, 1994.

As far as Dependency Grammars are concerned, formalisms which make them equivalent to context independent grammars exist

H. Gaifman, Dependency systems and phrase-structure systems. Information & Control, 8, 1965.

but other formalisms, which allow them to describe mildly context-sensitive languages, exist as well:

H. Maruyama, Constraint dependency grammar and its weak generative capacity. Computer Software, 1990.

2. From a linguistic point of view. This point of view refers to the easiness with which a linguist can describe linguistic phenomena typical of a specific language using a specific formalism. From this point of view we think the answer to your question depends on the considered language and on the linguistic tradition which exists for that specific language. With respect to the Romanian language we consider the Dependency Grammar formalism more adequate since it is closer to the traditional way of performing syntactic analysis of Romanian and therefore permits more easily to incorporate knowledge provided by Romanian linguists.

3. From the point of view of natural language stochastic modeling. For a complete discussion concerning the advantages provided by Dependency Grammars in stochastic modeling of natural language see section 12.1.7 of

C. D. Manning, H. Schutze, Foundations of Statistical Natural Language Processing. The MIT Press, 1999.

For the moment we shall only mention the fact that the best stochastic parsing system known until now is based on Dependency Grammars:

M. J. Collins, Three generative, lexicalised models for statistical parsing. ACL 35, 1997.

Our group has performed stochastic parsing using Dependency Grammars. According to our stochastic approach, in order to find the syntactic dependency structure of a given sentence it is not necessary to explicitly specify a Dependency Grammar. The grammar will be implicitly included in the parameters of the stochastic model, which, in turn, will be estimated by means of the linguistic data (namely of a corpus).

Within this framework one can say that finding a parsing algorithm means finding an algorithm having as input a sentence and as output the syntactic structure (S,D) of that sentence, where S=(T,P) and D have the same significance as that explained in the paper which is on the web. The stages of such an algorithm are: finding set T ("part of speech tagging"); finding set P (namely finding the dependency relations); finding set D (namely establishing the types of the dependencies).

Set T was found using an algorithm proposed by Ratnaparkhi in 1996. This algorithm is of stochastic nature and uses maximum entropy. Set P was also found by means of a stochastic algorithm, namely the algorithm proposed by Eisner, also in 1996. We have modified this algorithm by changing the stochastic model and by again using maximum entropy. The algorithm for finding set P represents an implementation of the Dynamic Programming Method with the aim of finding the most probable parse in a bottom-up manner. After determining sets T and P, finding set D is no longer a problem.

Our group has already performed "dependency parsing" of Romanian sentences in a stochastic manner. According to this approach, in order to find the syntactic dependency structure of a given sentence it is not necessary to explicitly specify a Dependency Grammar. The grammar will be implicitly included in the parameters of the stochastic model, which, in turn, will be estimated by means of the linguistic data (namely of a corpus).

Within this framework one can say that finding a parsing algorithm means finding an algorithm having as input a sentence and as output the syntactic structure (S,D) of that sentence, where S=(T,P) and D have the same significance as that explained in the paper which is on the web. The stages of such an algorithm are: finding set T ("part of speech tagging"); finding set P (namely finding the dependency relations); finding set D (namely establishing the types of the dependencies).

Set T was found using an algorithm proposed by Ratnaparkhi in 1996. This algorithm is of stochastic nature and uses maximum entropy. Set P was also found by means of a stochastic algorithm, namely the algorithm proposed by Eisner, also in 1996. We have modified this algorithm by changing the stochastic model and by again using maximum entropy. The algorithm for finding set P represents an implementation of the Dynamic Programming Method with the aim of finding the most probable parse in a bottom-up manner. After determining sets T and P, finding set D is no longer a problem.

Detecting dependencies is relevant mainly because, at the heart of sentence structure are the relations among words, no matter if by these relations we mean the possible grammatical functions or the links which bind words into larger units (like phrases, for instance). Unlike generative grammars, dependency grammars can describe linguistic phenomena like the variation of word order within a sentence or the existence of discontinuous constituents more successfully. As far as applications are concerned, the formalism of dependency relations has been proven to be more adequate than the generative grammars formalism for being combined with maximum entropy modeling in order to obtain a stochastic parser, for instance.

The classical top-down and bottom-up parsing algorithms are based on generative grammars, which view the sentence structure as being formed of constituents. In this case, the structure of a sentence, given by its constituents, represents the main concept of syntax. Unlike generative grammars, dependency grammars are not based on the notion of constituent but on the direct relations existing among words. The dependency structure can be viewed, among other ways, versus constituent structure. The main isea behind the notion of dependency is that each word depends on the word which links it to the rest of the sentence, practically explaining why it is used. Unlike generative grammars, dependency grammars can describe linguistic phenomena like the variation of word order within a sentence or the existence of discontinuous constituents more successfully.

Another class of grammars which generates languages not having a direct link to the Chomsky hierarchy is that of Contextual Grammars. Contextual Grammars were introduced by Solomon Marcus in 1969 as "intrinsic grammars" without auxiliary symbols, based only on the fundamental linguistic operation of inserting words into given phrases according to certain contextual dependencies. Contextual Grammars include contexts i.e. pairs of words, associated with selectors (sets of words). A context can be adjoined to any associated selector element. In this way, starting from a finite set of words (axioms), the language is generated. It has been shown that this formalism provides an appropriate description of natural languages. It is only in 1999 that K. Harbusch succeeds in presenting a parser based on contextual grammars. Recent promising results have encouraged researchers to concentrate on building a contextual grammar for English.

Other types of grammars used in NLP are Link Grammars and Tree Adjoining Grammars, as well as others. Please feel free to contact us again if you are interested in finding out more about a specific class of grammars.

Since a standard set of tags for syntactic annotation of a text does not exist yet, DGA uses a set of tags inspired by XCES (the standard set of tags for representing morphosyntactic annotation) in order to represent annotated texts. The general idea was that of using a set of tags as simple as possible so that it can easily become compatible with a future standard. From XCES we have kept those tags indicating the general structure (sentence delimitation by <s>...</s>, delimitation of each token within a sentence by <tok>...</tok>). Corresponding to each token we have kept the marking of the orthographic form by <orth>...</orth>and of the non-ambiguous part of speech by <ctag>...</ctag> . We have given up those XCES tags which refer to morphological information and we have created new tags corresponding to syntactic information: <syn>...</syn>, <head>...</head>, <reltype>...</reltype>.

There are various possible solutions to this problem. In what follows, we are presenting a solution that has already been implemented:

First of all, the XML files resulting as a consequence of DGA annotation have been transformed, using XSLT, into HTML files. Within the HTML files each sentence is contained in a FORM. As a consequence of the SUBMIT operation (in our case click on a sentence), the FORM will send the server (by means of some fields of type HIDDEN) the information contained in the annotation. Based on this information a perl script existing on the server builds a jpeg image that represents the annotation in the usual graphical form. This image is returned to the browser, which will display it in a new window. You can see how this works at the address:

http://phobos.cs.unibuc.ro/roric/texts/indexro.html

Defining a Dependency Grammar for a specific language requires finding a set of constraints that can help in establishing the fact that certain syntactic structures are correct, while others are not. For instance, according to such constraints one can decide that certain words of a sentence can be head words, while others can not. In other words, specifying a Dependency Grammar for a specific language means finding a set of rules which indicate what dependency relations are accepted in that language. Defining such constraints and rules corresponding to a specific language can be a very difficult and time consuming task. This is probably one of the reasons why a Dependency Grammar for Romanian does not exist yet. Our group has established a set of dependency relations in Romanian, relations that can be used in performing various tasks, such as stochastic parsing of Romanian sentences.

Syntactic parsing has been performed, within the formal framework of Dependency Grammars, using "Constraint Dependency Grammar" - CDG (Maruyama, 1990). Decision procedures for dependency parsing using graded constraints exist. CDG strictly separates possible structural descriptions from the correctness conditions for linguistic structures. CDG is weakly context-sensitive. In order to learn about CDG based algorithms, we recommend

Menzel,Wolfgang and Schroder,Ingo, "Decision procedures for dependency parsing using graded constraints", in: Sylvain Kahane si Alain Polguere, editors, "Proc. Coling - ACL Workshop on Processing of Dependency-based Grammars", pag. 78-87, Montreal, Canada, 1998.

Our group has also performed dependency parsing, using a stochastic approach. This approach consists of associating a probability to each syntactic structure, and of choosing that syntactic structure which has the maximum associated probability corresponding to each given sentence. Assigning such a probability means finding a stochastic model, namely the most adequate one. According to this approach, in order to find the syntactic dependency structure of a given sentence it is not necessary to explicitly specify a Dependency Grammar. The grammar will be implicitly included in the parameters of the stochastic model, which, in turn, will be estimated by means of the linguistic data (namely of a corpus).

Within this framework one can say that finding a parsing algorithm means finding an algorithm having as input a sentence and as output the syntactic structure (S,D) of that sentence, where S=(T,P) and D have the same significance as that explained in the paper which is on the web.

The stages of such an algorithm are: finding set T ("part of speech tagging"); finding set P (namely finding the dependency relations); finding set D (namely establishing the types of the dependencies).

Set T was found using an algorithm proposed by Ratnaparkhi in 1996. This algorithm is of stochastic nature and uses maximum entropy. Set P was also found by means of a stochastic algorithm, namely the algorithm proposed by Eisner, also in 1996. We have modified this algorithm by changing the stochastic model and by again using maximum entropy. The algorithm for finding set P represents an implementation of the Dynamic Programming Method with the aim of finding the most probable parse in a bottom-up manner. After determining sets T and P, finding set D is no longer a problem.

The formalism of Dependency Grammars has been used, within the DBR-MAT project, in the case of the Romanian language, in order to perform stochastic parsing of Romanian sentences. Within the formal framework of Dependency Grammars finding a parsing algorithm means finding an algorithm which has as input a sentence and as output the syntactic structure (S,D) of that sentence, where S=(T,P) and D have the same significance as in the paper which now exists on the web. The steps of such an algorithm are: finding set T ("part of speech tagging"), finding set P (namely the dependency relations) and finding set D (namely the types of the dependencies). The main conclusion that we came to, within the DBR-MAT project, and independently of any specific language, was that the formalism of Dependency Grammars is extremely adequate and can be successfully used in performing stochastic parsing.

The main theories in the DG family are the following ones:

• Case Grammar (Anderson)

• Daughter-Dependency Theory (Hudson)

• Dependency Unification Grammar (Hellwig)

• Functional-Generative Description (Sgall)

• Lexicase (Starosta)

• Meaning-Text Model (Melcuk)

• Metataxis (Schubert)

• Unification Dependency Grammar (Maxwell)

• Constraint Dependency Grammar (Maruyama)

As Richard Hudson points out, grammars, and theories of grammar, can be classified according to whether the basic unit of sentence structure is:

• the phrase (PSG);

• the dependency between two words (DG).

Each approach implies the other:

• PSG implies inter-word dependencies (but only if one word is chosen as the phrasal head);

• DG implies phrases (a word plus its dependents and their phrases constitutes a phrase).

A number of logicians, including Bar-Hillel, proved that DG (including Categorial Grammar) is WEAKLY equivalent to a context-free PSG (Gaifman, "Dependency systems and phrase-structure systems"). This result is generally accepted. But it is NOT a notational variant of PSG because it is not STRONGLY equivalent - i.e., as Richard Hudson points out, it does not allow the same analyses:

• phrases are implicit, not explicit so 
  - phrases can not be classified separately from their heads;

• relations are explicit, not implicit, so 
  - relations can be classified and labelled;

• all phrases must be endocentric, so 
  - apparently exocentric constructions such as gerunds (an NP with the internal structure of a clause) are a fundamental challenge;

• no non-terminal nodes are allowed, so DG does not allow 
  - unary branching (e.g. NP consisting of just N),

• VP (contrasting with V).

Word Grammar is a theory which Richard Hudson has been developing since the early 1980s. It is firmly based on DG and probably has the best possible combination of other features. The main features of WG as noted by its author are:

• it is monostratal - there is only one syntactic structure per sentence, paired with a semantic structure and a phonological one;

• it is enriched - it allows multiple dependencies (a word can have more than one parent);

• it generalizes by means of default inheritance based on the 'isa' relationship;

• it allows labelled relationships (in an isa hierarchy);

• it is non-modular and cognitive: language is an area of the general network of knowledge.

DGA is not semi-automatic in the sense that it does not contain an internal mechanism for initially annotating a corpus in order to present it to the user for performing corrections. DGA has been thus designed in order to make it language independent and as independent as possible from all types of formalisms related to Dependency Grammars. However, DGA can easily be turned into a semi-automatic tool by integrating various external products (POS tagger, parser etc.). DGA allows viewing and modifying previously annotated corpora (by using the Open corpus command of menu File). Although, initially, this facility was intended to be used in order to modify annotations performed by means of DGA, it can also be used in the case of various external products (POS tagger, parser etc.). In order to do this it is only necessary for the automatically annotated corpus (with the external product) to be turned from the format used by the corresponding external product into the XML format used by DGA. After performing this operation the corpus can be opened with DGA and the automatically performed annotations can be corrected.

One example of Dependency Grammar - based applications is parsing, the software applications being the corresponding parsing programs.

Syntactic parsing has been performed, within the formal framework of Dependency Grammars, using "Constraint Dependency Grammar" - CDG (Maruyama, 1990). Decision procedures for dependency parsing using graded constraints exist. CDG strictly separates possible structural descriptions from the correctness conditions for linguistic structures. CDG is weakly context-sensitive. In order to learn about CDG based algorithms, we recommend reading

Menzel,Wolfgang and Schroder,Ingo, "Decision procedures for dependency parsing using graded constraints", in: Sylvain Kahane si Alain Polguere, editors, "Proc. Coling - ACL Workshop on Processing of Dependency-based Grammars", pag. 78-87, Montreal, Canada, 1998.

As far as our group is concerned, we have performed dependency parsing using a stochastic approach. It consists of associating a probability to each syntactic structure, and of choosing that syntactic structure which has the maximum associated probability corresponding to each given sentence. Assigning such a probability means finding a stochastic model, namely the most adequate one. According to this approach, in order to find the syntactic dependency structure of a given sentence it is not necessary to explicitly specify a Dependency Grammar. The grammar will be implicitly included in the parameters of the stochastic model, which, in turn, will be estimated by means of the linguistic data (namely of a corpus).

Within this framework one can say that finding a parsing algorithm means finding an algorithm having as input a sentence and as output the syntactic structure (S,D) of that sentence, where S=(T,P) and D have the same significance as that explained in the paper which is on the web.

The stages of such an algorithm are: finding set T ("part of speech tagging"); finding set P (namely finding the dependency relations); finding set D (namely establishing the types of the dependencies).

Set T was found using an algorithm proposed by Ratnaparkhi in 1996. This algorithm is of stochastic nature and uses maximum entropy. Set P was also found by means of a stochastic algorithm, namely the algorithm proposed by Eisner, also in 1996. We have modified this algorithm by changing the stochastic model and by again using maximum entropy. The algorithm for finding set P represents an implementation of the Dynamic Programming Method with the aim of finding the most probable parse in a bottom-up manner. After determining sets T and P, finding set D is no longer a problem.

The existing programs are language independent and have been successfully tested by us in the case of the Romanian language.

XCES (XML Corpus Encoding Standard) is a standard for corpus representation. More information and details concerning XCES can be found at

http://www.cs.vassar.edu/XCES

Yes, it can. In order to be used for morpho-syntactic annotation as well it is only necessary for DGA to allow the specifying of morphological information relatively to each word. This can be easily done by adding, in the contextual menu which is opened when performing a right click on a word, a command of type "morphology", for instance. When using this command you will be able to enter the morphological information corresponding to a specific word inside a dialog box which will open up.

Yes, this possibility exists. DGA allows viewing and modifying previously annotated corpora (by using the Open corpus command of menu File). Although, initially, this facility was intended to be used in order to modify annotations performed by means of DGA, it can also be used in the case of various external products (POS tagger, parser etc.). In order to do this it is only necessary for the automatically annotated corpus (with the external product) to be turned from the format used by the corresponding external product into the XML format used by DGA. After performing this operation the corpus can be opened with DGA and the automatically performed annotations can be corrected (modified).

Questions Referring to HPSG

Yes, there are. Among the most recent ones (known by us) is an implementation of the HPSG grammar of interrogatives in English. There is also a computational implementation of Andreas Kathol's analysis of word order phenomena in German.

Up to the past year, there were two courses of HPSG, both at the Faculty of Letters of the University of Bucharest: an introductory one (for the fourth year of studies), and another one with more applications to Romanian, for the master program in theoretical linguistics. By a decision of the head of the department of Romanian, the former course was eliminated, so during this academic year only one HPSG course is being delivered.

The ultimate roots of HPSG lie in Chomsky's program of the Universal Grammar. In this sense, HPSG is a version of the Universal Grammar, because it is naturally interested in the invariants of human language. Unlike Chomsky's program, though, HPSG does not privilege those invariants. On the contrary, HPSG also approaches those facts tight to the idiosynchratic aspects of languages. From this point of view, HPSG is rather close to 'traditional grammar'.

We are already applying it. You will see this, in just a few months, right here, in this page. In fact, we are a small group of researchers analyzing Romanian from the HPSG perspective.

This is a phrase of type head-subject. The subject is the noun phrase "the girl", while the head is the verb phrase "is laughing happy". This latter phrase is of type head-adjunct. The head is the verb "is laughing" and the adjunct is the adjective "happy". English does not force the adjective to show agreement features between the adjective and the subject noun phrase "the girl". But, in a language like Romanian, this agreement is obligatory. HPSG resolves this further dependency in a very simple way: the adjective displays the information that its subject is identical to the subject of the phrase "is laughing happy".

Strict (or strong) lexicalism is the view that the internal structure of the word is independent of the way the words contribute to the structure of the phrases. Strict lexicalism characterizes HPSG as well as other grammatical theories - for instance, the Minimalist Program also adheres to it, in spite of the fact that the previous version of Chomsky's program - The GB Theory - is not lexicalist.

There are three components of the HPSG treatment of LDDs: a constraint on a particular type of phrase (i. e. the head-filler phrase), a constraint on phrases instantiating the feature SLASH, and a constraint ruling the collection of this feature on a lexical head (for details see the presentation on our web site, section 2.2.2.2). Thanks to these constraints, a 'gap' is 'collected' by a lexical head and it is allowed to percolate up to the point where it is 'filled' with the corresponding grammatical information:

(1) Bagels i , John always said that he likes _ i.

In (i) and (iv), likes and said, respectively, 'collect' the gap, in (ii)-(iii), and (v)-(vi) the gap successively 'percolates' different phrases, while (1) is the closure itself of the gap (through the constraint on the head-filler phrase).:

(i) likes _ i 
(ii) he likes _ i 
(iii) that he likes _ i 
(iv) said that he likes _ i. 
(v) always said that he likes _ i 
(vi) John always said that he likes _ i.

Pollard and Sag ("Head-driven Phrase Structure Grammar", Chicago University Press, 1994, 73-88) classify agreement according to the elements involved in this relationship:

1. Pronoun-antecedent

2. Subject-verb

3. Determiner-noun

One must emphasize the fact that this classification does not follow from theory-internal reasons. That is, it is not determined by the fact that someone works in HPSG. This classification is determined by the nature of the language subject to investigation - in the present case, English.

No, I don't think this is possible. If, for instance, we start up with the information about noun-adjective agreement in Romanian, without knowing anything about what happens in English concerning the same topic, we will probably be inclined to transfer the peculiarities of agreement in Romanian to English (which is, of course, a mistake).

Yes, one may do so. What is unified can equally be regarded as a union.

Yes, there are, for instance, in Doina Tatar, "Inteligenta artificiala", Editura Albastra, Cluj, 2001.

Type hpsg as a key word and you will find an address for the site "HPSG literature", which contains bibliography. Many works are accessible on line.

I am not sure I understand correctly what you mean by "HPSG-based computational devices". If you refer to HPSG principles (for instance the (syntactic) principle of the HEAD features, which - in my terminology - is a HPSG-based computational device), then I would say that I know of no specific implemetation. Nevertheless, he who wants to implement a certain fragment of a grammar, cannot avoid the implementation of the most general HPSG devices - or principles - like HFP. So, even if I am not able to indicate a specific work dealing with this topic, such an implementation must exist, and, for sure, it is feasible.

We know of PROLOG HPSG applications but we think that such applications in LISP also exist.

Yes, it does. The way constraints are checked in HPSG resembles much the way you may perform independent operations when you use your computer. For instance, you are not bound to quit the program Word if you want to listen to a CD: you simply use the CD option and you continue working. Similarly, constraints are checked independently, that is, no order is a priori imposed.

Most HPSG applications are programmed (especially in Europe) in PROLOG. This, of course, does not mean that one should underestimate LISP.

HPSG considers itself to be a grammar of a language in general, so I would not say that there are "privileged" and "disgraced" phenomena (so to speak). Nevertheless, I might "reverse" the question and focus on what was felt as a failure: the analysis of unbounded dependencies (like in the sentence "Who do you think killed Kennedy ?") which was subject to a careful and long elaboration - the first version not being satisfactory. Also, the analysis of relative clauses (which is a chapter of Unbounded Dependencies) enjoyed successive reconsiderations.

Yes, it is. Nevertheless, it has to be said that in the absence of these devices the analysis of certain phenomena in natural language would meet impressive difficulties.

Structure sharing expresses identities of information which are essential to the correctness of the construction. For instance, in the sentence "John, nobody believes that police looks for it" it is essential to point out that the NP John is at the same time the understood object of the verb to look for. On the contrary, the fact that nobody and police have the same person and number is not essential for the grammaticality of the sentence. Consequently, there is a distinction between the two identities and it is the duty of the theory to emphasize it. Structure sharing makes the difference.

This structure is first a phrase of type head-subject (the head being the phrase "shines happy" and the subject being the NP "the moon ". The VP "shines happy", in turn, is a phrase of type head-adjunct. The verb is the head while the adjective is the adjunct. In Romanian, unlike English, this sentence shows the double dependency of the adjective - because of the visible agreement features of the adjective: the gender and the number of the adjective must be the same with the gender and the number of the NP "the moon". This double dependency is pointed out simply by a notation which shows that the subject of the adjective must be the same with the subject of the verb. This renders the derivational procedure of the standard theory useless: no need any longer to invoke a more basic structure of type "The moon shines and is happy" which is subject to a transformation.

Ivan A. Sag (professor of linguistics and symbolic systems at Stanford University) and Carl Pollard (professor of linguistics at Ohio State University).

The main utility consists in the fact that the analysis becomes testable and it thereby may offer hypotheses concerning the psychological plausibility of the way the structure subject to analysis is appropriated.

Because it discovered no convincing evidence that movement really does exist.

Yes, there are. I would first mention Monachesi's analyses of weak pronouns. There is also an analysis of the multiple negation by Emil Ionescu (published in the Proceedings of Formal Grammar Conference, Utrecht 1999). Ana Maria Barbu proposed an analysis of the constituent order in the NP (the work is in print). Finally, a promising fact is that several dissertations of the students interested in HPSG applications exist.

HPSG makes no use of any operation of movement whatsoever, because it does not find any convincing evidence that this operation really does exist as a part of the mental grammar.

Pollard and Sag ("Head-driven Phrase Structure Grammar", Chicago University Press, 1994, 73-88) treat agreement according to the elements involved in this relationship:

1. Pronoun-antecedent

2. Subject-verb

3. Determiner-noun

We must emphasize the fact that this classification does not follow from theory-internal reasons. That is, it is not determined by the fact that someone works in HPSG. This classification is determined by the nature of the language subject to investigation - here, English.

The essential element in the HPSG treatment of phrasal types is the property of having a non-empty value for the feature DAUGHTERS. That is, a phrase is bound to have inner structure, reflected in the fact that it can be decomposed according to elements that may be either words or phrases (but not morphemes). This is the most general property of phrases. Further on, the diversity of phrasal types depends on the language subject to investigation. For instance, Romanian, but not also English, bears a phrase of type head-marker used to 'make obvious' certain direct objects NPs:

Ion o iubeste pe
Maria John loves Mary

The main 'levels' of lexical information within HPSG are the grammatical one, the semantical one, the phonological one and the pragmatical one. There is also a level accounting for the word placement within a phrase.

What is specific to lexical representations in HPSG is the fact that they are rich - if compared for instance with GB lexical representations. This is because lexical representations account for facts - such as long distance dependencies, quantification or binding - which in other grammatical frameworks are treated as independent and autonomous phenomena.