Constituent parsing has been studied extensively in the last decades. Chomsky-Schutzenberger parsing as an approach to constituent parsing has only been investigated theoretically, yet. It uses the decomposition of a language into a regular language, a homomorphism, and a bracket language to divide the parsing problem into simpler subproblems. We provide the first implementation of Chomsky-Sch  utzenberger parsing. It employs multiple context-free grammars and incorporates many refinements to achieve feasibility. We compare its performance to state-of-the-art grammar-based parsers. The description of the syntax of natural languages (such as Danish, English, and German) with the help of formal grammars has been studied since Chomsky (1956). With a formal grammar, computers can calculate a syntactic representation (called parse ) of a sentence in a natural language. Of the grammar classes in the Chomsky hierarchy (Chomsky, 1959), context-free grammars (short: CFGs) lack the expressive power necessary to model natural languages (Shieber, 1985) and parsing with context-sensitive grammars cannot be done efficiently (i.e. in polynomial time). This led to the introduction of a series of classes of mildly context-sensitive grammars (Joshi, 1985) that allow parsing in polynomial time but also capture an increasing amount of phenomena present in natural languages. Tree adjoining grammars (Joshi et al., 1975), linear context-free string-rewriting systems (short: LCFRSs, Vijay-Shanker et al., 1987), and multiple CFGs (short: MCFGs, Seki et al., 1991) are among those classes. Chomsky-Schutzenberger (short: CS) parsing was introduced by Hulden (2011) for CFGs and extended to MCFGs by Denkinger (2017). It uses a classical theorem by Chomsky and Schutzenberger (1963, or the generalisation by Yoshinaka et al., 2010), which states that the language L ( G ) of a CFG (or an MCFG) G can be represented by a regular language R , a homomorphism h , and a Dyck language (resp. multiple Dyck language) D such that L ( G ) = h ( R  D ) . The elements of R  D correspond to parses in G . For a sentence w , a CS parser calculates the elements of h  1 ( w )  R  D and transforms them into parses. CS parsing can be viewed as a coarse-to-fine mechanism where R corresponds to the coarse grammar and R  D to the fine grammar. The respective coarse-to-fine pipeline consists of (con-ceptually) simple operations such as h  1 or the intersection with R , which provides great flexibility. The flexibility is used to provide a fallback mechanism in case a finer stage of the pipeline rejects all proposals of a coarser stage. It also permits CS parsing in a broader setting than usual (for parsing) with minimal modification (see sec. 6). We suspected that the coarse-to-fine view on CS parsing leads to an efficient implementation. Since initial tests revealed that the original algorithm for MCFGs (Denkinger, 2017, alg. 3, recalled in sec. 2) is not feasible in practice, we explore numerous optimisations (sec. 4), one of which is the use of a context-free approximation of the multiple Dyck language D . We introduce component-wise derivations (sec. 3) to relate this context-free approximation to D . Employing the optimisations, we provide the first implementation of a CS parser. In sec. 5, we compare our parser's performance to Grammatical Framework (Angelov and Ljunglof, 2014), rparse (Kallmeyer and Maier, 2013), and disco-dop (van Cranenburgh et al., 2016). We restrict our comparison to (discontinuous) grammar-based parsers (excluding e.g. transition systems, Maier, 2015, Coavoux and Crabbe, 2017) since the principle of CS parsing requires a grammar. The sets of non-negative integers and positive integers are denoted by N and N + , respectively. We abbreviate { 1 , . . . , n } by [ n ] for each n  N . Let A and B be sets. The powerset of A and the set of (finite) strings over A are denoted by P ( A ) and A  , respectively. The set of possibly infinite sequences of elements of A is denoted by A  . A partition of A is a set P  P ( A ) whose elements (called cells ) are non-empty, pairwise disjoint, and cover A (i.e. (cid:83) p  P p = A ). For each a  A and each equivalence relation  on A , we denoted the equivalence class of a w.r.t.  by [ a ]  . The set of functions from A to B is denoted by A  B . Note that ( A  B )  ( A  B ) . The composition of two binary relations R 1 and R 2 is R 2  R 1 = { ( a, c ) |  b : ( a, b )  R 1 , ( b, c )  R 2 } . Finite state automata. We assume that the reader is familiar with finite state automata. For details, we refer to Hopcroft and Ullman (1979). A finite state automaton (short: FSA) is a tuple A = ( Q, , q i , q f , T ) where Q and  are finite sets ( states and terminals , respectively), q i , q f  Q ( initial and final state , respectively), and T  Q     Q is finite ( transitions ). We call q the source and q (cid:48) the target of a transition ( q, u, q (cid:48) ) . A run is a string  of transitions such that the target of a transition is the source of the next transition in  . The language of A is denoted by L ( A ) . Sorts. Sorts are a widespread concept in computer science: one can think of sorts as data types in a programming language. Let S be a set (of sorts ). An S -sorted set is a tuple ( , sort ) where  is a set and sort :   S . We abbreviate ( , sort ) by  and sort  1 ( s ) by  s for s  S . Now let  be an ( S   S ) -sorted set. The set of trees over  is the S -sorted set T  where (T  ) s = {  ( t 1 , . . . , t k ) | s 1 , . . . , s k  S,    ( s 1  s k ,s ) , t 1  (T  ) s 1 , . . . , t k  (T  ) s k } for each s  S . Multiple context-free grammars. A rule of a context-free grammar has the ability to concatenate the strings generated by its right-hand side non-terminals. Multiple context-free grammars extend this ability to concatenating stringtuples . This is done with the help of composition functions. Let  be a finite set. A composition function w.r.t.  is a function c that takes tuples of strings over  as arguments and returns a tuple of strings over  (i.e. there are k  N and s 1 , . . . , s k , s  N + such that c : (   ) s 1  . . .  (   ) s k  (   ) s ), and is defined by an equation c (( x 11 , . . . , x s 1 1 ) , . . . , ( x 1 k , . . . , x s k k )) = ( u 1 , . . . , u s ) where u 1 , . . . , u s are strings of x ji 's and symbols from  . We call c linear if each x ji occurs at most once in u 1    u s . We sometimes write [ u 1 , . . . , u s ] instead of c . Furthermore, setting sort ( c ) = ( s 1    s k , s ) , the composition functions w.r.t.  form a sorted set. The following example shows how linear composition functions are used in the rules of a multiple context-free grammar. Example 1. Consider G = ( N, , S, P ) where N = { S, A, B } and  = { a , b , c , d } are finite sets ( non-terminals and terminals , respectively), S  N ( initial non-terminal ) and P is a finite set ( rules ) that contains the following five objects:  1 = S  [ x 11 x 12 x 21 x 22 ]( A, B )  2 = A  [a x 11 , c x 21 ]( A )  4 = A  [ ,  ]()  3 = B  [b x 11 , d x 21 ]( B )  5 = B  [ ,  ]() . We call G a multiple context-free grammar. Consider the rule  1 . Similar to a rule of a context-free grammar,  1 rule has one left-hand side nonterminal ( S ) and zero or more right-hand side non-terminals ( A and B ). A derivation of G can be build by combining rules in P to form a tree according to their leftand right-hand side nonterminals. If a derivation starts with the initial non-terminal (here S ), then it is called complete . Hence, each complete derivation in G has the form d m,n =  1 (  m 2 (  4 ) ,  n 3 (  5 )) for some m, n  N . If we replace each rule in a derivation by its composition function, we obtain a term of composition functions which can be evaluated. We call the resulting value the yield of a derivation. A derivation d m,n has yield yd( d m,n ) = a m b n c m d n . The set of yields of all complete derivations is the language of G : L ( G ) = { a m b n c m d n | m, n  N } . (cid:3) Definition 2 (Seki et al., 1991) . A multiple context-free grammar (short: MCFG) is a tuple G = ( N, , S, P ) where N is a finite N + -sorted set ( non-terminals ),  is a finite set ( terminals ), S  N 1 ( initial non-terminal ), P is a finite ( N   N ) -sorted set of strings  of the form A  c ( B 1 , . . . , B k ) such that A, B 1 , . . . , B k  N , c is a linear composition function, and sort ( c ) = ( sort ( B 1 )    sort ( B k ) , sort ( A )) . The sort of  is ( B 1    B k , A ) . The left-hand side (short: lhs) of  is A . The fanout of  is fanout(  ) = sort ( A ) and the rank of  is rank (  ) = k . The elements of P are called rules . The set of derivations (resp. complete derivations) of G is DG = TP (resp. D c G = (TP ) S ). Let w    and d =  ( d 1 , . . . , d k )  DG with  = A  c ( B 1 , . . . , B k ) . The yield of d is yd( d ) = c (yd( d 1 ) , . . . , yd( d k )) . The set of derivations of w in G is D c G ( w ) = yd  1 ( w )  D c G . The language of A in G is L ( G, A ) = { yd( d ) | d  (TP ) A } . The language of G is L ( G ) = L ( G, S ) . Any language generated by an MCFG is called multiple context-free (short: mcf). (cid:3) A context-free grammar (short: CFG) is an MCFG where each non-terminal has sort 1. Each rule of a CFG has the form A  [ u 0 x 1 i (1) u 1    x 1 i ( n ) u n ]( B 1 , . . . , B k ) . We abbreviate this rule by A  u 0 B i (1) u 1    B i ( n ) u n . Weighted multiple context-free grammars. A weighted MCFG is obtained by assigning a weight to each rule of an (unweighted) MCFG. In this paper, the weights will be taken from a p artially o rdered c ommutative mo noid with z ero (short: POCMOZ). A POCMOZ is an algebra ( M, (cid:12) , 1 , 0 , (cid:2) ) where (cid:2) is a partial order on M ; (cid:12) is associative, commutative, decreasing (i.e. m (cid:12) m (cid:48) (cid:2) m ), and monotonous (i.e. m 1 (cid:2) m 2 implies m 1 (cid:12) m (cid:2) m 2 (cid:12) m ); 1 is neutral w.r.t. (cid:12) ; and 0 is absorbing w.r.t. (cid:12) . We call M factorisable if for each m  M \ { 1 } , there are m 1 , m 2  M \ { 1 } with m = m 1 (cid:12) m 2 . The probability algebra Pr = ([0 , 1] ,  , 1 , 0 ,  ) is a factorisable POCMOZ where r =  r   r for each r  [0 , 1) . Example 3 (continues ex. 1) . Consider the tuple ( G,  ) where  : P  Pr is a function where  (  1 ) = 1 ,  (  2 ) =  (  4 ) = 1 / 2 ,  (  3 ) = 1 / 3 , and  (  5 ) = 2 / 3 . We call ( G,  ) a weighted MCFG. The weight of the a derivation d m,n is obtained by multiplying the weights of all rule occurrences in it: wt( d m,n ) = 1 / 2 m +1  2 / 3 n +1 . (cid:3) Definition 4. A weighted MCFG (short: wMCFG) is a tuple ( G,  ) where G = ( N, , S, P ) is an MCFG ( underlying MCFG ),  : P  M \ { 0 } ( weight assignment ), and ( M, (cid:12) , 1 , 0 , (cid:2) ) is a factorisable POCMOZ. ( G,  ) inherits all objects associated with G . Let d =  ( d 1 , . . . , d k )  DG . The weight of d is wt( d ) =  (  ) (cid:12) (cid:74) ki =1 wt( d i ) . (cid:3) For the rest of this paper, we fix a wMCFG ( G,  ) with underlying MCFG G = ( N, , S, P ) and weight assignment  : P  M . Chomsky-Schutzenberger theorem. In the Chomsky-Schutzenberger theorem for CFGs (cf. sec. 1), D contains strings of brackets where each opening bracket is matched by the corresponding closing bracket. This property can be described with an equivalence relation. Let  be a set (of opening brackets) and s  be the set (of closing brackets) that contains s  for each    . We define   as the smallest equivalence relation where u  s  v   uv for each    and u, v    . The Dyck language w.r.t.  is D  = [  ]   . In the Chomsky-Schutzenberger representation for MCFGs, the brackets fulfil three functions: (i) terminal brackets (cid:74)  (cid:75)  stand for a terminal symbol  , (ii) component brackets (cid:74) (cid:96) and (cid:75) (cid:96) denote beginning and end of substrings produced by the (cid:96) -th component of a rule  , and (iii) variable brackets (cid:74) j,i and (cid:75) j,i denote beginning and end of substrings produced by variable x ji in a rule  . As for CFGs, each opening bracket must be matched by the corresponding closing bracket. Furthermore, because applying a rule of an MCFG produces multiple strings simultaneously, we need to ensure that the brackets corresponding to the same application of a rule occur simultaneously. This is described with another equivalence relation. Let P be a partition of  . Intuitively, each cell of P is a set of (opening) brackets that occur simultaneously. We define  P as the smallest equivalence relation on P (cid:0) (    )  (cid:1) where for each {  1 , . . . ,  s }  P with |{  1 , . . . ,  s }| = s , u 0 , . . . , u s , v 1 , . . . , v s  D  , and L  (    )  : (cid:8) u 0  1 v 1 s  1 u 1     s v s s  s u s (cid:9)  L  P (cid:8) u 0    u s , v 1    v s (cid:9)  L . The multiple Dyck language w.r.t. P is mD P = (cid:83) ( L | L  [ {  } ]  P ) . Note that mD P  D  . Theorem 5 provides a representation of each mcf language by a multiple Dyck language (see above), a recognisable language (to ensure local consistency), and a homomorphism (to decode the bracket sequences into terminal strings). The corresponding construction is recalled in def. 6. Theorem 5 (cf. Yoshinaka et al., 2010, thm. 3) . For every mcf language L    there are a homomorphism h : (   s  )     , a regular language R  (   s  )  , and a multiple Dyck language mD  (   s  )  such that L = h ( R  mD ) . (cid:4) Definition 6 (Denkinger, 2017, def. 3.6, 4.9, 5.15) . The multiple Dyck language w.r.t. G is mD G = mD PG where PG is the smallest set that contains the cell (cid:8) (cid:74)  (cid:9) for each    and the cells (cid:8) (cid:74) (cid:96) | (cid:96)  [ sort ( A )] (cid:9) and (cid:8) (cid:74) j,i | j  [ sort ( B i )] (cid:9) for each  = A  c ( B 1 , . . . , B k )  P and i  [ k ] . Let  G = (cid:83) p  PG p . We denote the elements of   G by closing brackets, e.g. s (cid:74)  = (cid:75)  , and let  G =  G    G . The homomorphism w.r.t. G , denoted by hom G , is the unique extension of h :  G    {  } to strings where h (  ) =  if  is of the form (cid:74)  and h (  ) =  otherwise. The automaton w.r.t. G , denoted by AG , is the FSA ( Q,  G , S 1 ,  S 1 , T ) where Q = (cid:8) A (cid:96) ,  A (cid:96) | A  N, (cid:96)  [ sort ( A )] (cid:9) and T is the smallest set such that for each rule   P of the form A  [ u 1 , 0 y 1 , 1 u 1 , 1    y 1 ,n 1 u 1 ,n 1 , . . . , u s, 0 y s, 1 u s, 1    y s,n s u s,n s ]( B 1 , . . . , B k ) where the y s are elements of X and the u s are elements of   , we have (abbreviating (cid:74)  1 (cid:75)  2    (cid:74)  k (cid:75)  k by (cid:94)  1     k ) the following transitions in T : (i) (cid:0) A (cid:96) , (cid:74) (cid:96) (cid:103) u (cid:96), 0 (cid:75) (cid:96) , s A (cid:96) (cid:1)  T for every (cid:96)  [ s ] with n (cid:96) = 0 , (ii) (cid:0) A (cid:96) , (cid:74) (cid:96) (cid:103) u (cid:96), 0 (cid:74) j,i , B ji (cid:1)  T for every (cid:96)  [ s ] where n (cid:96) (cid:54) = 0 and y (cid:96), 1 is of the form x ji , (iii) (cid:0) s B ji , (cid:75) j,i (cid:103) u (cid:96), (cid:74) j (cid:48) ,i (cid:48) , B j (cid:48) i (cid:48) (cid:1)  T for every (cid:96)  [ s ] and   [ n (cid:96)  1] where y (cid:96), is of the form x ji and y (cid:96), +1 is of the form x j (cid:48) i (cid:48) , and (iv) (cid:0) s B ji , (cid:75) j,i (cid:103) u (cid:96),n (cid:96) (cid:75) (cid:96) , s A (cid:96) (cid:1)  T for every (cid:96)  [ s ] where n (cid:96) (cid:54) = 0 and y (cid:96),n (cid:96) is of the form x ji . Example 7 (continues ex. 1) . The automaton w.r.t. G is shown in fig. 1. An illustration of the application of  PG is given in the appendix (p. 11). (cid:3) The vanilla parser. The vanilla parser (i.e. alg. 3 from Denkinger, 2017), is shown in fig. 2 (top). Similar to the parser proposed by Hulden (2011), we divide it in three essential phases: (i) FSA constructions for the intersection of hom  1 G ( w ) and RG , (ii) an extraction of (in our case multiple ) Dyck words from the intersection, and (iii) the conversion of words into derivations. Formally, the vanilla parser is the function V :    (D c G )  defined as V = MAP ( TODERIV )  FILTER (mD G )  SORT (  (cid:48) )  (  RG )  hom  1 G where hom  1 G ( w )  RG is represented by an FSA for each w    (phase (i)). (cid:48) ( u ) is the product of the weights of each occurrence of a bracket of the form (cid:74) (cid:96) or (cid:75) (cid:96) in u . These weights are fixed such that  (cid:48) (cid:0) (cid:74) 1  (cid:75) 1     (cid:74) (cid:96) (cid:75) (cid:96) ) =  (  ) for each   P with fanout (cid:96) . SORT (  (cid:48) ) brings the elements of its argument, which is a subset of  G  , in some descending order w.r.t.  (cid:48) and (cid:2) , returning a (pos-sibly infinite) sequence of elements of  G  , which we call candidates . Sequences are implemented as iterators. FILTER (mD G ) removes the candidates from its argument sequence that are not in mD G while preserving the order (cf. Denkinger, 2017, alg. 2). (Both steps, SORT (  (cid:48) ) and FILTER (mD G ) , are phase (ii).) TODERIV returns the derivation in G that corresponds to its argument (which is from the set RG  mD G ), cf. Denkinger (2017, function fromBrackets, p. 20). MAP ( TODERIV ) applies TODERIV to each candidate in its argument while preserving the order (phase (iii)). Denkinger (2017, thm. 5.22) showed that TAKE ( n )  V solves the n -best parsing problem. 1 We omit the additional restrictions that he imposed on the given wMCFG because they are only necessary to show the termination of his algorithm. 1 In the following, we will gloss over the distinction between derivations and parses. In sec. 4, we will outline modifications to the vanilla parser that make the extraction of the elements of mD G from hom  1 G ( w )  RG efficient (items 24). To facilitate this, we first decompose FILTER (mD G ) into FILTER (mD G )  FILTER (D  G ) , which is possible because D  G  mD G . Secondly, we implement FILTER (D  G )  SORT (  (cid:48) ) with a dynamic programming algorithm (cf. Hulden, 2011, alg. 1, similar to Bar-Hillel et al., 1961, sec. 8). And lastly, we replace FILTER (mD G ) by steps that exploit the well-bracketing of the elements of D  G . The elements of RG  D  G can be represented as trees over rules of G . 2 We label the edges of those trees to allow us to check if vertices that correspond to the same application of a rule of the MCFG G match. The resulting objects are called component-wise derivations . The set RG  D  G is characterised in terms a CFG G cf . Definition 8. Let   P be a rule of the form A  [ u 1 , . . . , u s ]( B 1 , . . . , B k ) , (cid:96)  [ s ] , and u (cid:96) be of the form w 0 x j (1) i (1) w 1    x j ( n ) i ( n ) w n for some w 0 , . . . , w n    . We define the rule  ( (cid:96) ) = A (cid:96)  (cid:113) (cid:96)  (cid:102) w 0 v 1 (cid:102) w 1    v n (cid:102) w n (cid:121) (cid:96)  where each v  = (cid:74) j (  ) ,i (  ) B j (  ) i (  ) (cid:75) j (  ) ,i (  ) . The context-free CS approximation of G (short: CFA ), denoted by G cf , is the CFG ( N cf ,  G , S 1 , P cf ) where N cf = { A (cid:96) | A  N, (cid:96)  [ sort ( A )] } and P cf = {  ( (cid:96) ) |   P, (cid:96)  [fanout(  )] } . (cid:3) Observation 9. D  G  RG = L ( G cf ) . (cid:4) Definition 10. Let (cid:96)  N + and t be a tree whose vertices are labelled with elements of P and whose edges are labelled with elements of N +  N + . The label at the root of t is denoted by root( t ) . The set of labels of the outgoing edges from the 2 Those trees correspond to the derivations of the guiding grammar in the coarse-to-fine parsing approach of Barth  elemy et al. (2001, sec. 3). root of t is denoted by out( t ) . A ( i, j ) -subtree of t , is a sub-graph of t consisting of all the vertices (and their edges) reachable from some target vertex of the outgoing edge from the root that is labelled with ( i, j ) . If there is a unique ( i, j ) subtree of t , then we denote it by sub ( i,j ) ( t ) . Now let root( t ) = A  [ u 1 , . . . , u s ]( B 1 , . . . , B k ) . We call t an ( (cid:96) -)component-wise derivation, short: ( (cid:96) -)cow derivation, of G if the following four requirements are met: (i) out( t ) contains exactly the pairs ( i, j ) such that x ji occurs in u (cid:96) , (ii) a unique ( i, j ) -subtree of t exists, (iii) root(sub ( i,j ) ( t )) has lhs B i , and (iv) sub ( i,j ) ( t ) is a j -cow derivation for each ( i, j )  out( t ) . We denote the set of cow derivations of G whose root's lhs is S by cowD c G . The set of (cid:96) -cow derivations whose root's label has lhs A is denoted by (cid:96) cowD AG . (cid:3) An example of a cow derivation is shown in fig. 3a. The root is the top-most vertex. Definition 11. Let  = A  c ( B 1 , . . . , B k )  P , (cid:96)  [fanout(  )] , and the (cid:96) -th component of c be u 0 x j (1) i (1) u 1    x j ( n ) i ( n ) u n with u 1 , . . . , u n    . Furthermore, for each   [ n ] , let t   j (  ) cowD B i (  ) G . By  (cid:10) ( i (  ) , j (  )) /t  |   [ n ] (cid:11) , we denote the cow derivation t such that root( t ) =  , out( t ) = { ( i (  ) , j (  )) |   [ n ] } , and for each   [ n ]: sub ( i (  ) ,j (  )) ( t ) = t  . (cid:3) Proof sketch. We define the partial function toCowD from  G  to cow derivations of G as follows: toCowD( u ) =  (cid:10) ( i (  ) , j (  )) / toCowD( v  ) |   [ n ] (cid:11) if u is of the form (cid:114) (cid:96)  (cid:102) u 0 (cid:74) j (1) ,i (1) v 1 (cid:75) j (1) ,i (1) (cid:102) u 1 . . . (cid:74) j ( n ) ,i ( n ) v n (cid:75) j ( n ) ,i ( n ) (cid:102) u n (cid:122) (cid:96)  for some rule  = A  c ( B 1 , . . . , B k ) where the (cid:96) -th component of c is u 0 x j (1) i (1) u 1    x j ( n ) i ( n ) u n with u 1 , . . . , u n    ; otherwise, toCowD( u ) is undefined. The partial function toCowD is a bijection between L ( G cf ) and cowD c G (proven in appendix A.2). (cid:4) Example 13 (continues ex. 1) . We construct G cf = ( { S 1 , A 1 , A 2 , B 1 , B 2 } ,  G , S 1 , P cf ) where P cf contains, among others, the following rules:  (1)1 = S 1  (cid:114) 1  1 (cid:113) 1  1 , 1 A 1 (cid:121) 1  1 , 1 (cid:113) 1  1 , 2 B 1 (cid:121) 1  1 , 2 (cid:113) 2  1 , 1 A 2 (cid:121) 2  1 , 1 (cid:113) 2  1 , 2 B 2 (cid:121) 2  1 , 2 (cid:122) 1  1 ,  (1)3 = B 1  (cid:114) 1  3 (cid:101) b (cid:113) 1  3 , 1 B 1 (cid:121) 1  3 , 1 (cid:122) 1  3 ,  (1)4 = A 1  (cid:74) 1  4 (cid:75) 1  4 ,  (2)4 = A 2  (cid:74) 2  4 (cid:75) 2  4 ,  (1)5 = B 1  (cid:74) 1  5 (cid:75) 1  5 , . . . . Figure 3a shows the image of the word (cid:114) 1  1 (cid:114) 1  1 , 1 (cid:113) 1  4 (cid:121) 1  4 (cid:122) 1  1 , 1 (cid:114) 1  1 , 2 (cid:113) 1  3 (cid:101) b (cid:113) 1  3 , 1 (cid:74) 1  5 (cid:75) 1  5 (cid:121) 1  3 , 1 (cid:121) 1  3 (cid:122) 1  1 , 2 (cid:114) 2  1 , 1 (cid:113) 2  4 (cid:121) 2  4 (cid:122) 2  1 , 1 (cid:114) 2  1 , 2 (cid:113) 2  5 (cid:121) 2  5 (cid:122) 2  1 , 2 (cid:122) 1  1 in L ( G cf ) under toCowD . In the following, we define a property called consistency to discern those cow derivations that correspond to derivations of the MCFG G . Definition 14. Let s  N + and t 1 , . . . , t s be cow derivations of G . We call the set { t 1 , . . . , t s } consistent if there is a rule  = A  c ( B 1 , . . . , B k )  P such that root( t 1 ) = . . . = root( t s ) =  , s = sort ( A ) , and for each i  [ k ] : the set { sub ( i,j ) ( t (cid:96) ) | (cid:96)  [ s ] , j  [ sort ( B i )]: ( i, j )  out( t (cid:96) ) } is consistent. If s = 1 , then we also call t 1 consistent . (cid:3) The cow derivation shown in fig. 3a is not consistent. If we consider the set of nodes that is reachable from the root via edges labelled with a tuple whose first component is 2 (the right dotted box), then it is easy to see that the rules at these nodes are not equal. A consistent cow derivation is shown in the appendix (fig. 6). In this section, we describe several improvements to the vanilla parser (cf. end of sec. 2). Since the definitions of AG , hom G , and mD G do not depend on the word w , we may compute appropriate representations for these objects before the beginning of the parsing process, and store them persistently. (a) A cow derivation. The dotted boxes show clusters of nodes that are reachable from the root via edges labelled with matching first components. (b) Construction of new rules for each cluster in fig. 3a. If there were any unused nonterminals in these constructed rules, they are removed and the indices of variables changed accordingly. For each cluster, all reachable nodes are clustered via the first component of the labels as in fig. 3a. (c) Construction of new rules from the clusters in fig. 3b. In the following, we briefly describe each improvement that we applied to the vanilla parser: 1. Let us call a rule  in G w -consistent if each string of terminals that occurs in (the composition function of)  is a substring of w . A rule is called useful w.r.t. w if it occurs in some complete derivation of G in which each rule is w -consistent. In the construction of the FSA for RG  hom  1 G ( w ) , we only calculate the transitions that relate to rules of G that are useful w.r.t. w . 2. The function FILTER (mD G ) is decomposed into FILTER (mD G )  FILTER (D  G ) in preparation for the next two items. 3. FILTER (D  G )  SORT (  (cid:48) ) is implemented with the algorithm EXTRACTDYCK ( G,  (cid:48) ) that uses dynamic programming to extract Dyck words from the language of the given FSA more efficiently. For this, we extend alg. 1 by Hulden (2011) to use weights such that it returns the elements in descending order w.r.t.  (cid:48) and (cid:2) (see appendix A.3, alg. 3). In our implementation, we change this al-Algorithm 1 reads off cow derivations from words of the CFA of G . gorithm even further such that items are explored in a similar fashion as in the CKY-algorithm (Kasami, 1966; Younger, 1967; Cocke and Schwartz, 1970). 4. For FILTER (mD G ) , instead of isMember (cid:48) by Denkinger (2017, p. 2830), which runs in quadratic time, we use the composition of two algorithms that run in linear time:  alg. 1, which reads a cow derivation off a given word in RG  D  G , and  an algorithm that checks a given cow derivation for consistency. (This is similar to alg. 2; but instead of derivations, we return Boolean values. The algorithm is given explicitly in sec. A.3.) 5. Algorithm 2 computes the bijection between cowD c G and D c G (see prop. 15). Analogously to def. 14, the function TOMCFGDERIV ' checks a set of cow derivations for equivalence of the root symbol and the function COLLECTCHILDREN groups the subtrees via the first component of the successor labels. It is easy to see that TOMCFGDERIV ( t ) is only defined if the cow derivation t is consistent (cf. item 4). Thus, we use TOMCFGDERIV in combination with TOCOWDERIV to replace MAP ( TODERIV )  FILTER (mD G ) . The time complexity of alg. 2 is linear in the Algorithm 2 converts a consistent element of cowD c G into a complete derivation of G . number of vertices of the given cow derivation. This number, in turn, is linear in the length of the processed candidate. The parser obtained by applying items 1 to 5 to the vanilla parser is visualised in fig. 2 (bottom). It is sound and complete. 3 The following two modifications (items 6 and 7) destroy both soundness and completeness. Item 6 allows only the best intermediate results to be processed further and limits the results to a subset of those of the vanilla parser. In item 7, we compensate this by an approximation we consider useful in practise. 6. EXTRACTDYCK is extended with an optional implementation of beam search by limiting the amount of items for certain groups of state spans to a specific number ( beam width ), cf. Collins (1999). In our implementation, we chose these groups of state spans such that they correspond to equal states in 3 A parser is complete if it (eventually) computes all complete derivations of the given word in the given grammar. A parser is called sound if all computed parses are complete derivations of the given word in the given grammar. the automaton for hom  1 G ( w ) . Moreover, we introduce a variable that limits the number of candidates that are yielded by Algorithm 3 ( candidate count ). Both variables are the meta-parameters of our parser. 7. We introduce a fallback mechanism for the case that FILTER (mD G ) has input candidates but an empty output. Usually, in that case, we would suggest there is no derivation for w in G , yet for robustness, it is preferable to output some parse. Figure 3 illustrates a strategy to construct a complete derivation from any complete cow derivation with an example. We implemented the parser with the modifications sketched in sec. 4 for  -free and simple wMCFGs, 4 but no problems should arise generalising this implementation to arbitrary wMCFGs. The implementation is available as a part of Rustomata, 5 a framework for weighted automata with storage written in the programming language Rust. We used the NeGra corpus (German newspaper articles, 20,602 sentences, 355,096 tokens; Skut et al., 1998) to compare our parser to Grammatical Framework (Angelov and Ljunglof, 2014), rparse (Kallmeyer and Maier, 2013), and discodop (van Cranenburgh et al., 2016) with respect to parse time and accuracy. 6 Our experiments were conducted on defoliated trees, i.e. we removed the leaves from each tree in the corpus. Parsing was performed on gold part-of-speech tags. We performed a variant of ten-fold cross validation (short: TFCV; cf. Mosteller and Tukey, 1968), i.e. we split the corpus into ten consecutive parts; each part becomes the validation set in one iteration while the others serve as training set. We used the first iteration to select suitable values for our meta-parameters and the remaining nine for validation. In case of Rustomata, a binarised and markovized grammar was induced with discodop (head-outward binarisation, v = 1 , h = 2 , cf. Klein and Manning, 2003) in each iteration. For all other parsers, we induced a proba-4 A wMCFG G is called  -free and simple if each composition function that occurs in the rules of G is either of the form [ u 1 , . . . , u s ] for some non-empty strings of variables u 1 , . . . , u s , or of the form [ t ] for some terminal symbol t . 5 available on https://github.com/tud-fop/ rustomata . We used commit 867a451 for evaluation. 6 The evaluation scripts are available on https:// github.com/truprecht/rustomata-eval . bilistic LCFRS with the respective default config-urations (for details, cf. the evaluation scripts). After that, we ran our parser on each sentence of the validation set and recorded the parse time and the computed 1-best parse. The computed parses were evaluated against the gold parses of the validation set w.r.t. precision, recall, and f 1 -score (according to the labelled parseval measures, cf. Black et al., 1991; Collins, 1997, we used the implementation by van Cranenburgh et al., 2016). Previous experiments with an implementation of the vanilla parser already struggled with small subsets (we used grammars extracted from 250 1500 parse trees) of the NeGra corpus. Therefore, we omit evaluation of the vanilla parser. Meta-parameters. A grid search for meta-parameters was performed on sentences of up to 20 tokens (see the appendix, tab. 2, for a detailed listing). The results suggested to set the beam width to 200 and the candidate count to 10,000. Comparison to other parsers. The experiments were performed on sentences with up to 30 tokens. We instructed rparse, Grammatical Framework (short: GF) and Rustomata (short: OP) to stop parsing each sentence after 30 seconds ( timeout ). Disco-dop did not permit passing a timeout. In the case of disco-dop's LCFRS parser (short: ddlcfrs), we limited the validation set to sentences parser precision recall f 1 -score coverage NeGra corpus, | w |  20 ddctf-dop 81 . of at most 20 tokens, since ddlcfrs frequently exceeded 30 seconds of parse time for longer sentences in preliminary tests. Disco-dop's coarse-to-fine data-oriented parser (short: ddctf-dop) and disco-dop's coarse-to-fine LCFRS parser (short: ddctf-lcfrs) rarely exceeded 30 seconds of parse time in preliminary tests and we let them run on sentences of up to 30 tokens without the timeout. Figure 4a shows the parse times for each sentence length and parser. The parsers ddctf-dop, ddctf-lcfrs, GF, and OP perform similar for sentences of up to 20 tokens. The parse times of rparse and ddlcfrs grow rapidly after 10 and 16 tokens, respectively. Rparse even exceeds the timeout for more than half of the test sentences that are longer than 15 tokens. For sentences with up to 30 tokens, the parse times of ddctf-dop, ddctf-lcfrs and OP seem to remain almost constant. Table 1 shows the accuracy (i.e. precision, recall, and f 1 -score) and the coverage (i.e. the percentage of sentences that could be parsed) for each parser on the validation set. We report these scores to assert a correct implementation of our parser and to compare the different approximation strategies (and our fallback mechanism) implemented in the parsers. The low coverage of rparse stems from the frequent occurrences of timeouts. They also depress the recall for rparse. For sentences with at most 20 tokens, ddlcfrs, ddctf-lcfrs and OP perform very similar. These three parsers are outperformed by ddctf-dop in all aspects. For sentences of up to 30 tokens, the scores of all tested parsers drop similarly. However, ddctf-dop's scores drop the least amount. We repeated a part of the experiments with the Lassy corpus (Lassy Small, various kinds of written Dutch, 65,200 sentences, 975,055 tokens; van Noord et al., 2013). Since it is considerably larger than the NeGra corpus, we limited the experiments to one iteration of TFCV, and we only investigate OP, ddctf-lcfrs, and ddctf-dop. The results are shown in fig. 4b (parse time) and at the bottom of tab. 1 (accuracy). Figure 4b shows the difference of ddctf-lcfrs, ddctf-dop and OP in terms of parse times (which is not discernible in fig. 4a). This plot shows that OP maintains very small parse times  even for large copora  compared to the state-of-the-art parser disco-dop. All in all, our parser performs comparable to state-of-the-art MCFG parsers (GF, rparse, ddlcfrs, ddctf-lcfrs) and, using the NeGra corpus, it shows excellent results in parse time and good results in accuracy. Moreover, our parser can deal with any  -free and simple MCFG provided by an external tool, making it more flexible than discodop and rparse. However, we are not able to compete with ddctf-dop in terms of accuracy, since discontinuous data-oriented parsing is a more accurate formalism (van Cranenburgh and Bod, 2013). We see potential to improve the fallback mechanism explained in sec. 4. For now, we only considered reporting the first cow derivation. By introducing some degree of consistency of cow derivations, we could select a cow derivation that is closer to a derivation of G . Since recognisable languages are closed under inverse homomorphisms, we can use any recognisable language as input for hom  1 G (cf. fig. 2) without changing the rest of the pipeline. This is useful when the input of the parsing task is ambiguous, as in lattice-based parsing (e.g. Goldberg and Tsarfaty, 2008). Moreover, since weighted recognisable languages are closed under inverse homomorphisms and scalar product, we can even use a weighted recognisable language as input for hom  1 G , as in the setting of Rastogi et al. (2016). We thank our colleague Kilian Gebhardt as well as the anonymous reviewers for their insightful comments on drafts of this paper.
abstain abstain abstain objective abstain method abstain abstain abstain abstain abstain abstain other abstain abstain abstain abstain abstain abstain abstain abstain abstain objective method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain other abstain abstain abstain abstain abstain other abstain abstain abstain abstain other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain method abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain other abstain abstain abstain method abstain abstain other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method method abstain abstain abstain abstain other method other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain other abstain other abstain abstain method abstain abstain abstain method other method abstain other abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain method abstain abstain method abstain abstain abstain abstain method abstain method method abstain method objective abstain abstain other method other abstain method method method method abstain abstain abstain abstain abstain abstain abstain method abstain result abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain objective abstain abstain abstain abstain abstain result method abstain abstain abstain method abstain method other