Semantic representations in the form of directed acyclic graphs (DAGs) have been introduced in recent years, and to model them, we need probabilistic models of DAGs. One model that has attracted some attention is the DAG automaton, but it has not been studied as a probabilistic model. We show that some DAG automata cannot be made into useful probabilistic models by the nearly universal strategy of assigning weights to transitions. The problem affects single-rooted, multi-rooted, and unbounded-degree variants of DAG automata, and appears to be pervasive. It does not affect planar variants, but these are problematic for other reasons. Abstract Meaning Representation (AMR; Ba-narescu et al. 2013) has prompted a flurry of interest in probabilistic models for semantic parsing. AMR annotations are directed acyclic graphs (DAGs), but most probabilistic models view them as strings (e.g. van Noord and Bos, 2017) or trees (e.g. Flanigan et al., 2016), removing their ability to represent coreferenceone of the very aspects of meaning that motivates AMR. Could we we instead use probabilistic models of DAGs? To answer this question, we must define probability distributions over sets of DAGs. For inspiration, consider probability distributions over sets of strings or trees, which can be defined by weighted finite automata (e.g. Mohri et al., 2008; May et al., 2010): a finite automaton generates a set of strings or treescalled a languageand if we assume that probabilities factor over its transitions, then any finite automaton can be weighted to define a probability distribution over this language. This assumption underlies powerful dyEqual contribution. namic programming algorithms like the Viterbi, forward-backward, and inside-outside algorithms. What is the equivalent of weighted finite automata for DAGs? There are several candidates (Chiang et al., 2013; Bjorklund et al., 2016; Gilroy et al., 2017), but one appealing contender is the DAG automaton (Quernheim and Knight, 2012) which generalises finite tree automata to DAGs explicitly for modeling semantic graphs. These DAG automata generalise an older formalism called planar DAG automata (Kamimura and Slutzki, 1981) by adding weights and removing the planarity constraint, and have attracted further study (Blum and Drewes, 2016; Drewes, 2017), in particular by Chiang et al. (2018), who generalised classic dynamic programming algorithms to DAG automata. But while Quernheim and Knight (2012) clearly intend for their weights to define probabilities, they stop short of claiming that they do, instead ending their paper with an open problem:  Investigate a reasonable probabilistic model.  We investigate probabilistic DAG automata and prove a surprising result: For some DAG automata, it is impossible to assign weights that define non-trivial probability distributions . We exhibit a very simple DAG automaton that generates an infinite language of graphs, and for which the only valid probability distribution that can be defined by weighting transitions is one in which the support is a single DAG, with all other graphs receiving a probability of zero. Our proof relies on the fact that a non-planar DAG automaton generates DAGs so prolifically that their number grows factorially in their size, rather than exponentially as in other automata. It holds for DAG automata that allow multiple roots or nodes of unbounded degree. But it breaks down when applied to the planar DAGs of Kamimura and Slutzki (1981), which are nevertheless too restrictive to model semantic graphs. Our result does not mean that it is impossible to define a probability distribution for the language that a DAG automaton generates. But it does mean that this distribution does not factor over the automaton's transitions, so crucial dynamic programming algorithms do not generalise to DAG automata that are expressive enough to model semantic graphs. We are interested in AMR graphs like the one below for Rahul bakes his cake (Figure 1, left), which represents entities and events as nodes, and relationships between them as edges. Both nodes and edges have labels, representing the type of an entity, event, or relationship. But the graphs we model will only have labels on nodes. These node-labeled graphs can simulate edge labels using a node with one incoming and one outgoing edge, as in the graph on the right of Figure 1. bake Rahul cake ARG 1 ARG 0 POSS bake Rahul cake ARG 0 ARG 1 POSS Figure 1: A graph with both node and edge labels (left) and an equivalent graph with only node labels (right). Definition 1. A node-labeled directed graph over a label set  is a tuple G = ( V, E, lab , src , tar ) where V is a finite set of nodes, E is a finite set of edges, lab : V   is a function assigning labels to nodes, src : E  V is a function assigning a source node to every edge, and tar : E  V is a function assigning a target node to every edge. A node with no incoming edges is called a root and a node with no outgoing edges is called a leaf The degree of a node is the number of edges connected to it, so the degree of v is | IN ( v )  OUT ( v ) | . A path in a directed graph from node v to node v (cid:48) is a sequence of edges ( e 1 , . . . , e n ) where src ( e 1 ) = v , tar ( e n ) = v (cid:48) and src ( e i +1 ) = tar ( e i ) for all i from 1 to n  1 . A cycle in a directed graph is any path in which the first and last nodes are the same (i.e., v = v (cid:48) ). A DAG is connected if every pair of its nodes is connected by a sequence of edges, not necessarily directed. Because DAGs do not contain cycles, they must always have at least one root and one leaf, but they can have multiple roots and multiple leaves. However, our results apply in different ways to single-rooted and multi-rooted DAG languages, so, given a label set  , we distinguish between the set of all connected DAGs with a single root, G 1 ; and those with one or more roots, G   . Finite automata generate strings by transitioning from state to state. Top-down tree automata generalise string finite automata by transitioning from a state to an ordered sequence of states, generating trees top-down from root to leaves; while bottom-up tree automata transition from an ordered sequence of states to a single state, generating trees bottom-up from leaves to root. The planar DAG automata of Kamimura and Slutzki (1981) generalise tree automata, transitioning from one ordered sequence of states to another ordered sequence of states (Section 4). Finally, the DAG automata of Quernheim and Knight (2012) transition from multisets of states to multisets of states, rather than from sequences to sequences, and this allows them to generate non-planar DAGs. We summarise the differences in Table 1 below. For the remainder of this section and the next, we will focus only on non-planar DAG automata, and when we refer to DAG automata, we mean this type. To formally define them, we need a notation for multisetssets that can contain repeated elements. A multiset is a pair ( S, m ) where S is a finite set and m : S  N is a count functionthat is, m ( x ) counts the number of times x appears in the multiset. The set of all finite multisets over S is M ( S ) . When we write multisets, we will often simply enumerate their elements. For example, { p, q, q } is the multiset containing one p and two b a b c b a a q 's, and since multisets are unordered, it can also be written { q, p, q } or { q, q, p } . We write  for a multiset containing no elements. Definition 2. A DAG automaton is a triple A = ( Q,  , T ) where Q is a finite set of states;  is a finite set of node labels; and T is a finite set of transitions of the form     where    is a node label,   M ( Q ) is the left-hand side, and   M ( Q ) is the right-hand side. Example 1. Let A = ( Q,  , T ) be a DAG automaton where Q = { p, p (cid:48) , q } ,  = { a, b, c, d, e } and the transitions in T are as follows:  a  { p } ( t 1 ) { p } b  { p, q } ( t 2 ) { p } c  { p (cid:48) } ( t 3 ) { p (cid:48) , q } d  { p (cid:48) } ( t 4 ) { p (cid:48) } e   ( t 5 ) 2.1.1 Generating Single-rooted DAGs A DAG automaton generates a graph from root to leaves. To illustrate this, we'll focus on the case where a DAG is allowed to have only a single root, and return to the multi-rooted case in Section 3.1. To generate the root, the DAG automaton can choose any transition with  on its left-hand side these transitions behave like transitions from the start state in a finite automaton on strings, and always generate roots. In our example, the only available transition is t 1 , which generates a node labeled a with a dangling outgoing edge in state p , as in Figure 2(i). The set of all such dangling edges is the frontier of a partially-generated DAG. While there are edges on the frontier, the DAG automation must choose and apply a transition whose left-hand side matches some subset of them. In our example, the automaton can choose either t 2 or t 3 , each matching the available p edge. The edges associated with the matched states are attached to a new node with new outgoing frontier edges specified by the transition, and the matched states are removed from the frontier. If our automaton chooses t 2 , it arrives at the configuration in Figure 2(ii), with a new node labeled b , new edges on the frontier labeled p and q , and the incoming p state forgotten. Once again, it must choose between t 2 and t 3 it cannot use the q state because that state can only be used by t 4 , which also requires a p (cid:48) on the frontier. So each time it applies t 2 , the choice between t 2 and t 3 repeats. If the automaton applies t 2 again and then t 3 , as it has done in Figure 2(iii), it will face a new set of choices, between t 4 and t 5 . But notice that choosing t 5 will leave the q states stranded, leaving a partially derived DAG. We consider a run of the automaton successful only when the frontier is empty, so this choice leads to a dead end. If the automaton chooses t 4 , it has an additional choice: it can combine p (cid:48) with either of the available q states. If it combines with the lowermost q , it arrives at the graph in Figure 2(iv), and it can then apply t 4 to consume the remaining q , followed by t 5 , which has  on its right-hand side. Transitions to  behave like transitions to a final state in a finite automaton, and generate leaf nodes, so we arrive at the complete graph in Figure 2(v). If the p (cid:48) state in Figure 2(iii) had instead combined with the upper q , a different DAG would result, as shown in Figure 2(vi-vii). The DAGs in Figure 2(v) and Figure 2(vii) are planar, which means they can be drawn without crossing edges. 1 But this DAG automaton can also produce non-planar DAGs like the one in Figure 3. To see that it is non-planar, we first contract each dotted edge by removing it and fusing its endpoints into a single node. This gives us the minor 1 While the graph in Figure 2(vii) is drawn with crossing b  d edges, one of these edges can be redrawn so that they do not cross. subgraph K 3 , 3 , and any graph with a K 3 , 3 minor is non-planar (Wagner, 1937). We define the language generated by a DAG automaton in terms of recognition, which asks if an input DAG could have been generated by an input automaton. We recognise a DAG by finding a run of the automaton that could have generated it. To guess a run on a DAG, we guess a state for each of its edges, and then ask whether those states simulate a valid sequence of transitions. A run of a DAG automaton A = ( Q,  , T ) on a DAG G = ( V, E, lab , src , tar ) is a mapping  : E  Q from edges of G to automaton states Q . We extend  to multisets by saying  ( { e 1 , . . . , e n } ) = {  ( e 1 ) , . . . ,  ( e n ) } , and we call a run accepting if for all v  V there is a corresponding transition  ( IN ( v )) lab ( v )   ( OUT ( v )) in T . DAG G is recognised by automaton A if there is an accepting run of A on G . Example 2. The DAGs in Figure 2(v) and 2(vii) are recognised by the automaton in Example 1. The only accepting run for each DAG is denoted by the blue edge labels. 2.2 Probability and Weighted DAG Automata Definition 3. Given a language L of DAGs, a probability distribution over L is any function p : L  R meeting two requirements: (R1) Every DAG must have a probability between 0 and 1, inclusive. Formally, we require that for all G  L , p ( G )  [0 , 1] . (R2) The probabilities of all DAGs must sum to one. Formally, we require (cid:80) G  L p ( G ) = 1 . R1 and R2 suffice to define a probability distribution, but in practice we need something stronger than R1: all DAGs must receive a non-zero weight, since in practical applications, objects with probability zero are effectively not in the language. While there are many ways to define a function that meets requirements R1' and R2, probability distributions in natural language processing are widely defined in terms of weighted automata or grammars, so we adapt a common definition of weighted grammars (Booth and Thompson, 1973) to DAG automata. Definition 5. A weighted DAG automaton is a pair ( A, w ) where A = ( Q,  , T ) is a DAG automaton and w : T  R is a function that assigns real-valued weights to the transitions of A . Since weights are functions of transitions, we will write them on transitions following the node label and a slash ( / ). For example, if p a  q is a transition and 2 is its weight, we write p a/ 2  q . Example 3. Let ( A, w ) be a weighted DAG automaton with A = ( Q,  , T ) , where Q = { p, q } ,  = { a, b, c } , and the weighted transitions of T are as follows:  a/ 0 . Definition 6. Given a weighted DAG automaton ( A, w ) and a DAGG = ( V, E, lab , src , tar ) with an accepting run  , we extend w to compute the weight of the run w (  ) by multiplying the weights of all of its transitions: w (  ) = (cid:89) v  V w (  ( IN ( v )) lab ( v )   ( OUT ( v ))) Example 4. The DAG automaton of Example 3 generates the DAG in Figure 4, shown with its only accepting run in blue and the weighted transitions that generated it in grey. The weight of the accepting run is 0 . 5  0 . 5  0 . 5  1 = 0 . 125 . Let RA ( G ) be the set of all accepting runs of a DAG G using the automaton A . We extend w to calculate the weight of a DAG G as the sum of the weights of all the runs that produce it: w ( G ) = (cid:88)   RA ( G ) w (  ) . While all weighted DAG automata assign real values to DAGs, not all weighted DAG automata define probability distributions. To do so, they must also satisfy requirements R1 and R2. Example 5. Consider the weighted automaton in Example 3. Every DAG generated by this automaton must use t (cid:48) 1 and t (cid:48) 3 exactly once, and can use t (cid:48) 2 any number of times. If we let G n be the DAG that uses t (cid:48) 2 exactly n times, then the language L defined by this automaton is (cid:83) n  NG n . Since w ( G n ) = w ( t (cid:48) 1 ) w ( t (cid:48) 2 ) n w ( t (cid:48) 3 ) and w ( t (cid:48) 1 ) , w ( t (cid:48) 2 ) and w ( t (cid:48) 3 ) are positive, w satisfies R1 and: (cid:88) G  L w ( G ) =  (cid:88) n =0 w ( G n ) =  (cid:88) n =0 w ( t (cid:48) 1 ) w ( t (cid:48) 2 ) n w ( t (cid:48) 3 ) =  (cid:88) n =0 0 . 5 n +1 = 1 Thus w also satisfies R2 and the weighted automaton in Example 3 is probabilistic. Definition 8. A probabilistic automaton ( A, w ) over language L ( A ) is probabilistic with full support if and only if w has full support of L ( A ) . For every finite automaton over strings or trees, there is a weighting of its transitions that makes it probabilistic (Booth and Thompson, 1973), and it is easy to show that it can be made probabilistic with full support. For example, string finite automata have full support if for every state the sum of weights on its outgoing transitions is 1 and each weight is greater than 0. 2 But as we will show, this is not always possible for DAG automata. We will exhibit a DAG automaton that generates factorially many DAGs for a given number of nodes, and we will show that for any nontrivial assignment of weights, this factorial growth rate causes the weight of all DAGs to sum to infinity. Theorem 1. Let A be the automaton defined in Example 1. There is no w that makes ( A , w ) probabilistic with full support over L s ( A ) . Proof. In any run of the automaton, transition t 1 is applied exactly once to generate the single root, placing a p on the frontier. This gives a choice between t 2 and t 3 . If the automaton chooses t 2 , it keeps one p on the frontier and adds a q , and must then repeat the same choice. Suppose it chooses t 2 exactly n times in succession, and then chooses t 3 . Then the frontier will contain n edges in state q and one in state p (cid:48) . The only way to consume all of the frontier states is to apply transition t 4 exactly n times, consuming a q at each step, and then apply t 5 to consume p (cid:48) and complete the derivation. Hence in any accepting run, t 1 , t 3 and t 5 are each applied once, and t 2 and t 4 are each applied n times, for some n  0 . Since transitions map uniquely to node labels, it follows that every DAG in L s ( A ) will have exactly one node each labeled a , c , and e ; and n nodes each labeled b and d . When the automaton applies t 4 for the first time, it has n choices of q states to consume, each distinguished by its unique path from the root. The second application of t 4 has n  1 choices of q , and the i th application of t 4 has n  ( i  1) choices. Therefore, there are n ! different ways to consume the q states, each producing a unique DAG. Let f ( n ) be the weight of a run where t 2 has been applied n times, and to simplify our notation, let B = w ( t 1 ) w ( t 3 ) w ( t 5 ) , and C = w ( t 2 ) w ( t 4 ) . Let c ( n ) be the number of unique runs where t 2 has been applied n times. By the above: f ( n ) = w ( t 1 ) w ( t 2 ) n w ( t 3 ) w ( t 4 ) n w ( t 5 ) = BC n c ( n ) = n ! Now we claim that any DAG in L s ( A ) has exactly one accepting run, because the mapping of 2 Assuming no epsilon transitions, in our notation for DAG automata restricted to strings this would include transitions to  , which correspond to states with a final probability of 1 (Mohri et al., 2008). node labels to transitions also uniquely determines the state of each edge in an accepting run. For example, a b node must result from a t 2 transition and a d node from a t 4 transition, and since the output states of t 2 and input states of t 4 share only a q , any edge from a b node to a d node must be labeled q in any accepting run. Now let G  L s ( A ) be a DAG with n nodes labeled b . Since G has only one accepting run, we have: w ( G ) = f ( n ) Let L n be the set of all DAGs in L s ( A ) with n nodes labeled b . Then L s ( A ) = (cid:83)  n =0 L n and: (cid:88) G  L s ( A ) w ( G ) =  (cid:88) n =0 (cid:88) G  L n w ( G ) =  (cid:88) n =0 c ( n ) f ( n ) =  (cid:88) n =0 ( n !) (cid:0) BC n (cid:1) Hence for ( A , w ) to be probabilistic with full support, R1' and R2 require us to choose B and C so that, respectively, BC n  (0 , 1] for all n and (cid:80)  n =0 n ! BC n = 1 . Note that this does not constrain the component weights of B or C to be in (0 , 1] they can be any real numbers. But since R1' requires BC n to be positive for all n , both B and C must also be positive. If either were 0, then BC n would be 0 for n > 0 ; if either were negative, then BC n would be negative for some or all values of n . Now we show that any choice of positive C causes (cid:80) G  L s ( A ) w ( G ) to diverge. Given an infinite series of the form (cid:80)  n =0 a n , the ratio test (D'Alembert, 1768) considers the ratio between adjacent terms in the limit, lim n  | a n +1 | | a n | . If this ratio is greater than 1, the series diverges; if less than 1 the series converges; if exactly 1 the test is inconclusive. In our case: lim n  | ( n + 1)! Hence (cid:80) G  L s ( A ) diverges for any choice of C , equivalently for any choice of weights. So there is no w for which ( A , w ) is probabilistic with full support over L s ( A ) . Note that any automaton recognising L s ( A ) must accept factorially many DAGs in the number of nodes. Our proof implies that there is no probabilistic DAG automaton for language L s ( A ) , since no matter how we design its transitionseach of which must be isomorphic to one in A apart from the identities of the statesthe factorial will eventually overwhelm the constant factor corresponding to C in our proof, no matter how small it is. Theorem 1 does not rule out all probabilistic variants of A . It requires R1'if we only require the weaker R1, then a solution of B=1 and C=0 makes the automaton probabilistic. But this trivial distribution is not very useful: it assigns all of its mass to the singleton language { a c e } . Theorem 1 also does not mean that it is impossible to define a probability distribution over L s ( A ) with full support. If, for every DAG G with n nodes labeled b , we let p ( G ) = 1 2 n +1 n ! , then: (cid:88) G  L s ( A ) w ( G ) =  (cid:88) n =0 1 2 n +1 n ! n ! But this distribution does not factor over transitions, so it cannot be used with the dynamic programming algorithms of Chiang et al. (2018). A natural way to define distributions using a DAG automaton is to define two conditional probabilities: one over the choice of nodes to rewrite, given a frontier; and one over the choice of transition, given the chosen nodes. The latter factors over transitions, but the former does not, so it also cannot use the algorithms of Chiang et al. (2018). 3 Theorem 1 only applies to single-rooted, nonplanar DAG automata of bounded degree. Next we ask whether it extends to other DAG automata, including those that recognise multi-rooted DAGs, DAGs of unbounded degree, and planar DAGs. What happens when we consider DAG languages that allow multiple roots? In one reasonable interpretation of AMRbank, over three quarters of the DAGs have multiple roots (Kuhlmann and Oepen, 2016), so we want a model that permits this. 4 Section 2.1.1 explained how a DAG automaton can be constrained to generate single-rooted languages, by restricting start transitions (i.e. those 3 In this model, the subproblems of a natural dynamic program depend on the set of possible frontiers, rather than subsets of nodes as in the algorithms of Chiang et al. (2018). We do not know whether this could be made efficient. 4 AMR annotations are single-rooted, but they achieve this by duplicating edges: every edge type, like ARG 0, has an inverse type, like ARG 0-O F . The number cited here assumes edges of the second type are converted to the first type by reversing their direction. with  on the left-hand side) to a single use at the start of a derivation. To generate DAGs with multiple roots, we simply allow start transitions to be applied at any time. We still require the resulting DAGs to be connected. For an automaton A , we define its multi-rooted language L m ( A ) as { G  G   | A recognises G } . Although one automaton can define both single-and multi-rooted DAG languages, these languages are incomparable. Drewes (2017) uses a construction very similar to the one in Theorem 1 to show that single-rooted languages have very expressive path languages, which he argues are too expressive for modeling semantics. 5 Since the constructions are so similar, it natural to wonder if the problem that single-rooted automata have with probabilities is related to their problem with expressivity, and whether it likewise disappears when we allow multiple roots. We now show that multi-rooted languages have the same problem with probability, because any multi-rooted language contains the single-rooted language as a sublanguage. Corollary 1. Let A be the automaton defined in Example 1. There is no w that makes ( A , w ) probabilistic with full support over L m ( A ) . Proof. By their definitions, L s ( A )  L m ( A ) , so: (cid:88) G  L m ( A ) w ( G ) = (cid:88) G  L s ( A ) w ( G ) + (cid:88) G  L m ( A ) \ L s ( A ) w ( G ) The first term is  by Theorem 1 and the second is positive by R1', so the sum diverges. Hence there is no w for which ( A , w ) is probabilistic with full support over L m ( A ) . The maximum degree of any node in any DAG recognised by a DAG automaton is bounded by the maximum number of states in any transition, because any transition     generates a node with |  | incoming edges and |  | outgoing edges. So, the families of DAG languages we have considered all have bounded degree. 5 The path language of a DAG is the set of strings that label a path from a root to a leaf, and the path language of a DAG language is the set of all such strings over all DAGs. For example, the path language of the DAG in Figure 2(v) is { abde, abbdde, abbcdde } . Berglund et al. (2017) show that path languages of multi-rooted DAG automata are regular, while those of single-rooted DAG automata characterised by a partially blind multi-counter automaton. DAG languages with unbounded degree could be useful to model phenomena like coreference in meaning representations, and they have been studied by Quernheim and Knight (2012) and Chiang et al. (2018). These families generalise and strictly contain the family of bounded-degree DAG languages, so they too, include DAG automata that cannot be made probabilistic. We introduced DAG automata as a tool for modeling the meaning of natural language, but the DAG automaton in Theorem 1 is very artificial, so it's natural to ask whether it has any real relevance to natural language. We will argue informally that this example illustrates a pervasive problem with DAG automataspecifically, we conjecture that the factorial growth we observe in Theorem 1 arises under very mild conditions that arise naturally in models of AMR. Consider object control in a sentence like I help Ruby help you and its AMR in Figure 5. help I help Ruby you ARG 1 ARG 0 ARG 2 ARG 0 ARG 2 Figure 5: The AMR for I help Ruby help you. We can extend the control structure unboundedly with additional helpers, as in I help Briony help Kim-Joy help Ruby help you, and this leads to unboundedly long repetitive graphs like the one in Figure 6. These graphs can be cut to separate the sequence of help predicates from their arguments, as illustrated by the dashed blue line. I help Briony help Kim-Joy help Ruby help you (cid:7) ARG 1 ARG 0 ARG 2 ARG 1 ARG 0 ARG 2 ARG 1 ARG 0 ARG 2 ARG 0 ARG 2 Figure 6: The AMR for I help Briony help Kim-Joy help Ruby help you shown with a cut. Let a cut be a set of edges such that removing them splits the graph into two connected subgraphs: one containing the root, and the other containing all the leaves. Any cut in a complete graph could have been the frontier of a partially-derived graph. What if the number of edges in a cutor cut-width can be unbounded, as in the language of AMR graphs that model object control? Since a DAG automaton can have only a finite number of states, there is some state that can occur unboundedly many times in a graph cut. All edges in a cut with this state can be rewired by permuting their target nodes, and the resulting graph will still be recognised by the automaton, since the rewiring would not change the multiset of states into or out of any node. If each possible rewiring results in a unique graph then the number of recognised graphs will be factorial in the number of source nodes for these edges, and the argument of Theorem 1 can be generalised to show that no weighting of any DAG automaton over the graph language makes it probabilistic with full support. For example, in the graph above, all possible rewirings of the ARG 2 edges result in a unique graph. 6 Although edge labels are not states, their translation into node labels implies that they can only be associated to a finite number of transitions, hence to a finite number of states in any corresponding DAG automaton. A full investigation of conditions under which Theorem 1 generalises is beyond the scope of this paper. Conjecture 1. Under mild conditions, if language L ( A ) of a DAG automaton A has unbounded cut-width, there is no w that makes ( A, w ) probabilistic with full support. The fundamental problem with trying to assign probabilities to non-planar DAG automata is the factorial growth in the number of DAGs with respect to the number of nodes. Does this problem occur in planar DAG automata? Planar DAG automata are similar to the DAG automata of Section 2 but with an important difference: they transition between ordered sequences of states rather than unordered multisets of states. We write these sequences in parentheses, and their order matters: ( p, q ) differs from ( q, p ) . We write (cid:15) for the empty sequence. When a planar DAG automaton generates DAGs, it keeps a strict order over the set of frontier states at all times. A transition whose left-hand side is ( p, q ) can only be applied to adjacent states p and q in the frontier, with 6 This is also a problem linguistically, since many of the rewired graphs no longer model object control. p preceding q . The matched states are replaced in the frontier by the sequence of states in the transi-tion's right-hand side, maintaining order. In the non-planar case, n applications of t 2 can generate n ! unique DAGs, but n applications of the corresponding transition t (cid:48)(cid:48) 2 in this automaton can only generate one DAG. To see this, consider the partially derived DAG on the left of Figure 7, with its frontier drawn in order from left to right. The p (cid:48) state can only combine with the q state immediately to its right, and since dead-ends are not allowed, the only possible choice is to apply t (cid:48)(cid:48) 4 twice followed by t (cid:48)(cid:48) 5 , so the DAG on the right is the only possible completion of the derivation. This automaton is probabilistic when w ( t (cid:48)(cid:48) 1 ) = w ( t (cid:48)(cid:48) 2 ) = 1 / 2 , w ( t (cid:48)(cid:48) 3 ) = w ( t (cid:48)(cid:48) 4 ) = w ( t (cid:48)(cid:48) 5 ) = 1 , and indeed the argument in Theorem 1 does not apply to planar automata since the number of applicable transitions is linear in the size of the frontier. But planar DAG automata have other problems that make them unsuitable for modeling AMR. The first problem is that there are natural language constructions that naturally produce nonplanar DAGs in AMR. For example, consider the sentence Four contestants mixed, baked and ate cake. Its AMR, shown in Figure 8, is not planar because it has a K 3 , 3 minor, and it is easy to see from this example that any coordination of three predicates sharing two arguments produces this structure. In the first release of AMR, 117 out of 12844 DAGs are non-planar. The second problem is that planar DAG au-and bake mix eat contestant 4 cake OP 1 OP 2 OP 3 ARG 0 ARG 1 ARG 0 ARG 1 ARG 0 ARG 1 QUANTITY Figure 8: An AMR for the sentence Four contestants mixed, baked and ate a cake. tomata model Type-0 string derivations by design (Kamimura and Slutzki, 1981). This seems more expressive than needed to model natural language and means that many important decision problems are undecidablefor example, emptiness, which is decidable in polynomial time for non-planar DAG automata (Chiang et al., 2018). Table 2 summarises the properties of several different variants of DAG automata. It has been argued that all of these properties are desirable for probabilistic models of meaning representations (Drewes, 2017). Since none of the variants supports all properties, this suggests that no variant of the DAG automaton is a good candidate for modeling meaning representations. We believe other formalisms may be more suitable, including several subfamilies of hyperedge replacement grammars (Drewes et al., 1997) that have recently been proposed (Bjorklund et al., 2016; Matheja et al., 2015; Gilroy et al., 2017). This work was supported in part by the EP-SRC Centre for Doctoral Training in Data Science, funded by the UK Engineering and Physical Sciences Research Council (grant EP/L016427/1) and the University of Edinburgh. We thank Esma Balkir, Nikolay Bogoychev, Shay Cohen, Marco Damonte, Federico Fancellu, Joana Ribeiro, Nathan Schneider, Milos Stanojevic, Ida Szubert, Clara Vania, and the anonymous reviewers for helpful discussion of this work and comments on previous drafts of the paper.
abstain abstain result abstain abstain abstain abstain method method method abstain abstain abstain abstain abstain abstain abstain method method abstain abstain result abstain abstain abstain abstain abstain other abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain method method abstain abstain abstain abstain abstain abstain other other method abstain method abstain abstain abstain method abstain method abstain abstain abstain abstain abstain abstain method abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method method abstain method abstain abstain other 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 abstain abstain method abstain abstain method abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain method abstain method abstain abstain abstain abstain abstain abstain other abstain abstain method 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 abstain abstain abstain other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain other other other