We introduce a novel transition system for discontinuous constituency parsing. Instead of storing subtrees in a stack i.e. a data structure with linear-time sequential access  the proposed system uses a set of parsing items, with constant-time random access . This change makes it possible to construct any discontinuous constituency tree in exactly 4 n  2 transitions for a sentence of length n , whereas existing systems need a quadratic number of transitions to derive some structures. At each parsing step, the parser considers every item in the set to be combined with a focus item and to construct a new constituent in a bottom-up fashion. The parsing strategy is based on the assumption that most syntactic structures can be parsed incrementally and that the set  the memory of the parser remains reasonably small on average. Moreover, we introduce a dynamic oracle for the new transition system, and present the first experiments in discontinuous constituency parsing using a dynamic oracle. Our parser obtains state-of-the-art results on three English and German discontinuous treebanks. Discontinuous constituency trees extend standard constituency trees by allowing crossing branches to represent long distance dependencies, such as the wh -extraction in Figure 1. Discontinuous constituency trees can be seen as derivations of Linear Context-Free Rewriting Systems (LCFRS, Vijay-Shanker et al., 1987), a class of formal grammars more expressive than context-free grammars, which makes them much harder to parse. In particular, exact CKY-style LCFRS parsing has an O ( n 3 f ) time complexity where f is the fan-out of the grammar (Kallmeyer, 2010). A natural alternative to grammar-based chart parsing is transition-based parsing, that usually relies on fast approximate decoding methods such as greedy search or beam search. Transition-based discontinuous parsers construct discontinuous constituents by reordering terminals with the SWAP action (Versley, 2014a,b; Maier, 2015; Maier and Lichte, 2016; Stanojevic and Garrido Alhama, 2017), or by using a split stack and the GAP action to combine two non-adjacent constituents (Coavoux and Crabbe, 2017a; Coavoux et al., 2019). These proposals represent the memory of the parser (i.e. the tree fragments being constructed) with data structures with linear-time sequential access (either a stack, or a stack coupled with a double-ended queue). As a result, these systems need to perform at least n actions to construct a new constituent from two subtrees separated by n intervening subtrees. Our proposal aims at avoiding this cost when constructing discontinuous constituents. We design a novel transition system in which a discontinuous constituent is constructed in a single step, without the use of reordering actions such as SWAP . The main innovation is that the memory of the parser is not represented by a stack, Initial configuration (  , null , 0 ,  ) : 0 Goal configuration (  , { 0 , 1 , . . . , n  1 } , n, C ) : 4 n  2 Structural actions Input Output Precondition SHIFT ( S, s f , i, C ) : j  ( S  { s f } , { i } , i + 1 , C ) : j + 1 i < n , j is even COMBINEs ( S, s f , i, C ) : j  ( S  s, s f  s, i, C ) : j + 1 s  S , j is even Labelling actions LABEL-X ( S, s f , i, C ) : j  ( S, s f , i, C  { ( X, s f ) } ) : j + 1 j is odd NO-LABEL ( S, s f , i, C ) : j  ( S, s f , i, C ) : j + 1 i (cid:54) = n or S (cid:54) =  , j is odd Table 1: Set-based transition system description. as is usual in shift-reduce systems, but by an unordered random-access set. The parser considers every constituent in the current memory to construct a new constituent in a bottom-up fashion, and thus instantly models interactions between parsing items that are not adjacent. As such, we describe a left-to-right parsing model that deviates from the standard stack-buffer setting, a legacy from pushdown automata and classical parsing algorithms for context-free grammars. Our contributions are summarized as follows:  We design a novel transition system for discontinuous constituency parsing, based on a memory represented by a set of items, and that derives any tree in exactly 4 n  2 steps for a sentence of length n ;  we introduce the first dynamic oracle for discontinuous constituency parsing;  we present an empirical evaluation of the transition system and dynamic oracle on two German and one English discontinuous treebanks. The code of our parser is released as an open-source project at https://gitlab.com/ mcoavoux/discoparset . System overview We propose to represent the memory of the parser by (i) a set of parsing items and (ii) a single focus item . Figure 2 (lower part) illustrates a configuration in our system. The parser constructs a tree with two main actions: shift the next token to make it the new focus item ( SHIFT ), or combine any item in the set with the focus item to make a new constituent bottom-up ( COMBINE action). Since the memory is not an ordered data structure, the parser considers equally every pending parsing item, and thus constructs a discontinuous constituent in a single step, thereby making it able to construct any discontinuous tree in O ( n ) transitions. The use of an unordered random-access data structure to represent the memory of the parser also leads to a major change for the scoring system (Figure 2). Stack-based systems use a local view of a parsing configuration to extract features and score actions: features only rely on the few topmost elements on the stack and buffer. The score of each transition depends on the totality of this local view. In constrast, we consider equally every item in the set, and therefore rely on a global Even action Set ( S ) Focus ( s f ) Buffer Odd action {} none So what 's a parent to do ? view of the memory (Section 3). However, we score each possible combinations independently: the score of a single combination only depends on the two constituents that are combined, regardless of the rest of the set. Definitions We first define an instantiated (dis-continuous) constituent ( X, s ) as a nonterminal label X associated with a set of token indexes s . We call min( s ) the left-index of c and max( s ) its right-index . For example in Figure 1, the two VPs are respectively represented by (VP, { 1, 6 } ) and (VP, { 1, 5, 6 } ), and they have the same right index (6) and left index (1). A parsing configuration is a quadruple ( S, s f , i, C ) where:  S is a set of sets of indexes and represents the memory of the parser;  s f is a set of indexes called the focus item , and satisfies max( s f ) = i  1 ;  i is the index of the next token in the buffer;  C is a set of instantiated constituents. Each new constituent is constructed bottom-up from the focus item and another item in the set S . Transition set Our proposed transition system is based on the following types of actions:  SHIFT constructs a singleton containing the next token in the buffer and assigns it as the new focus item. The former focus item is added to S . COMBINEs computes the union between the focus item s f and another item s from the set S , to form the new focus item s  s f . LABEL-X instantiates a new constituent ( X, s f ) whose yield is the set of indexes in the focus item s f . NO-LABEL has no effect; its semantics is that the current focus set is not a constituent. Following Cross and Huang (2016b), transitions are divided into structural actions ( SHIFT , COMBINEs ) and labelling actions ( LABEL-X, NOLABEL ). The parser may only perform a structural action on an even step and a labelling action on an odd step. For our system, this distinction has the crucial advantage of keeping the number of possible actions low at each parsing step, compared to a system that would perform a COMBINE action and a labelling action in a single REDUCEs -X action. 1 Table 1 presents each action as a deduction rule associated with preconditions. In Table 2, we describe how to derive the tree from Figure 1. 2.2 Oracles Training a transition-based parser requires an oracle, i.e. a function that determines what the best action is in a specific parsing configuration to serve as a training signal. We first describe a static oracle that provides a canonical derivation for a given gold tree. We then introduce a dynamic oracle that determines what the best action is in any parsing configuration. 1 In such a case, we would need to score | S |  | N | + 1 actions, where N is the set of nonterminals, instead of | S | +1 actions for our system. Our transition system exhibits a fair amount of spurious ambiguity , the ambiguity exhibited by the existence of many possible derivations for a single tree. Indeed, since we use an unordered memory, an n -ary constituent (and more generally a tree) can be constructed by many different transition sequences. For example, the set { 0, 1, 2 } might be constructed by combining  { 0 } and { 1 } first, and the result with { 2 } ; or  { 1 } and { 2 } first, and the result with { 0 } ; or  { 0 } and { 2 } first, and the result with { 1 } . Following Cohen et al. (2012), we eliminate spurious ambiguity by selecting a canonical derivation for a gold tree. In particular, we design the static oracle (i) to apply COMBINE as soon as possible in order to minimize the size of the memory (ii) to combine preferably with the most recent set in the memory when several combinations are possible. The first choice is motivated by properties of our system: when the memory is smaller, there are fewer choices, therefore decisions are simpler and less expensive to score. Parsers are usually trained to predict the gold sequence of actions, using a static oracle. The limitation of this method is that the parser only sees a tiny portion of the search space at train time and only trains on gold input (i.e. configurations obtained after performing gold actions). At test time, it is in a different situation due to error propagation: it must predict what the best actions are in configurations from which the gold tree is probably no longer reachable. To alleviate this limitation, Goldberg and Nivre (2012) proposed to train a parser with a dynamic oracle , an oracle that is defined for any parsing configuration and outputs the set of best actions to perform. In contrast, a static oracle is deterministic and is only defined for gold configurations. Dynamic oracles were proposed for a wide range of dependency parsing transition systems (Goldberg and Nivre, 2013; Gomez-Rodrguez et al., 2014; Gomez-Rodrguez and Fernandez-Gonzalez, 2015), and later adapted to constituency parsing (Coavoux and Crabbe, 2016; Cross and Huang, 2016b; Fernandez-Gonzalez and Gomez-Rodrguez, 2018b,a). In the remainder of this section, we introduce a dynamic oracle for our proposed transition system. It can be seen as an extension of the oracle of Cross and Huang (2016b) to the case of discontinuous parsing. Preliminary definitions For a parsing configuration c , the relation c (cid:96) c (cid:48) holds iff c (cid:48) can be derived from c by a single transition. We note (cid:96)  the reflexive and transitive closure of (cid:96) . An instantiated constituent ( X, s ) is reachable from a configuration c = ( S, s f , i, C ) iff there exists c (cid:48) = ( S (cid:48) , s (cid:48) f , i (cid:48) , C (cid:48) ) such that ( X, s )  C (cid:48) and c (cid:96)  c (cid:48) . Similarly, a set of constituents t (possibly a full discontinuous constituency tree) is reachable iff there exists a configuration c (cid:48) = ( S (cid:48) , s (cid:48) f , i (cid:48) , C (cid:48) ) such that t  C (cid:48) and c (cid:96)  c (cid:48) . We note reach ( c, t  ) the set of constituents that are (i) in the gold set of constituents t (ii) reachable from c . We define a total order (cid:22) on index sets: s (cid:22) s (cid:48)    max( s ) < max( s (cid:48) ) , or max( s ) = max( s (cid:48) ) and s  s (cid:48) . This order naturally extends to the constituents of a tree: ( X, s ) (cid:22) ( X (cid:48) , s (cid:48) ) iff s (cid:22) s (cid:48) . If ( X, s ) precedes ( X (cid:48) , s (cid:48) ) , then ( X, s ) must be constructed before ( X (cid:48) , s (cid:48) ) . Indeed, since the right-index of the focus item is non-decreasing during a derivation (as per the transition definitions), constituents are constructed in the order of their right-index (first condition). Moreover, since the algorithm is bottom-up, a constituent must be constructed before its parent (second condition). From a configuration c = ( S, s f , i, C ) at an odd step, a constituent ( X, s g ) /  C is reachable iff both the following properties hold: 1. max( s f )  max( s g ) ; 2.  s  S  { s f } , ( s  s g ) or ( s  s g =  ) . Condition 1 is necessary because the parser can only construct new constituents ( X, s ) such that s f (cid:22) s . Condition 2 makes sure that s g can be constructed from a union of elements from S  { s f } , potentially augmented with terminals from the bufffer: { i, i + 1 , . . . , max( s g ) } . Following Cross and Huang (2016b), we define next ( c, t  ) as the smallest reachable gold constituent from a configuration c . Formally: next ( c, t  ) = argmin (cid:22) reach ( c, t  ) . Oracle algorithm We first define the oracle o for the odd step of a configuration c = ( S, s f , i, C ) : o odd ( c, t  ) = (cid:26) { LABEL-X } if  ( X, s f )  t  , { NO-LABEL } otherwise. For even steps, assuming next ( c, t  ) = ( X, s g ) , we define the oracle as follows: o even ( c, t  ) =   { COMBs | ( s f  s )  s g } if max( s g ) = max( s f ) , { COMBs | ( s f  s )  s g }  { SH } if max( s g ) > max( s f ) . We provide a proof of the correctness of the oracle in Appendix A. 3 A Neural Network based on Constituent Boundaries We first present an encoder that computes context-aware representations of tokens (Section 3.1). We then discuss how to compute the representation of a set of tokens (Section 3.2). We describe the action scorer (Section 3.3), the POS tagging component (Section 3.4), and the objective function (Sec-tion 3.5). As in recent proposals in dependency and constituency parsing (Cross and Huang, 2016a; Kiperwasser and Goldberg, 2016), our scoring system is based on a sentence transducer that constructs a context-aware representation for each token. Given a sequence of tokens x n 1 = ( x 1 , . . . , x n ) , we first run a single-layer character bi-LSTM encoder c to obtain a character-aware embedding c ( x i ) for each token. We represent a token x i as the concatenation of a standard word embedding e ( x i ) and the character-aware embedding: w x i = [ c ( x i ); e ( x i )] . Then, we run a 2-layer bi-LSTM transducer over the sequence of token representations: ( h (1)1 , . . . , h (1) n ) = bi-LSTM ( w x 1 , . . . , w x n ) , ( h (2)1 , . . . , h (2) n ) = bi-LSTM ( h (1)1 , . . . , h (1) n ) . The parser uses the context-aware token representations h (2) i to construct vector representations of sets or constituents. An open issue in neural discontinuous parsing is the representation of discontinuous constituents. In projective constituency parsing, it has become standard to use the boundaries of constituents (Hall et al., 2014; Crabbe, 2015; Durrett and Klein, 2015), an approach that proved very successful with bi-LSTM token representations (Cross and Huang, 2016b; Stern et al., 2017). Although constituent boundary features improves discontinuous parsing (Coavoux and Crabbe, 2017a), relying only on the left-index and the right-index of a constituent has the limitation of ignoring gaps inside a constituent. For example, since the two VPs in Figure 1 have the same right-index and left-index, they would have the same representations. It may also happen that constituents with identical right-index and left-index do not have the same labels. We represent a (possibly partial) constituent with the yield s , by computing 4 indexes from s : (min( s ) , max( s ) , min( s ) , max( s )) . The set s represents the gap in s , i.e. the tokens between min( s ) and max( s ) that are not in the yield of s : s = { i | min( s ) < i < max( s ) and i /  s } . For an index set that does not contain a gap, we have s =  . To handle this case, we use a parameter vector h nil , randomly initialized and learned jointly with the network, to embed max(  ) = min(  ) = nil . For example, the constituents (VP, { 1, 6 } ) and (VP, { 1, 5, 6 } ) will be respectively vectorized as: r ( { 1 , 6 } ) = [ h (2)1 ; h (2)6 ; h (2)2 ; h (2)5 ] , r ( { 1 , 5 , 6 } ) = [ h (2)1 ; h (2)6 ; h (2)2 ; h (2)4 ] . This representation method makes sure that two distinct index sets have distinct representations, as long as they have at most one gap each. This property no longer holds if one index sets has more than one gap. For each type of action structural or labelling we use a feedforward network with two hidden layers. Structural actions At structural steps, for a configuration c = ( S, s f , i, C ) , we need to compute the score of | S | COMBINE actions and possibly a SHIFT action. In our approach, the score of a combines action only depends on s and s f and is independent of the rest of the configuration (i.e. other items in the set). We first construct input matrix M as follows: M = (cid:18) r ( s 1 )    r ( s n ) r ( { i } ) r ( s f )    r ( s f ) r ( s f ) (cid:19) . Each of the first n columns of matrix M represents the input for a COMBINE action, whereas the last column is the input for the SHIFT action. We then compute the score of each structural action: P ( | c ) = Softmax ( FF s ( M )) , where FF s is a feedforward network with two hidden layers, a tanh activation and a single output unit. In other words, it outputs a single scalar for each column vector of matrix M . This part of the network can be seen as an attention mechanism, where the focus item is the query, and the context is formed by the items in the set and the first element in the buffer. Labelling actions We compute the probabilities of labelling actions as follows: P ( | s f ) = Softmax ( FF l ( r ( s f ))) , where FF l is a feedforward network with two hidden layers activated with the tanh function, and | N | + 1 output units, where N is the set of nonterminals. Following Coavoux and Crabbe (2017b), we use the first layer of the bi-LSTM transducer as input to a Part-of-Speech (POS) tagger that is learned jointly with the parser. For a sentence x n 1 , we compute the probability of a sequence of POS tags t n 1 = ( t 1 , . . . , t n ) as follows: P ( t n 1 | x n 1 ) = n (cid:89) i =1 Softmax ( W ( t )  h (1) i + b ( t ) ) t i , where W ( t ) and b ( t ) are parameters. In the static oracle setting, for a single sentence x n 1 , we optimize the sum of the log-likelihood of gold POS-tags t n 1 and the log-likelihood of gold parsing actions a n 1 : L = L t + L p , L t =  n (cid:88) i =1 log P ( t i | x n 1 ) , L p =  4 n  2 (cid:88) i =1 log P ( a i | a i  1 1 , x n 1 ) . We optimize this objective by alternating a stochastic step for the tagging objective and a stochastic step for the parsing objective, as is standard in multitask learning (Caruana, 1997). In the dynamic oracle setting, instead of optimizing the likelihood of the gold actions (assum-ing all previous actions were gold), we optimize the likelihood of the best actions, as computed by the dynamic oracle, from a configuration sampled from the space of all possible configurations. In practice, before each epoch, we sample each sentence from the training corpus with probability p and we use the current (non-averaged) parameters to parse the sentence and generate a sequence of configurations. Instead of selecting the highest-scoring action at each parsing step, as in a normal inference step, we sample an action using the softmax distribution computed by the parser, as done by Ballesteros et al. (2016). Then, we use the dynamic oracle to calculate the best action from each of these configurations. In case there are several best actions, we deterministically choose a single action by favoring a COMBINE over a SHIFT (to bias the model towards a small mem-ory), and to COMBINE with the item with the highest right-index (to avoid spurious discontinuity in partial constituents). We train the parser on these sequences of potentially non-gold configuration-action pairs. We carried out experiments to assess the adequacy of our system and the effect of training with the dynamic oracle. We present the three discontinuous constituency treebanks that we used (Sec-tion 4.1), our experimental protocol (Section 4.2), then we discuss the results (Section 4.3) and the efficiency of the parser (Section 4.4). We perform experiments on three discontinuous constituency corpora. The discontinuous Penn Treebank was introduced by Evang and Kallmeyer (2011) who converted the long distance dependencies encoded by indexed traces in the original Penn treebank (Marcus et al., 1993) to discontinuous constituents. We used the standard split (sec-tions 2-21 for training, 22 for development and 23 for test). The Tiger corpus (Brants et al., 2004) and the Negra corpus (Skut et al., 1997) are both German treebanks natively annotated with discontinuous constituents. We used the SPMRL split for the Tiger corpus (Seddah et al., 2013), and the split of Dubey and Keller (2003) for the Negra corpus. We implemented our parser in Python using the Pytorch library (Paszke et al., 2017). We trained each model with the ASGD algorithm (Polyak and Juditsky, 1992) for 100 epochs. Training a single model takes approximately a week with a GPU. We evaluate a model every 4 epochs on the validation set and select the best performing model according to the validation F-score. We refer the reader to Table 5 of Appendix B for the full list of hyperparameters. We evaluate models with the dedicated module of discodop 2 (van Cranenburgh et al., 2016). We use the standard evaluation parameters ( proper.prm ), that ignore punctuations and root symbols. We report two evaluation metrics: a standard Fscore (F) and an Fscore computed only on discontinuous constituents (Disc. F), which provides a more qualitative evaluation of the ability of the parser to recover long distance dependencies. 2 https://github.com/andreasvc/ disco-dop 4.3 Results Effect of Dynamic Oracle We present parsing results on the development sets of each corpus in Table 3. The effect of the oracle is in line with other published results in projective constituency parsing (Coavoux and Crabbe, 2016; Cross and Huang, 2016b) and dependency parsing (Goldberg and Nivre, 2012; Gomez-Rodrguez et al., 2014): the dynamic oracle improves the generalization capability of the parser. External comparisons In Table 4, we compare our parser to other transition-based parsers (Maier, 2015; Coavoux and Crabbe, 2017a; Stanojevic and Garrido Alhama, 2017; Coavoux et al., 2019), the pseudo-projective parser of Versley (2016), grammar-based chart parsers (Evang and Kallmeyer, 2011; van Cranenburgh et al., 2016; Gebhardt, 2018) and parsers based on dependency parsing (Fern  andez-Gonz  alez and Martins, 2015; Corro et al., 2017). Note that some of them only report results in a gold POS tag setting (the parser has access to gold POS tags and use them as fea-tures), a setting that is much easier than ours. Our parser matches the state of the art of Coavoux et al. (2019). This promising result shows that it is feasible to design accurate transition systems without an ordered memory. Our transition system derives a tree for a sentence of n words in exactly 4 n  2 transitions. Indeed, there must be n SHIFT actions, and n  1 COMBINE actions. Each of these 2 n  1 transitions must be followed by a single labelling action. The statistical model responsible for choosing which action to perform at each parsing step needs to score | S | + 1 actions for a structural step and | N | +1 actions for a labelling step (where N is the set of possible nonterminals). Since in the worst case, | S | contains n  1 singletons, the parser has an O ( n ( | N | + n )) time complexity. In practice, the memory of the parser S remains relatively small on average. We report in Figure 3 the distribution of the size of S across configurations when parsing the development sets of three corpora. For the German treebanks, the memory contains 7 or fewer elements for more than 99 percents of configurations. For the Penn treebank, the memory is slighlty larger, with 98 percents of configuration with 11 or fewer items. We report empirical runtimes in Table 6 of Appendix C. Our parser compares decently with other transition-based parsers, despite being written in Python. Existing transition systems for discontinuous constituency parsing rely on three main strategies for constructing discontinuous constituents: a swap-based swap-based strategy, a split-stack strategy, and the use of non-local transitions. Swap-based systems Swap-based transition systems are based on the idea that any discontinuous constituency tree can be transformed into a projective tree by reordering terminals. They reorder terminals by swapping them with a dedicated action ( SWAP ), commonly used in dependency parsing (Nivre, 2009). The first proposals in transition-based discontinuous constituency parsing used the SWAP action on top of an easy-first parser (Versley, 2014a,b). Subsequent proposals relied on a shift-reduce system (Maier, 2015; Maier and Lichte, 2016) or a shift-promote-adjoin system (Stanojevic and Garrido Alhama, 2017). The main limitation of swap-based system is that they tend to require a large number of transitions to derive certain trees. The choice of an oracle that minimizes derivation lengths has a substantially positive effect on parsing (Maier and Lichte, 2016; Stanojevic and Garrido Alhama, 2017). Split-stack systems The second parsing strategy constructs discontinuous constituents by allowing the parser to reduce pairs of items that are not adjacent in the stack. In practice, Coavoux and Crabbe (2017a) split the usual stack of shift-reduce parsers into two data structures (a stack and a double-ended queue), in order to give the parser access to two focus items: the respective tops of the stack and the dequeue, that may or may not be adjacent. A dedicated action, GAP , pushes the top of the stack onto the bottom of the queue to make the next item in the stack available for a reduction. The split stack associated with the GAP action can be interpreted as a linear-access memory: it is possible to access the i th element in the stack, but it requires i operations. Non-local transitions Non-local transitions generalize standard parsing actions to nonadjacent elements in the parsing configurations. Maier and Lichte (2016) introduced a non-local transition SKIPSHIFTi which applies SHIFT to the i th element in the buffer. Non-local transitions are also widely used in non-projective dependency parsing (Attardi, 2006; Qi and Manning, 2017; Fernandez-Gonzalez and Gomez-Rodrguez, 2018). The key difference between these systems and ours is that we use an unordered memory. As a result, the semantics of the COMBINEs action we introduce in Section 2 is independent from a specific position in the stack or the buffer. A system with an action such as SKIPSHIFTi needs to learn parameters with every possible i , and will only learn parameters with the SKIPSHIFTi actions that are required to derive the training set. In contrast, we use the same parameters to score each possible COMBINEs action. We have presented a novel transition system that dispenses with the use of a stack, i.e. a memory with linear sequential access. Instead, the memory of the parser is represented by an unordered data structure with random-access: a set. We have designed a dynamic oracle for the resulting system and shown their empirical potential with state-of-the-art results on discontinuous constituency parsing of one English and two German treebanks. Finally, we plan to adapt our system to non-projective dependency parsing and semantic graph parsing. We thank Caio Corro, Giorgio Satta, Marco Da-monte, as well as NAACL anonymous reviewers for feedback and suggestions. We gratefully acknowledge the support of Huawei Technologies.
objective abstain abstain abstain abstain objective result abstain abstain abstain abstain abstain abstain objective objective other abstain abstain abstain other other method abstain abstain method abstain abstain abstain abstain abstain method abstain method method method abstain other abstain method abstain abstain abstain abstain abstain abstain method abstain method method method method method method abstain method method abstain abstain method abstain abstain abstain abstain abstain abstain method abstain abstain method abstain abstain method abstain abstain method abstain abstain abstain abstain other abstain abstain method abstain method method method method method method abstain method other abstain abstain abstain abstain abstain abstain method abstain method method other abstain abstain method method abstain abstain abstain method abstain abstain method abstain method method abstain abstain method method method method method method abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain other other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain other other other other other other other other other other other other other other other method abstain other objective objective abstain result abstain other other