### Rootedness, connectedness and unique parenthood

Rootedness - there is exactly one word W for which the following two statements are both true:

• W is the source of at least one dependency
• W is not the target of any dependency

Connectedness - every word is either the source or target of some dependency

Unique parenthood - every word which is the target of some dependency, is the target of just the one dependency

### Rootedness, connectedness and unique parenthood are all independent

Rooted + connected + unique parent

```John thinks that Mary rocks
(thinks,John)
(thinks,that)
(that,rocks)
(rocks,Mary)
```

Rooted + connected + non-unique parent

```John thinks that Mary rocks
(thinks,John)
(thinks,that)
(that,rocks)
(rocks,Mary)
(thinks,rocks)
```

Rooted + non-connected + unique parent

```John thinks that Mary rocks
(thinks,John)
(thinks,rocks)
(rocks,Mary)
```

Rooted + non-connected + non-unique parent

```John thinks that Mary rocks
(thinks,John)
(thinks,rocks)
(rocks,Mary)
(thinks,Mary)
```

Non-rooted + connected + unique parent

```John thinks that Mary rocks
(thinks,John)
(that,rocks)
(rocks,Mary)
```

Non-rooted + connected + non-unique parent

```John thinks that Mary rocks
(thinks,John)
(that,Mary)
(rocks,Mary)
```

Non-rooted + non-connected + unique parent

```John thinks that Mary rocks
(thinks,John)
(rocks,Mary)
```

Non-rooted + non-connected + non-unique parent

```John thinks that Mary rocks
(thinks,John)
(rocks,Mary)
(thinks,Mary)
```

### Acyclicity

If there is a sequence of dependencies from word W1 to word W2, then there is no sequence of dependencies from W2 to W1.

### Rooted + unique parent + cyclic is inconsistent

Rooted + connected + unique parent + acyclic

```John thinks that Mary rocks
(thinks,John)
(thinks,that)
(that,rocks)
(rocks,Mary)
```

Rooted + connected + unique parent + cyclic

```John thinks that Mary rocks
XXX
```

Rooted + connected + non-unique parent + acyclic

```John thinks that Mary rocks
(thinks,John)
(thinks,that)
(that,rocks)
(rocks,Mary)
(thinks,Mary)
```

Rooted + connected + non-unique parent + cyclic

```John thinks that Mary rocks
(thinks,John)
(thinks,that)
(that,rocks)
(rocks,Mary)
(Mary,that)
```

Rooted + non-connected + unique parent + acyclic

```John thinks that Mary rocks
(thinks,John)
(thinks,rocks)
(rocks,Mary)
```

Rooted + non-connected + unique parent + cyclic

```John thinks that Mary rocks
XXX
```

Rooted + non-connected + non-unique parent + acyclic

```John thinks that Mary rocks
(thinks,John)
(thinks,rocks)
(rocks,Mary)
(thinks,Mary)
```

Rooted + non-connected + non-unique parent + cyclic

```John thinks that Mary rocks
(thinks,John)
(thinks,rocks)
(rocks,Mary)
(Mary,rocks)
```

Non-rooted + connected + unique parent + acyclic

```John thinks that Mary rocks
(thinks,John)
(that,rocks)
(rocks,Mary)
```

Non-rooted + connected + unique parent + cyclic

```John thinks that Mary rocks
(thinks,John)
(that,rocks)
(rocks,Mary)
(Mary,that)
```

Non-rooted + connected + non-unique parent + acyclic

```John thinks that Mary rocks
(thinks,John)
(that,rocks)
(rocks,Mary)
(that,Mary)
```

Non-rooted + connected + non-unique parent + cyclic

```John thinks that Mary rocks
(thinks,John)
(that,rocks)
(rocks,Mary)
(Mary,that)
```

Non-rooted + non-connected + unique parent + acyclic

```John thinks that Mary rocks
(thinks,John)
(rocks,Mary)
```

Non-rooted + non-connected + unique parent + cyclic

```John thinks that Mary rocks
(that,rocks)
(rocks,Mary)
(Mary,that)
```

Non-rooted + non-connected + non-unique parent + acyclic

```John thinks that Mary rocks
(that,rocks)
(Mary,rocks)
```

Non-rooted + non-connected + non-unique parent + cyclic

```John thinks that Mary rocks
(that,rocks)
(Mary,rocks)
(rocks,Mary)
```

i.e.

• rooted, unique parent implies acyclic
• rooted, cyclic implies non-unique parent
• unique parent, cyclic implies non-rooted

In other words, a "tree" can be defined as a rooted, unique parent dependency structure - acyclicity is implied.

### Others

Functionality - for each word W and each dependency label T, there is no more than one dependency from W labelled with T

-- MarkMcConville - 14 Aug 2008

Edit | Attach | Print version |  | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r3 - 18 Aug 2008 - 23:40:21 - MarkMcConville

Copyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback