s2fieldsofstudy:
Computer Science
Linguistics

text:
Statistical Parsing of Morphologically Rich Languages (SPMRL) What, How and Whither

The term Morphologically Rich Languages (MRLs) refers to languages in which significant information concerning syntactic units and relations is expressed at word-level. There is ample evidence that the application of readily available statistical parsing models to such languages is susceptible to serious performance degradation. The first workshop on statistical parsing of MRLs hosts a variety of contributions which show that despite language-specific idiosyncrasies, the problems associated with parsing MRLs cut across languages and parsing frameworks. In this paper we review the current state-of-affairs with respect to parsing MRLs and point out central challenges. We synthesize the contributions of researchers working on parsing Arabic, Basque, French, German, Hebrew, Hindi and Korean to point out shared solutions across languages. The overarching analysis suggests itself as a source of directions for future investigations.

Introduction
The availability of large syntactically annotated corpora led to an explosion of interest in automatically inducing models for syntactic analysis and disambiguation called statistical parsers. The development of successful statistical parsing models for English focused on the Wall Street Journal Penn Treebank (PTB, (Marcus et al., 1993)) as the primary, and sometimes only, resource. Since the initial release of the Penn Treebank (PTB Marcus et al. (1993)), many different constituent-based parsing models have been developed in the context of parsing English (e.g. (Magerman, 1995;Collins, 1997;Charniak, 2000;Chiang, 2000;Bod, 2003;Charniak and Johnson, 2005;Petrov et al., 2006;Huang, 2008;Finkel et al., 2008;Carreras et al., 2008)). At their time, each of these models improved the state-of-the-art, bringing parsing performance on the standard test set of the Wall-Street-Journal to a performance ceiling of 92% F 1 -score using the PARS-EVAL evaluation metrics (Black et al., 1991). Some of these parsers have been adapted to other language/treebank pairs, but many of these adaptations have been shown to be considerably less successful.
Among the arguments that have been proposed to explain this performance gap are the impact of small data sets, differences in treebanks' annotation schemes, and inadequacy of the widely used PARS-EVAL evaluation metrics. None of these aspects in isolation can account for the systematic performance deterioration, but observed from a wider, crosslinguistic perspective, a picture begins to emergethat the morphologically rich nature of some of the languages makes them inherently more susceptible to such performance degradation. Linguistic factors associated with MRLs, such as a large inventory of word-forms, higher degrees of word order freedom, and the use of morphological information in indicating syntactic relations, makes them substantially harder to parse with models and techniques that have been developed with English data in mind.
In addition to these technical and linguistic factors, the prominence of English parsing in the literature reduces the visibility of research aiming to solve problems particular to MRLs. The lack of streamlined communication among researchers working on different MRLs often leads to a reinventing the wheel syndrome. To circumvent this, the first workshop on Statistical Parsing of Morphologically Rich Languages (SPMRL 2010) offers a platform for this growing community to share their views of the different problems and oftentimes similar solutions.
We identify three main types of challenges, each of which raises many questions. Many of the questions are yet to be conclusively answered. The first type of challenges has to do with the architectural setup of parsing MRLs: What is the nature of the input? Can words be represented abstractly to reflect shared morphological aspects? How can we cope with morphological segmentation errors propagated through the pipeline? The second type concerns the representation of morphological information inside the articulated syntactic model: Should morphological information be encoded at the level of PoS tags? On dependency relations? On top of non-terminals symbols? How should the integrated representations be learned and used? A final genuine challenge has to do with sound estimation for lexical probabilities: Given the finite, and often rather small, set of data, and the large number of morphological analyses licensed by rich inflectional systems, how can we analyze words unseen in the training data?
Many of the challenges reported here are mostly irrelevant when parsing Section 23 of the PTB but they are of primordial importance in other tasks, including out-of-domain parsing, statistical machine translation, and parsing resource-poor languages. By synthesizing the contributions to the workshop and bringing it to the forefront, we hope to advance the state of the art of statistical parsing in general.
In this paper we therefore take the opportunity to analyze the knowledge that has been acquired in the different investigations for the purpose of identifying main bottlenecks and pointing out promising research directions. In section 2, we define MRLs and identify syntactic characteristics associated with them. We then discuss work on parsing MRLs in both the dependency-based and constituency-based setup. In section 3, we review the types of chal-lenges associated with parsing MRLs across frameworks. In section 4, we focus on the contributions to the SPMRL workshop and identify recurring trends in the empirical results and conceptual solutions. In section 5, we analyze the emerging picture from a bird's eye view, and conclude that many challenges could be more faithfully addressed in the context of parsing morphologically ambiguous input.

What are MRLs?
The term Morphologically Rich Languages (MRLs) is used in the CL/NLP literature to refer to languages in which substantial grammatical information, i.e., information concerning the arrangement of words into syntactic units or cues to syntactic relations, is expressed at word level.
The common linguistic and typological wisdom is that "morphology competes with syntax" (Bresnan, 2001). In effect, this means that rich morphology goes hand in hand with a host of nonconfigurational syntactic phenomena of the kind discussed by Hale (1983). Because information about the relations between syntactic elements is indicated in the form of words, these words can freely change their positions in the sentence. This is referred to as free word order (Mithun, 1992). Information about the grouping of elements together can further be expressed by reference to their morphological form. Such logical groupings of disparate elements are often called discontinuous constituents. In dependency structures, such discontinuities impose nonprojectivity. Finally, rich morphological information is found in abundance in conjunction with so-called pro-drop or zero anaphora. In such cases, rich morphological information in the head (or co-head) of the clause often makes it possible to omit an overt subject which would be semantically impoverished.
English, the most heavily studied language within the CL/NLP community, is not an MRL. Even though a handful of syntactic features (such as person and number) are reflected in the form of words, morphological information is often secondary to other syntactic factors, such as the position of words and their arrangement into phrases. German, an Indo-European language closely related to English, already exhibits some of the properties that make parsing MRLs problematic. The Semitic languages Arabic and Hebrew show an even more extreme case in terms of the richness of their morphological forms and the flexibility in their syntactic ordering.

Parsing MRLs
Pushing the envelope of constituency parsing: The Head-Driven models of the type proposed by Collins (1997) have been ported to parsing many MRLs, often via the implementation of Bikel (2002). For Czech, the adaptation by Collins et al. (1999) culminated in an 80 F 1 -score.
German has become almost an archetype of the problems caused by MRLs; even though German has a moderately rich morphology and a moderately free word order, parsing results are far from those for English (see (Kübler, 2008) and references therein). Dubey (2005) showed that, for German parsing, adding case and morphology information together with smoothed markovization and an adequate unknown-word model is more important than lexicalization (Dubey and Keller, 2003).
For Modern Hebrew, Tsarfaty and Sima'an (2007) show that a simple treebank PCFG augmented with parent annotation and morphological information as state-splits significantly outperforms Head-Driven markovized models of the kind made popular by Klein and Manning (2003). Results for parsing Modern Standard Arabic using Bikel's implementation on gold-standard tagging and segmentation have not improved substantially since the initial release of the treebank (Maamouri et al., 2004;Kulick et al., 2006;Maamouri et al., 2008).
For Italian, Corazza et al. (2004) used the Stanford parser and Bikel's parser emulation of Collins' model 2 (Collins, 1997) on the ISST treebank, and obtained significantly lower results compared to English. It is notable that these models were applied without adding morphological signatures, using gold lemmas instead. Corazza et al. (2004) further tried different refinements including parent annotation and horizontal markovization, but none of them obtained the desired improvement.
For French, Crabbé and Candito (2008) and Seddah et al. (2010) show that, given a corpus comparable in size and properties (i.e. the number of tokens and grammar size), the performance level, both for Charniak's parser (Charniak, 2000) and the Berke-ley parser (Petrov et al., 2006) was higher for parsing the PTB than it was for French. The split-mergesmooth implementation of (Petrov et al., 2006) consistently outperform various lexicalized and unlexicalized models for French (Seddah et al., 2009) and for many other languages (Petrov and Klein, 2007). In this respect, (Petrov et al., 2006) is considered MRL-friendly, due to its language agnostic design.
The rise of dependency parsing: It is commonly assumed that dependency structures are better suited for representing the syntactic structures of free word order, morphologically rich, languages, because this representation format does not rely crucially on the position of words and the internal grouping of surface chunks (Mel'čuk, 1988). It is an entirely different question, however, whether dependency parsers are in fact better suited for parsing such languages.
The CoNLL shared tasks on multilingual dependency parsing in (Buchholz and Marsi, 2006Nivre et al., 2007a) demonstrated that dependency parsing for MRLs is quite challenging. While dependency parsers are adaptable to many languages, as reflected in the multiplicity of the languages covered, 1 the analysis by Nivre et al. (2007b) shows that the best result was obtained for English, followed by Catalan, and that the most difficult languages to parse were Arabic, Basque, and Greek. Nivre et al. (2007a) drew a somewhat typological conclusion, that languages with rich morphology and free word order are the hardest to parse. This was shown to be the case for both MaltParser (Nivre et al., 2007c) and MST (McDonald et al., 2005), two of the best performing parsers on the whole.

Annotation and evaluation matter:
An emerging question is therefore whether models that have been so successful in parsing English are necessarily appropriate for parsing MRLs -but associated with this question are important questions concerning the annotation scheme of the related treebanks. Obviously, when annotating structures for languages with characteristics different than English one has to face different annotation decisions, and it comes as no surprise that the annotated structures for MRLs often differ from those employed in the PTB.
For Spanish and French, it was shown by Cowan and Collins (2005) and in (Arun and Keller, 2005;Schluter and van Genabith, 2007), that restructuring the treebanks' native annotation scheme to match the PTB annotation style led to a significant gain in parsing performance of Head-Driven models of the kind proposed in (Collins, 1997). For German, a language with four different treebanks and two substantially different annotation schemes, it has been shown that a PCFG parser is sensitive to the kind of representation employed in the treebank.
Dubey and Keller (2003), for example, showed that a simple PCFG parser outperformed an emulation of Collins' model 1 on NEGRA. They showed that using sister-head dependencies instead of headhead dependencies improved parsing performance, and hypothesized that it is due to the flatness of phrasal annotation. Kübler et al. (2006) showed considerably lower PARSEVAL scores on NEGRA (Skut et al., 1998) relative to the more hierarchically structured TüBa-D/Z (Hinrichs et al., 2005), again, hypothesizing that this is due to annotation differences.
Related to such comparisons is the question of the relevance of the PARSEVAL metrics for evaluating parsing results across languages and treebanks. Rehbein and van Genabith (2007) showed that PARS-EVAL measures are sensitive to annotation scheme particularities (e.g. the internal node ratio). It was further shown that different metrics (i.e. the Leafancestor path (Sampson and Babarczy, 2003) and dependency based ones in (Lin, 1995)) can lead to different performance ranking. This was confirmed also for French by Seddah et al. (2009).
The questions of how to annotate treebanks for MRLs and how to evaluate the performance of the different parsers on these different treebanks is crucial. For the MRL parsing community to be able to assess the difficulty of improving parsing results for French, German, Arabic, Korean, Basque, Hindi or Hebrew, we ought to first address fundamental questions including: Is the treebank sufficiently large to allow for proper grammar induction? Does the annotation scheme fit the language characteristics? Does the use of PTB annotation variants for other languages influence parsing results? Does the spacedelimited tokenization allow for phrase boundary detection? Do the results for a specific approach generalize to more than one language?

Primary Research Questions
It is firmly established in theoretical linguistics that morphology and syntax closely interact through patterns of case marking, agreement, clitics and various types of compounds. Because of such close interactions, we expect morphological cues to help parsing performance. But in practice, when trying to incorporate morphological information into parsing models, three types of challenges present themselves: Architecture and Setup: When attempting to parse complex word-forms that encapsulate both lexical and functional information, important architectural questions emerge, namely, what is the nature of the input that is given to the parsing system? Does the system attempt to parse sequences of words or does it aim to assign structures to sequences of morphological segments? If the former is the case, how can we represent words abstractly so as to reflect shared morphological aspects between them? If the latter is the case, how can we arrive at a good enough morphological segmentation for the purpose of statistical parsing, given raw input texts?
When working with morphologically rich languages such as Hebrew or Arabic, affixes may have syntactically independent functions. Many parsing models assume segmentation of the syntactically independent parts, such as prepositions or pronominal clitics, prior to parsing. But morphological segmentation requires disambiguation which is non-trivial, due to case syncretism and high morphological ambiguity exhibited by rich inflectional systems. The question is then when should we disambiguate the morphological analyses of input forms? Should we do that prior to parsing or perhaps jointly with it? 2 Representation and Modeling: Assuming that the input to our system reflects morphological information, one way or another, which types of morpho-logical information should we include in the parsing model? Inflectional and/or derivational? Case information and/or agreement features? How can valency requirements reflected in derivational morphology affect the overall syntactic structure? In tandem with the decision concerning the morphological information to include, we face genuine challenges concerning how to represent such information in the syntactic model, be it constituency-based or dependencybased. Should we encode morphological information at the level of PoS tags and/or on top of syntactic elements? Should we decorate non-terminals nodes and/or dependency arcs or both?
Incorporating morphology in the statistical model is often even more challenging than the sum of these bare decisions, because of the nonconfigurational structures (free word order, discontinuous constituents) for rich markings are crucial (Hale, 1983). The parsing models designed for English often focus on learning rigid word order, and they do not take morphological information into account (cf. developing parsers for German (Dubey and Keller, 2003;Kübler et al., 2006)). The more complex question is therefore: what type of parsing model should we use for parsing MRLs? shall we use a general purpose implementation and attempt to amend it? how? or perhaps we should devise a new model from first principles, to address nonconfigurational phenomena effectively? using what form of representation? is it possible to find a single model that can effectively cope with different kinds of languages?

Estimation and Smoothing:
Compared to English, MRLs tend to have a greater number of word forms and higher out-of-vocabulary (OOV) rates, due to the many feature combinations licensed by the inflectional system. A typical problem associated with parsing MRLs is substantial lexical data sparseness due to high morphological variation in surface forms. The question is therefore, given our finite, and often fairly small, annotated sets of data, how can we guess the morphological analyses, including the PoS tag assignment and various features, of an OOV word? How can we learn the probabilities of such assignments? In a more general setup, this problem is akin to handling out-of-vocabulary or rare words for robust statistical parsing, and techniques for domain adaptation via lexicon enhance-  ment (also explored for English and other morphologically impoverished languages). So, in fact, incorporating morphological information inside the syntactic model for the purpose of statistical parsing is anything but trivial. In the next section we review the various approaches taken in the individual contributions of the SPMRL workshop for addressing such challenges.

Parsing MRLs: Recurring Trends
The first workshop on parsing MRLs features 11 contributions for a variety of languages with a range of different parsing frameworks. Table 1 lists the individual contributions within a cross-language cross-framework grid. In this section, we focus on trends that occur among the different contributions. This may be a biased view since some of the problems that exist for parsing MRLs may have not been at all present, but it is a synopsis of where we stand with respect to problems that are being addressed.

Architecture and Setup: Gold vs. Predicted Morphological Information
While morphological information can be very informative for syntactic analysis, morphological analysis of surface forms is ambiguous in many ways. In German, for instance, case syncretism (i.e. a single surface form corresponding to different cases) is pervasive, and in Hebrew and Arabic, the lack of vocalization patterns in written texts leads to multiple morphological analyses for each space-delimited token. In real world situations, gold morphological information is not available prior to parsing. Can parsing systems make effective use of morphology even when gold morphological information is absent?
Several papers address this challenge by presenting results for both the gold and the automatically predicted PoS and morphological information (Ambati et al., 2010a;Marton et al., 2010;Goldberg and Elhadad, 2010;Seddah et al., 2010). Not very surprisingly, all evaluated systems show a drop in parsing accuracy in the non-gold settings.
An interesting trend is that in many cases, using noisy morphological information is worse than not using any at all. For Arabic Dependency parsing, using predicted CASE causes a substantial drop in accuracy while it greatly improves performance in the gold setting (Marton et al., 2010). For Hindi Dependency Parsing, using chunk-internal cues (i.e. marking non-recursive phrases) is beneficial when gold chunk-boundaries are available, but suboptimal when they are automatically predicted (Ambati et al., 2010a). For Hebrew Dependency Parsing with the MST parser, using gold morphological features shows no benefit over not using them, while using automatically predicted morphological features causes a big drop in accuracy compared to not using them (Goldberg and Elhadad, 2010). For French Constituency Parsing, Seddah et al. (2010) and Candito and Seddah (2010) show that while gold information for the part-of-speech and lemma of each word form results in a significant improvement, the gain is low when switching to predicted information. Reassuringly, Ambati et al. (2010a), Marton et al. (2010), and Goldberg and Elhadad (2010) demonstrate that some morphological information can indeed be beneficial for parsing even in the automatic setting. Ensuring that this is indeed so, appears to be in turn linked to the question of how morphology is represented and incorporated in the parsing model.  pro-drop) in the input to the parser. Just like overt morphology, traces and null elements encapsulate functional information about relational entities in the sentence (the subject, the object, etc.), and including them at the input level provides helpful disambiguating cues for the overall structure that represents such relations. However, assuming that such traces are given prior to parsing is, for all practical purposes, infeasible. This leads to an interesting question: will identifying such functional elements (marked as traces, overt morphology, etc) during parsing, while complicating that task itself, be on the whole justified?
Closely linked to the inclusion of morphological information in the input is the choice of PoS tag set to use. The generally accepted view is that finegrained PoS tags are morphologically more informative but may be harder to statistically learn and parse with, in particular in the non-gold scenario. Marton et al. (2010) demonstrate that a fine-grained tag set provides the best results for Arabic dependency parsing when gold tags are known, while a much smaller tag set is preferred in the automatic setting.

Representation and Modeling: Incorporating Morphological Information
Many of the studies presented here explore the use of feature representation of morphological information for the purpose of syntactic parsing ( A closer view into the results mentioned in the previous paragraph suggests that, beyond the kind of information that is being used, the way in which morphological information is represented and used by the model has substantial ramification as to whether or not it leads to performance improvements. The so-called "agreement features" GEN-DER, NUMBER, PERSON, provide for an interesting case study in this respect. When included directly as machine learning features, agreement features benefit dependency parsing for Arabic (Marton et al., 2010), but not Hindi (dependency) (Ambati et al., 2010a;Ambati et al., 2010b) or Hebrew (Goldberg and Elhadad, 2010). When represented as simple splits of non-terminal symbols, agreement information does not help constituency-based parsing performance for Hebrew (Tsarfaty and Sima'an, 2010). However, when agreement patterns are directly represented on dependency arcs, they contribute an improvement for Hebrew dependency parsing (Goldberg and Elhadad, 2010). When agreement is encoded at the realization level inside a Relational-Realizational model (Tsarfaty and Sima'an, 2008), agreement features improve the state-of-the-art for Hebrew parsing (Tsarfaty and Sima'an, 2010).
One of the advantages of the latter study is that morphological information which is expressed at the level of words gets interpreted elsewhere, on functional elements higher up the constituency tree. In dependency parsing, similar cases may arise, that is, morphological information might not be as useful on the form on which it is expressed, but would be more useful at a different position where it could influence the correct attachment of the main verb to other elements. Interesting patterns of that sort occur in Basque, where the SUBORDINATIONTYPE morpheme attaches to the auxiliary verb, though it mainly influences attachments to the main verb.
Bengoetxea and Gojenola (2010) attempted two different ways to address this, one using a transformation segmenting the relevant morpheme and attaching it to the main verb instead, and another by propagating the morpheme along arcs, through a "stacking" process, to where it is relevant. Both ways led to performance improvements. The idea of a segmentation transformation imposes non-trivial pre-processing, but it may be that automatically learning the propagation of morphological features is a promising direction for future investigation.
Another, albeit indirect, way to include morphological information in the parsing model is using so-called latent information or some mechanism of clustering. The general idea is the following: when morphological information is added to standard terminal or non-terminal symbols, it imposes restrictions on the distribution of these no-longerequivalent elements.
Learning latent informa-tion does not represent morphological information directly, but presumably, the distributional restrictions can be automatically learned along with the splits of labels symbols in models such as (Petrov et al., 2006). For Korean (Chung et al., 2010), latent information contributes significant improvements. One can further do the opposite, namely, merging terminals symbols for the purpose of obtaining an abstraction over morphological features. When such clustering uses a morphological signature of some sort, it is shown to significantly improve constituency-based parsing for French (Candito and Seddah, 2010).

Representation and Modeling: Free Word Order and Flexible Constituency Structure
Off-the-shelf parsing tools are found in abundance for English. One problematic aspect of using them to parse MRLs lies in the fact that these tools focus on the statistical modeling of configurational information. These models often condition on the position of words relative to one another (e.g. in transition-based dependency parsing) or on the distance between words inside constituents (e.g. in Head-Driven parsing). Many of the contributions to the workshop show that working around existing implementations may be insufficient, and we may have to come up with more radical solutions.
Several studies present results that support the conjecture that when free word-order is explicitly taken into account, morphological information is more likely to contribute to parsing accuracy. The Relational-Realizational model used in (Tsarfaty and Sima'an, 2010) allows for reordering of constituents at a configuration layer, which is independent of the realization patterns learned from the data (vis-à-vis case marking and agreement). The easyfirst algorithm of (Goldberg and Elhadad, 2010) which allows for significant flexibility in the order of attachment, allows the model to benefit from agreement patterns over dependency arcs that are easier to detect and attach first. The use of larger subtrees in (Chung et al., 2010) for parsing Korean, within a Bayesian framework, allows the model to learn distributions that take more elements into account, and thus learn the different distributions associated with morphologically marked elements in constituency structures, to improve performance.
In addition to free word order, MRLs show higher degree of freedom in extraposition. Both of these phenomena can result in discontinuous structures. In constituency-based treebanks, this is either annotated as additional information which has to be recovered somehow (traces in the case of the PTB, complex edge labels in the German TüBa-D/Z), or as discontinuous phrase structures, which cannot be handled with current PCFG models. Maier (2010) suggests the use of Linear Context-Free Rewriting Systems (LCFRSs) in order to make discontinuous structure transparent to the parsing process and yet preserve familiar notions from constituency.
Dependency representation uses non-projective dependencies to reflect discontinuities, which is problematic to parse with models that assume projectivity. Different ways have been proposed to deal with non-projectivity (Nivre and Nilsson, 2005;Mc-Donald et al., 2005;McDonald and Pereira, 2006;Nivre, 2009). Bengoetxea and Gojenola (2010) discuss non-projective dependencies in Basque and show that the pseudo-projective transformation of (Nivre and Nilsson, 2005) improves accuracy for dependency parsing of Basque. Moreover, they show that in combination with other transformations, it improves the utility of these other ones, too.

Estimation and Smoothing: Coping with Lexical Sparsity
Morphological word form variation augments the vocabulary size and thus worsens the problem of lexical data sparseness. Words occurring with mediumfrequency receive less reliable estimates, and the number of rare/unknown words is increased. One way to cope with the one of both aspects of this problem is through clustering, that is, providing an abstract representation over word forms that reflects their shared morphological and morphosyntactic aspects. This was done, for instance, in previous work on parsing German. Versley and Rehbein (2009) cluster words according to linear context features. These clusters include valency information added to verbs and morphological features such as case and number added to pre-terminal nodes. The clusters are then integrated as features in a discriminative parsing model to cope with unknown words. Their discriminative model thus obtains state-of-the-art results on parsing German.
Several contribution address similar challenges. For constituency-based generative parsers, the simple technique of replacing word forms with more abstract symbols is investigated by (Seddah et al., 2010;Candito and Seddah, 2010). For French, replacing each word form by its predicted part-ofspeech and lemma pair results in a slight performance improvement (Seddah et al., 2010). When words are clustered, even according to a very local linear-context similarity measure, measured over a large raw corpus, and when word clusters are used in place of word forms, the gain in performance is even higher (Candito and Seddah, 2010). In both cases, the technique provides more reliable estimates for in-vocabulary words, since a given lemma or cluster appear more frequently. It also increases the known vocabulary. For instance, if a plural form is unseen in the training set but the corresponding singular form is known, then in a setting of using lemmas in terminal symbols, both forms are known.
For dependency parsing, Marton et al. (2010) investigates the use of morphological features that involve some semantic abstraction over Arabic forms. The use of undiacritized lemmas is shown to improve performance. Attia et al. (2010) specifically address the handling of unknown words in the latentvariable parsing model. Here again, the technique that is investigated is to project unknown words to more general symbols using morphological clues. A study on three languages, English, French and Arabic, shows that this method helps in all cases, but that the greatest improvement is obtained for Arabic, which has the richest morphology among three.

Where we're at
It is clear from the present overview that we are yet to obtain a complete understanding concerning which models effectively parse MRLs, how to annotate treebanks for MRLs and, importantly, how to evaluate parsing performance across types of languages and treebanks. These foundational issues are crucial for deriving more conclusive recommendations as to the kind of models and morphological features that can lead to advancing the state-of-theart for parsing MRLs. One way to target such an understanding would be to encourage the investigation of particular tasks, individually or in the context of shared tasks, that are tailored to treat those problematic aspects of MRLs that we surveyed here.
So far, constituency-based parsers have been assessed based on their performance on the PTB (and to some extent, across German treebanks (Kübler, 2008)) whereas comparison across languages was rendered opaque due to data set differences and representation idiosyncrasies. It would be interesting to investigate such a cross-linguistic comparison of parsers in the context of a shared task on constituency-based statistical parsing, in additional to dependency-based ones as reported in (Nivre et al., 2007a). Standardizing data sets for a large number of languages with different characteristics, would require us, as a community, to aim for constituency-representation guidelines that can represent the shared aspects of structures in different languages, while at the same time allowing differences between them to be reflected in the model. Furthermore, it would be a good idea to introduce parsing tasks, for either constituent-based or dependency-based setups, which consider raw text as input, rather than morphologically segmented and analyzed text. Addressing the parsing problem while facing the morphological disambiguation challenge in its full-blown complexity would be illuminating and educating for at least two reasons: firstly, it would give us a better idea of what is the state-of-the-art for parsing MRLs in realistic scenarios. Secondly, it might lead to profound insights about the potentially successful ways to use morphology inside a parser, which may differ from the insights concerning the use of morphology in the less realistic parsing scenarios, where gold morphological information is given.
Finally, to be able to perceive where we stand with respect to parsing MRLs and how models fare against one another across languages, it would be crucial to arrive at evaluation metrics that capture information that is shared among the different representations, for instance, functional information concerning predicate-argument relations. Using the different kinds of measures in the context of crossframework tasks will help us understand the utility of the different evaluation metrics that have been proposed and to arrive at a clearer picture of what it is that we wish to compare, and how we can faithfully do so across models, languages and treebanks.

Conclusion
This paper presents the synthesis of 11 contributions to the first workshop on statistical parsing for morphologically rich languages. We have shown that architectural, representational, and estimation issues associated with parsing MRLs are found to be challenging across languages and parsing frameworks. The use of morphological information in the non gold-tagged input scenario is found to cause substantial differences in parsing performance, and in the kind of morphological features that lead to performance improvements.
Whether or not morphological features help parsing also depends on the kind of model in which they are embedded, and the different ways they are treated within. Furthermore, sound statistical estimation methods for morphologically rich, complex lexica, turn out to be crucial for obtaining good parsing accuracy when using general-purpose models and algorithms. In the future we hope to gain better understanding of the common pitfalls in, and novel solutions for, parsing morphologically ambiguous input, and to arrive at principled guidelines for selecting the model and features to include when parsing different kinds of languages. Such insights may be gained, among other things, in the context of more morphologically-aware shared parsing tasks.


extfieldsofstudy:
Mathematics
Computer Science

text:
Numerically Representing A Stochastic Process Algebra

The syntactic nature and compositionality characteristic of stochastic process algebras make models to be easily understood by human beings, but not convenient for machines as well as people to directly carry out mathematical analysis and stochastic simulation. This paper presents a numerical representation schema for the stochastic process algebra PEPA, which can provide a platform to directly and conveniently employ a variety of computational approaches to both qualitatively and quantitatively analyse the models. Moreover, these approaches developed on the basis of the schema are demonstrated and discussed. In particular, algorithms for automatically deriving the schema from a general PEPA model and simulating the model based on the derived schema to derive performance measures are presented.

Introduction
Stochastic process algebras, such as PEPA [1], TIPP [2], EMPA [3], are powerful modelling formalisms for concurrent systems which have enjoyed considerable success over the last decade. A stochastic process algebra model is constructed to approximately and abstractly represent a system whilst hiding its implementation details. Based on the model, performance properties of the dynamic behaviour of the system can be assessed, through some techniques and computational methods. This process is referred to as the performance modelling of the system, which mainly involves three levels: model construction, technical computation and performance derivation. In order to derive performance measures from large scale stochastic process algebra models, many mathematical tools and approaches have been proposed to study the models. For instance, a fluid approximation method has been proposed in [4] to avoid the state space explosion problem encountered in the analysis of large scale PEPA models.
However, the syntactic nature of stochastic process algebras makes models easily understood by human beings, but not convenient for machines/computers (as well as for human beings) to directly employ these tools and approaches. In addition, the compositionality of the formalisms allow a model to be locally defined, but the analysis of the model or the underlying continuoustime Markov chain (CTMC) carries out in the global manner since it is the whole system rather than a part of it to be usually interested and considered. The syntactical and compositional qualities of the stochastic process algebras, which are advantages in model construction, turn to be disadvantages in model analysis.

Paper contributions
In order to overcome the obstacles in the direct and convenient application of the mathematical tools, we propose a new numerical representation schema for the formulism PEPA in this paper. In this schema, labelled activities are defined to cope with the difference between actions in PEPA and transitions in the underlying CTMC, so that the correspondence between them is one-to-one. Activity matrices based on the labelled activities are defined to capture structural information about PEPA models. Moreover, transition rate functions are proposed to capture the timing information. These concepts numerically describe and represent a PEPA model, and provide a platform for conveniently and easily simulating the underlying CTMC, deriving the fluid approximation, as well as leading to an underlying Place/Transition (P/T) structure. These definitions are consistent with the original semantics of PEPA, and a PEPA model can be recovered from its numerical representation. An algorithm for automatically deriving the schema from any given PEPA model has been provided. Some characteristics of this numerical representation are revealed. For example, using numerical vector forms the exponential increase of the size of the state space with the number of components can be reduced to at most a polynomial increase. The benefits of the schema embodies the three aspects of performance modelling, which are illustrated by Figure 1. At the first level, the proposed new schema numerically describes any given PEPA model and provides a platform to directly employ a variety of approaches to analyse the model. These approaches are shown at the second level. At this level, a fluid approximation method for the quantitative analysis of PEPA is established, as well as investigated, mainly with respect to its convergence and the consistency between this method and the underlying CTMC. In addition, a P/T structure-based approach is revealed, which can be utilised to qualitatively analyse the model. At the third level, both qualitative and quantitative performance measures can be derived from the model through those approaches. A stochastic simulation algorithm for the aggregated CTMC, which is based on the numerical representation schema, is proposed to obtain general performance metrics in this paper. As for the other two approaches, related investigation and analysis were given in [5] and [6] respectively, which will be briefly introduced in the next subsection.

Related work
Our work is motivated and stimulated by the pioneering work on the numerical vector form and activity matrix in [4], which was dedicated to the fluid approximation for PEPA. The P/T structure underlying each PEPA model, as stated in Theorem 1 in this paper, reveals tight connections between stochastic process algebras and stochastic Petri nets. Based on this structure and the theories developed for Petri nets, several powerful techniques for structural analysis of PEPA were presented in [5], including a structure-based deadlock-checking method which avoids the state space explosion problem. In [7], a new operational semantics was proposed to give a compact symbolic representation of PEPA models. This semantics extends the application scope of the fluid approximation of PEPA by incorporating all the operators of the language and removing earlier assumptions on the syntactical structure of the models amenable to this analysis. Moreover, the paper [6] shows how to derive the performance metrics such as action throughput and capacity utilisaition from the fluid approximation of a PEPA model.

Paper organisation
The remainder of this paper is structured as follows: Section 2 gives a brief introduction to the PEPA formulism; In Section 3, 4 and 5, we respectively present the three combinators of the numerical schema, i.e. the numerical vector form, labelled activity and activity matrix, as well as the transition rate function. Computational approaches for performance derivation that are developed on the basis of the schema are demonstrated in Section 6. We finally conclude the paper in Section 7.
2 Introduction to PEPA PEPA (Performance Evaluation Process Algebra) [1], developed by Hillston in the 1990s, is a high-level model specification language for low-level stochastic models, and describes a system as an interaction of the components which engage in activities. In contrast to classical process algebras, activities are assumed to have a duration which is a random variable governed by an exponential distribution. Thus each activity in PEPA is a pair (α, r) where α is the action type and r is the activity rate. The language has a small number of combinators, for which we provide a brief introduction below; the structured operational semantics can be found in [1]. The grammar is as follows: where S denotes a sequential component and P denotes a model component which executes in parallel. C stands for a constant which denotes either a sequential component or a model component as introduced by a definition. C S stands for constants which denote sequential components. The effect of this syntactic separation between these types of constants is to constrain legal PEPA components to be cooperations of sequential processes.
Prefix: The prefix component (α, r).S has a designated first activity (α, r), which has action type α and a duration which satisfies exponential distribution with parameter r, and subsequently behaves as S.
Choice: The component S + T represents a system which may behave either as S or as T . The activities of both S and T are enabled. Since each has an associated rate there is a race condition between them and the first to complete is selected. This gives rise to an implicit probabilistic choice between actions dependent of the relative values of their rates.
Hiding: Hiding provides type abstraction, but note that the duration of the activity is unaffected. In P/L all activities whose action types are in L appear as the "private" type τ .
Cooperation:P L Q denotes cooperation between P and Q over action types in the cooperation set L. The cooperands are forced to synchronise on action types in L while they can proceed independently and concurrently with other enabled activities (individual activities). The rate of the synchronised or shared activity is determined by the slower cooperation (see [1] for details). We write P Q as an abbreviation for P L Q when L = ∅ and P [N ] is used to represent N copies of P in a parallel, i.e. P [3] = P P P .
Constant: The meaning of a constant is given by a defining equation such as A def = P . This allows infinite behaviour over finite states to be defined via mutually recursive definitions.
On the basis of the operational semantic rules (please refer to [1] for details), a PEPA model may be regarded as a labelled multi-transition system C, Act, where C is the set of components, Act is the set of activities and the multi-relation (α,r) −→ is given by the rules. If a component P behaves as Q after it completes activity (α, r), then denote the transition as P (α,r) −→ Q. The memoryless property of the exponential distribution, which is satisfied by the durations of all activities, means that the stochastic process underlying the labelled transition system has the Markov property. Hence the underlying stochastic process is a CTMC. Note that in this representation the states of the system are the syntactic terms derived by the operational semantics. Once constructed the CTMC can be used to find steady-state or transient probability distributions from which quantitative performance can be derived.

Numerical Vector Form
The usual state representation in PEPA models is in terms of the syntactic forms of the model expression. When a large number of repeated components are involved in a system, the state space of the CTMC underling the model can be large. This is mainly because each copy of the same type of component is considered to be distinct, resulting in distinct Markovian states. The multiple states within the model that exhibit the same behaviour can be aggregated to reduce the size of the state space as shown by Gilmore et al. [8] using the technique based on a vector form. The CTMC is therefore constructed in terms of equivalence classes of syntactic terms. "At the heart of this technique is the use of a canonical state vector to capture the syntactic form of a model expression", as indicated in [4]. Rather than the canonical representation style, an alternative numerical vector form was proposed by Hillston in [4] for capturing the state information of models with repeated components. In the numerical vector form, there is one entry for each local derivative of each type of component in the model. The entries in the vector are the number of components currently exhibiting this local derivative, no longer syntactic terms representing the local derivative of the sequential component. Following [4], hereafter the term local derivative refers to the local state of a single sequential component. By adopting this model-aggregation technique, the number of the states of the system can be reduced to only increase (at most) polynomially with the number of instances of the components. According to Definition 1, m(C i j ) ≥ 0 for each C i j . At any time, each sequential component stays in one and only one local derivative. So the sum of m(C i ), i.e. d i j=1 m[C i j ], specifies the population of C i in the system. Notice that m(C i ) satisfies is an upper bound of the exact number of the states in terms of C i .
Notice that Therefore, it is easy to verify the following Proposition 1. Consider a system comprising n types of component, namely C 1 , C 2 , · · · , C n , with M i copies of the component of type C i in the system, where C i has d i local derivatives, for i = 1, 2, · · · , n. Then the size of the state space of the system is at most The upper bound given in Proposition 1 guarantees that the size of the state space increases at most polynomially with the number of instances of the components. Consider the following PEPA model. According to the semantics of PEPA originally defined in [1], the size of the state space of the CTMC underlying Model 1 is 2 M +N , which increases exponentially with the numbers of the users and severs in the system. According to Definition 1, the system vector m has four entries representing the instances of components in the total four local derivatives, that is Let M = N = 2, then the system equation of Model 1 determines the starting state (2, 0, 2, 0). By enabling activities or transitions, all reachable system states can be manifested, see Figure 2. The size of the state space is nine. The upper bound of the size given by Proposition 1, , is nine, coinciding with the size of the state space. The bound given in Proposition 1 is sharp and can be hit in some situations.

Labelled Activity and Activity Matrix
In the PEPA language, the transition is embodied in the syntactical definition of activities, in the context of sequential components. Since the consideration is in terms of the whole system rather than sequential components, the transition between these system states should be defined and represented. This section presents a numerical representation for the transitions between system states and demonstrates how to derive this representation from a general PEPA model. If a system vector changes into another vector after firing an activity, then the difference between these two vectors manifests the transition corresponding to this activity. Obviously, the difference is in numerical forms since all states are numerical vectors. Consider Model 1 and its transition diagram in Figure 2. Each activity in the model corresponds to a vector, called the transition vector. For example, task 1 corresponds to the transition vector l task 1 = (−1, 1, −1, 1) T . That is, the derived state vector by firing task 1 from a state, can be represented by the sum of l task 1 and the state enabling task 1 . For instance, (2, 0, 2, 0) T + l task 1 = (1, 1, 1, 1) T illustrates that s 1 = (2, 0, 2, 0) T transitions into s 2 = (1, 1, 1, 1) T after enabling task 1 .
Each activity in the model is represented by a transition vector -a column of the activity matrix, and each column expresses an activity. So the activity matrix is essentially indicating both an injection and a surjection from syntactic to numerical representation of the transition between system states. The concept of the activity matrix for PEPA was first proposed by Hillston in [4,10]. However, the original definition cannot fully reflect the representation mapping Table 1: Transition vectors form an activity matrix here. This is due to the fact of that the original definition is local-derivative-centric rather than transition centric. This results in some limitations for more general applications. For example, for some PEPA models (e.g. Model 2 in the following context), some columns of the originally defined matrix cannot be taken as transition vectors so that this definition cannot fully reflect the PEPA semantics in some circumstances. In the following, a modified definition of the activity matrix is given. The new definition is activity-or transition-centric, which brings the benefit that each transition is represented by a column of the matrix and vice versa. Figure 3: Transition diagram of Model 2 Let us consider a PEPA model, i.e. the following Model 2, in which there are multiple choices after firing some activities. In this model, firing α in the component P may lead to two possible local derivatives: P 2 and P 3 , while firing β may lead to P 1 and P 3 . In addition, firing γ may lead to P 1 , Q 1 . However, only one derivative can be chosen after each firing of an activity, according to the semantics of PEPA. But the original definition of activity matrix cannot clearly reflect this point. See the activity matrix of Model 2 given in Table 2. Moreover, the individual activity γ in this table, which can be enabled by both P 3 and Q 2 , may be confused as a shared activity.
In order to better reflect the semantics of PEPA, we modify the definition of the activity matrix in this way: if there are m possible outputs, namely {R 1 , R 2 , · · · , R m }, after firing either an individual or a shared activity l, then l is "split" into m labelled ls: l w 1 , l w 2 , · · · , l wm . Here respectively. Each l w i can only lead to a unique output R i . Here there are no new activities created, since we just attach labels to the activity to distinguish the outputs of firing this activity. The modified activity matrix clearly reflects that only one, not two or more, result can be obtained from firing l. And thus, each l w i can represent a transition vector.
For example, see the modified activity matrix of Model 2 in Table 3. In this activity matrix, the individual activity γ has different "names" for different component types, so that it is not confused with a shared activity. Another activity β, is labelled as β P 2 →P 1 and β P 2 →P 3 , to respectively reflect the corresponding two choices. In this table, the activity α is also split and attached with labels.
Before giving the modified definition of activity matrix for any general PEPA model, the pre and post sets for an activity are first defined. For convenience, throughout this paper any transition U (l,r) −→ V defined in the PEPA models may be rewritten as U 1. If a local derivative U can enable an activity l, that is U l −→ ·, then U is called a pre local derivative of l. The set of all pre local derivatives of l is denoted by pre(l), called the pre set of l.
2. If V is a local derivative obtained by firing an activity l, i.e. ·  Obviously, if l has only one pre local derivative, i.e. #pre(l) = 1, then l is an individual activity, like β in Model 2, whereafter the notation #A is defined as the cardinality of the set A, i.e. the number of elements of A. But l being individual does not imply #pre(l) = 1, see γ for instance. If l is shared, then #pre(l) > 1, for example, see #pre(α) = #{P 1 , Q 1 } = 2. For a shared activity l with pre(l) = k, there are k local derivatives that can enable this activity, each of them belonging to a distinct component type.
For an individual activity l, things are rather simple and easy: for U ∈ pre(l), l can be labelled as l U →post(U,l) [1] , l U →post(U,l) [2] , l U →post(U,l)[k U ] , where k U = #post(U, l). Varying U ∈ pre(l), there are U ∈pre(l) #post(U, l) labels needed to distinguish the possible transitions. See β P 2 →P 1 , β P 2 →P 3 , γ P 3 →P 1 , γ Q 2 →Q 1 in Model 2 for instance. Now we give the formal definition. 1. For any individual activity l, for each U ∈ pre(l), V ∈ post(U, l), label l as l U →V .
2. For a shared activity l, for each (V 1 , V 2 , · · · , V k ) ∈ post(pre(l) [1], l) × post(pre(l) [2], l) × · · · × post(pre(l)[k], l), label l as l w , where Each l U →V or l w is called a labelled activity. The set of all labelled activities is denoted by A label . For the above labelled activities l U →V and l w , their respective pre and post sets are defined as According to Definition 3, each l U →V or l w can only lead to a unique output. No new activities are created, since labels are only attached to the activity to distinguish the results after this activity is fired.
The impact of labelled activities on local derivatives can be recorded in a matrix form, as defined below. Definition 4. (Activity Matrix). For a model with N A label labelled activities and N D distinct local derivatives, the activity matrix C is an N D × N A label matrix, and the entries are defined as follows where l j is a labelled activity. The pre activity matrix C pre and post activity matrix C post are defined as otherwise. , The modified activity matrix captures all the structural information, including the information about choices and synchronisations, of a given PEPA model. From each row of the matrix, which corresponds to each local derivative, we can know which activities this local derivative can enable and after which activities are fired this local derivative can be derived. From the perspective of the columns, the number of "−1"s in a column tells whether the corresponding activity is synchronised or not. Only one "−1" means that this transition corresponds to an individual activity. The locations of "−1" and "1" indicate which local derivatives can enable the activity and what the derived local derivatives are, i.e. the pre and post local derivatives. In addition, the numbers of "−1"s and "1"s in each column are the same, because any transition in any component type corresponds to a unique pair of pre and post local derivatives. In fact, all this information is also stored in the labels of the activities. Therefore, with the transition rate functions defined in the next section to capture the timing information, a given PEPA model can be recovered from its activity matrix.
Moreover, the pre and post activity matrix indicate the local derivatives which can fire a labelled activity and the derived local derivative after firing a labelled activity respectively. The modified activity matrix equals the difference between the pre and post activity matrices, i.e. C = C Post − C Pre . Hereafter the terminology of activity matrix refers to the one in Definition 4. This definition embodies the transition or operation rule of a given PEPA model, with the exception of timing information. For a given PEPA model, each transition of the system results from the firing of an activity. Each optional result after enabling this activity corresponds to a relevant labelled activity, that is, corresponds to a column of the activity matrix. Conversely, each column of the activity matrix corresponding to a labelled activity, represents an activity and the chosen derived result after this activity is fired. So each column corresponds to a system transition. Therefore, we have the following proposition, which specifies the correspondence between system transitions and the columns of the activity matrix.
Proposition 2. Each column of the activity matrix corresponds to a system transition and each transition can be represented by a column of the activity matrix.

Transition Rate Function
The structural information of any general PEPA model is captured in the activity matrix, which is constituted by all transition vectors. However, the duration of each transition has not yet been specified. This section defines transition rate functions for transition vectors or labelled activities to capture the timing information of PEPA models.

Model 2 continued
Let us start from Model 2 again. As Table 3 shows, activity γ in Model 2 is labelled as γ P 3 →P 1 and γ Q 2 →Q 1 . For γ P 3 →P 1 , there are x[P 3 ] instances of the component type P in the local derivative P 3 in state x, each enabling the individual activity concurrently with the rate r γ . So the rate of γ P 3 →P 1 in state x is f (x, γ P 3 →P 1 ) = r γ x[P 3 ]. Similarly, the rate for γ Q 2 →Q 1 in state x is r γ x[Q 2 ]. This is consistent with the definition of apparent rate in PEPA, which states that if there are N replicated instances of a component enabling a transition (l, r), the apparent rate of the activity will be r × N .
In Model 2 activity β is labelled as β P 2 →P 1 and β P 2 →P 3 , to respectively reflect the corresponding two choices. According to the model definition, there is a flux of r β x(P 2 ) into P 1 from P 2 after firing β in state x. So the transition rate function is defined as f (x, β P 2 →P 1 ) = r β x[P 2 ]. Similarly, we can define f (x, β P 2 →P 3 ) = r β x[P 2 ]. These rate functions can be defined or interpreted in an alternative way. In state x, there are x[P 2 ] instances that can fire β. So the apparent rate of β is (r β + r β )x[P 2 ]. By the semantics of PEPA, the probabilities of choosing the outputs are r β r β +r β and r β r β +r β respectively. So the rate of the transition β P 2 →P 1 is while the rate of the transition β P 2 →P 3 is In Model 2, α is a shared activity with three local rates: r α , r α and r α . The apparent rate of α in P 1 is (r α +r α )x[P 1 ], while in Q 1 it is r α x[Q 1 ]. According to the PEPA semantics, the apparent rate of a synchronised activity is the minimum of the apparent rates of the cooperating components. So the apparent rate of α as a synchronisation activity is min{(r α + r α )x[P 1 ], r α x[Q 1 ]}. After firing α, P 1 becomes either P 2 or P 3 , with the probabilities r α r α +r α and r α r α +r α respectively. Simultaneously, Q 1 becomes Q 2 with the probability 1. So the rate function of transition (P 1 → P 2 , Q 1 → Q 2 ), represented by f (x, α (P 1 →P 2 ,Q 1 →Q 2 ) ), is The above discussion about the simple example should help the reader to understand the definition of transition rate function for general PEPA models, which is presented in the next subsection.

Definitions of transition rate function
In a PEPA model, as we have mentioned, we may rewrite any U  (5.6) The apparent rate of l in U in state x, denoted by r l (x, U ), is defined as The above definition is used to define the following transition rate function. −→ V , the transition rate function of labelled activity l U →V in state x is defined as Then the transition rate function of labelled activity l w in state x is defined as Remark 1. Definition 6 accommodates the passive or unspecified rate . If some r U →V l are , then the relevant calculation in the rate functions (5.8) and (5.9) can be made according to the inequalities and equations that define the comparison and manipulation of unspecified activity rates (see [1]). Moreover, we assume that 0 · = 0. So the terms such as "min{A , rB}" are interpreted as [11]: The definition of the transition rate function is consistent with the semantics of PEPA: The transition rate function in Definition 6 is consistent with the operational semantics of PEPA.
The proof is easy and omitted here. Since both the structural and timing information has been captured in the defined numerical representation schema, PEPA models can be therefore recovered from its representation schema. In addition, it is also easy to find that the transition rate function has the following homogenous property. This property will identify the CTMCs underlying a PEPA model to be density dependent (see Theorem 4 in the next section).

Algorithm for deriving activity matrix and transition rate functions
This subsection presents an algorithm for automatically deriving the activity matrix and transition rate functions from any PEPA model, see Algorithm 1. The lines 3-12 of Algorithm 1 deal with individual activities while lines 13 − 32 deal with shared activities. The calculation methods in this algorithm are essentially the embodiment of the definitions of labelled activity and apparent rate as well as transition rate function. So we do not give more introduction to this algorithm.

Computational approaches for PEPA
As a model being represented numerically, efficient techniques such as stochastic simulation and fluid approximation can be can be directly utilised to analyse the model. This section briefly introduces these approaches as well as technical foundations for employing them in the context of PEPA.

Place/Transition structure in PEPA models
Whilst the focus of stochastic process algebras has understandably been primarily quantitative analysis, qualitative analysis can also provide valuable insight into the behaviour of a system. In contrast, in Petri net modelling there are well-established techniques of structural analysis [12][13][14]. This subsection shows how the new representation schema helps to manifest the P/T structure underlying PEPA models, and makes it possible to readily adapt structural analysis techniques for Petri nets to PEPA. First, the relevant definitions are given below.

2.
A marking is a vector m : P → N that assigns to each place of a P/T net a nonnegative integer (number of tokens).
3. A P/T system is a pair S = N , m 0 : a net N with an initial marking m 0 .
By Definition 7, it is easy and direct to verify Theorem 1. There is a P/T system underlying any PEPA model, that is N , m 0 , where m 0 is the starting state; N = D, A label , C Pre , C Post is P/T net: where D is the set of local derivatives, A label is the labelled activity set; C Pre and C Post are the pre and post activity matrices respectively. Moreover, each state m of the PEPA model is a marking.
Based on the P/T structure underlying PEPA models and the theories developed for P/T nets, several powerful techniques and approaches for structural analysis of PEPA were established in [5]. For instance, the authors gave a method of deriving and storing the state space which avoids the problems associated with populations of components, and an approach to find invariants which can be used to qualitatively reason about systems. Moreover, a structure-based deadlock-checking algorithm was proposed, which can avoid the state space explosion problem. // Form a corresponding column of the activity matrix and the rate function 8: for all (V 1 , V 2 , · · · , V k ) ∈ K(l) do 28:

29:
A label = A label ∪ {l w } // Label l as l w

30:
// Form a column of M a and the rate function corresponding to l w

Stochastic simulation of PEPA models
By solving the global balance equations associated with the infinitesimal generator of the CTMC underlying a PEPA model, the steady-state probability distribution can be obtained, from which performance measures can be derived. According to the original definition of the PEPA language in which each instance of the same component type is considered distinctly, the size of the state space of this original CTMC may increase exponentially with the number of components. By adopting the numerical vector form to represent the system state which results in the aggregated CTMC, the size of the state space can thus be significantly reduced, as Proposition 1 shows, together with the computational complexity of deriving the performance by solving the corresponding global balance equations since, the dimension of the infinitesimal generator matrix is the square of the size of the state space.
Unless otherwise stated, hereafter the CTMC underlying a PEPA model refers to the aggregated CTMC, and the state of a model or a system is considered in the sense of aggregation. If the size of the state space is too large, it is not feasible to calculate the steady-state distribution and thus to get a performance measure R, which is usually expressed as R = s∈S ρ(s)π(s) where ρ and π defined on the state space S are the reward function and the steady-state probability distribution respectively. An alternative widely-used way to obtained performance is stochastic simulation.
As discussed previously, a transition between states, namely from x to x + l, is represented by a transition vector l corresponding to the labelled activity l (for convenience, hereafter each pair of transition vectors and corresponding labelled activities shares the same notation). The rate of the transition l in state x is specified by the transition rate function f (x, l). That is, x (l,f (x,l)) −→ x + l. Given a starting state x 0 , the transition chain corresponding to a firing sequence l 0 , l 1 , · · · , l, · · · is The above sequence can be considered as one path or realisation of a simulation of the aggregated CTMC, if the enabled activity at each state is chosen stochastically, i.e. is chosen through the approach of sampling. After a long time, the steady-state of the system is assumed to be achieved. Hence the average performance R = s∈S ρ(s)π(s) can be calculated. As one benefit of our numerical representation schema, it provides a good platform for directly and conveniently simulating the CTMC for PEPA, see Algorithm 2. In Algorithm 2, the states of a PEPA model are represented as numerical vector forms, and the rates between those states are specified by the transition rate functions which only depend on the transition type (i.e. labelled activity) and the current state. In this algorithm, the generated time τ in each iteration can be regarded as having been drawn from an exponential distribution with the mean 1 f (x) (see Example 2.3 in [15], page 38). That is, Line 9 in Algorithm 2 is in fact expressing: "generate τ from an exponential distribution with the mean 1 f (x) ". Line 10 determines which transition will be chosen, and consequently determines the next state that the system will transition into. Therefore, this algorithm is essentially to simulate the CTMC underlying a PEPA model. The choices for stopping the algorithm include a given large time, or the absolute or relative error of two continued iterations being small enough (since the output performance converges compute the transition rate function f (x, l j ), j = 1, 2, · · · , m 7: generate uniform random numbers r 1 , r 2 on [0, 1] 9: compute τ = −(1/f (x)) ln r 1 10: x = x + l µ // Update state vector of system 15: end while 16: Output performance: PerMeasure t as time goes to infinity as the following Theorem 3 states). Now we prove the convergence of the performance calculated using the algorithm. We need the following theorem. Moreover, for any bounded function ρ : S → R, we have where E[ρ(X)] = s∈S ρ(s)π(s).
Here is our conclusion (we assume the CTMCs underlying PEPA models to be irreducible and positive recurrent): Theorem 3. The performance measure calculated according to Algorithm 2 converges as time goes to infinity, that is, lim t→∞ Proof. Assume that n − 1 iterations have been finished and the time has accumulated to t n−1 . Suppose the current one is the n-th iteration and τ is the generated time in this iteration. After the n-th iteration is finished, the accumulated time will be updated to t n = t n−1 + τ . During the τ time interval, the simulated CTMC stays in the state x, that is, Therefore, after this n-th iteration, PerMeasure will be accumulated to = tn 0 ρ(X z )dz and PerMeasure t n = 1 t n tn 0 ρ(X z )dz.
According to Theorem 2, 1 t n tn 0 ρ(X z )dz tends to E[ρ(X)] as t n tends to infinity. So the performance obtained through Algorithm 2 converges to E[ρ(X)] as the simulation time goes to infinity.
Performance metrics, such as activity throughput of an activity and capacity utilisation of a local derivative that are discussed in [6], can be derived through this algorithm by choosing appropriate reward functions.

Fluid approximation of PEPA models
The weakness of the simulation method is its high computational cost, which makes it not suitable for real-time performance monitoring or prediction. Recently, a novel approach to get performance measures from PEPA models has been proposed in [4] and subsequently expanded in [7] and [17], making a continuous state space approximation as a set of ordinary differential equations (ODEs). In this section, we present a mapping semantics for this approaches, which is based on the numerical representation schema. In addition, a theoretical justification of this approach, mainly in terms of its consistency with the CTMCs, will be discussed.
In our representation schema, the transition rate f (x, l) reflects the intensity of the transition from state x to state x + l. The state space is inherently discrete with the entries within the numerical vector form always being non-negative integers and always being incremented or decremented in steps of one. As pointed out in [4], when the numbers of components are large these steps are relatively small and we can approximate the behaviour by considering the movement between states to be continuous, rather than occurring in discontinuous jumps. In fact, let us consider the evolution of the numerical state vector. Denote the state at time t by x(t). In a short time ∆t, the change to the vector x(t) will be x(·, t + ∆t) − x(·, t) = ∆t l∈A label lf (x(·, t), l).
Dividing by ∆t and taking the limit, ∆t → 0, we obtain a set of ODEs: lf (x, l). (6.12) Once the activity matrix and the transition rate functions are generated, the ODEs are immediately available. All of them can be obtained automatically by Algorithm 1.
For an arbitrary CTMC, the evolution of probabilities distributed on each state can be described using linear ODEs (see [18], page 52). For example, for the aggregated CTMC underlying a PEPA model, the corresponding differential equations are dπ dt = Q T π, (6.13) where each entry of π(t) represents the probability of the system being in each state at time t, and Q is an infinitesimal generator matrix corresponding to the CTMC. Clearly, the dimension of the coefficient matrix Q is the square of the size of the state space, which increases with the number of components.
The scale of (6.13), i.e. the number of the ODEs, depends on the size of the state space, so it suffers from the state sapce explosion problem. In contrast, the ODEs (6.12) reflect the evolution of the population of the components in each local derivative, so the scale is only determined by the number of local derivatives and is unaffected by the size of the state space. Therefore, it avoids the explosion problem. But the price paid is that the ODEs (6.12) are generally nonlinear due to synchronisations, whereas (6.13) is linear.
This paper emphasises the consistency between the fluid approximation and the aggregated CTMC. Obviously, the CTMC depends on the starting state of the given PEPA model. By altering the population of components presented in the model, which can be done by varying the initial states, we may get a sequence of aggregated CTMCs. Moreover, the homogenous property that the transition rate function satisfies, indicated in Proposition 4, identifies the aggregated CTMC to be density dependent.
Definition 8. ( [19]). A family of CTMCs {X n } n is called density dependent if and only if there exists a continuous function f (x, l), x ∈ R d , l ∈ Z d , such that the infinitesimal generators of X n are given by: q (n) x,x+l = nf (x/n, l), l = 0, where q (n) x,x+l denotes an entry of the infinitesimal generator of X n , x a numerical state vector and l a transition vector.
This allows us to immediately conclude the following conclusion: Theorem 4. ( [7,17]) Let {X n } be a sequence of aggregated CTMCs generated from a given PEPA model (by scaling the initial state), then {X n } is density dependent.
Since both ODEs and density dependent CTMCs can be derived from the same PEPA model through the same activity matrix and transition rate functions, it is natural to believe some kind of consistency between them. In fact, according to Kurtz's theorem [20], the complete solution of some ODEs can be the limit of a sequence of Markov chains. Such consistency in the context of PEPA has been previously illustrated for a particular PEPA model in [21], and subsequently generalised to general models in [7] and [17]. The result presented below is extracted from [17], in which the convergence is in the sense of almost surely rather than probabilistically as in [21] and [7].
Theorem 5. ( [17]) Let x(t) be the solution of the ODEs (6.12) derived from a given PEPA model with initial condition x 0 , and let {X n (t)} be the density dependent CTMCs with X n (0) = nx 0 . Then for any t > 0, lim n→∞ sup u≤t X n (u)/n − x(u) = 0 a.s. (6.14) This theorem justifies the fluid approximation by manifesting the consistency between this approach and the corresponding CTMCs for a general PEPA model. Furthermore, if there is no synchronisation contained in the model then the derived ODEs (6.12) becomes linear, and (6.13) and (6.12) coincide except for a constant factor. Moreover, the fundamental results on the fluid approximation of PEPA models such as the existence, uniqueness, boundedness and nonnegativeness of the ODEs' solution, as well as the solution's asymptotic behaviour, have been obtained. In particular, the convergence of the ODEs' solution as time tends to infinity, has been proved under a condition, which is revealed to relate to some famous constants of Markov chains such as the spectral gap and the Log-Sobolev constant. For more details about these stories, please refer to [22]. As for performance derivation via this approach, please see [6].

Conclusions
In this paper we have demonstrated a schema, which bridges the syntactic and numerical representation, as well as the local definition and global analysis for a PEPA model. Computational approaches and associated algorithms developed based on the schema have been presented, which can help to relieve the state space explosion problem for large scale models. For other stochastic process algebras, similar numerical representation schema can be established and expected to benefit relevant performance modelling.