Héctor Martínez
email: hector.martinez-alonso@inria.fr

Anders Johannsen
email: anders@johannsen.com

Barbara Plank
email: b.plank@rug.nl

Supersense tagging with inter-annotator disagreement

Linguistic annotation underlies many successful approaches in Natural Language Processing (NLP), where the annotated corpora are used for training and evaluating supervised learners. The consistency of annotation limits the performance of supervised models, and thus a lot of effort is put into obtaining high-agreement annotated datasets. Recent research has shown that annotation disagreement is not random noise, but carries a systematic signal that can be used for improving the supervised learner. However, prior work was limited in scope, focusing only on part-ofspeech tagging in a single language. In this paper we broaden the experiments to a semantic task (supersense tagging) using multiple languages. In particular, we analyse how systematic disagreement is for sense annotation, and we present a preliminary study of whether patterns of disagreements transfer across languages.

Introduction

Consistent annotations are important if we wish to train reliable models and perform conclusive evaluation of NLP. The standard practice in annotation efforts is to define annotation guidelines that aim to minimize annotator disagreement. However, in practical annotation projects, perfect agreement is virtually unattainable. Moreover, not all of disagreement should be considered noise because some of it is systematic [START_REF] Krippendorff | Agreement and information in the reliability of coding[END_REF].

The work of Plank et al. (2014a) shows that the regularity of some disagreement in part-of-speech (POS) annotation can be used to obtain more robust POS taggers. They adjust the training loss of each example according to its possible varia-tion in agreement, providing smaller losses when a classifier training decision makes a misclassification that matches with human disagreement. For example, the loss for predicting a particle instead of an adverb is smaller than the loss for predicting a noun instead of an adverb, because the particle/adverb confusion is fairly common among annotators (Sec. 3).

In this article, we apply the method of Plank et al. (2014a) to a semantic sequence-prediction task, namely supersense tagging (SST). SST is considered a more difficult task than POS tagging, because the semantic classes are more dependent on world knowledge, and the number of supersenses is higher than the number of POS labels. We experiment with different methods to calculate the label-wise agreement (Sec. 3.1), and apply these methods to datasets in two languages, namely English and Danish (Sec. 3.2). Moreover, we also perform cross-linguistic experiments to assess how much of the annotation variation in one language can be applied to another.

Variation in supersense annotation

This section provides examples of reasonable disagreement in supersense annotation. We have extracted examples of disagreement from English supersense data [START_REF] Johannsen | More or less supervised supersense tagging of Twitter[END_REF], which we later use in our experiments. Tables 1 provides example nominal and verbal expressions, and how they have been annotated by three annotators, namely A 1 -A 3 . In the first noun example, human being is seen by most as a two-token multiword of N.PERSON, but A 2 emphasizes the biological reading of human being when assigning senses, thus interpreting it as N.ANIMAL.

For lightning, we observe a disagreement across two types (N.EVENT and N.PHENOMENON) that arguably have a hyponymy relation between them (phenomena being a type of event), and we consider this disagreement a consequence of the overlap in the supersense inventory. The word thunder shows the same disagreement.

A 1 A 2 A 3 human B-N.PERSON B-N.ANIMAL B-N.PERSON being B-N.PERSON I-N.ANIMAL I-N.PERSON
In the case of October Iron Range eNews, there is disagreement on the extension of the spans of the multiword. This difference also makes A 3 provide a different semantic type to each of the three multiwords.

Even without span-size disagreements and with a slightly smaller inventory, supersense annotation for verbs is harder than for nouns. For instance, run is the main verb of "He's gonna run out of money", and even though run is prototypically V.MOTION, the three senses provided in Table 1 reflect the meaning of "run out of ". In the second example, the word stop has full disagreement, and it even has two supersenses that seem contradictory, namely V.MOTION and V.STATIVE. This disagreement is a result of the overlap between possible annotations for stop.

The case of rewind seems more surprising, but it comes from the sentence "Rewind the 1st time I gave you a bar of chocolate", where rewind is used to mean remember. Both A 2 and A 3 have chosen V.COGNITION to give account for the metaphorical meaning of the verb, while A 1 has given the prototypical, literal sense of rewind.

Method

Our approach is based on the confusion-matrix cost-sensitive learning described in Plank et al. (2014a). We use a soft notion of correctness, so that the cost of making a prediction y depends not only on whether the correct gold label y is recovered, but also on how often annotators clashed when deciding between between y and y . The idea is to give the learner more leeway to make mistakes as long as these mistakes are the same as those made by human annotators. The learning algorithm is parameterized with a cost matrix C, where the C i,j is the cost of predicting j when i is the true label.

To obtain the costs, we first calculate the disagreement matrix D for each doubly-annotated dataset. An entry D i,j contains the probability of two annotators providing a conflicting annotation with labels i and j. High-probability entries indicate low agreement. The cost matrix is then

C i,j = 1 -D i,j .
In our experiments we use a structured perceptron with cost-sensitive updates as the learner.

Factorizations

While disagreement for POS is straightforward, disagreement on supersense labels can be estimated in various ways, because supersense tags contain span, POS and sense information. Supersense tags are similar to named entity tags, but using semantic types from WordNet's lexicographer files. A tag for a content word is of the form {B,I}-{POS}.{SEMANTIC-TYPE}.

Data

We use supersense data from two languages, Danish and English. For Danish, we use the Sem-Dax corpus [START_REF] Sandford Pedersen | The semdax corpus-sense annotations with scalable sense inventories[END_REF], a collection of supersense-annotated documents of different domains. 1 For English, we use SemCor [START_REF] Miller | Using a semantic concordance for sense identification[END_REF]

Doubly-annotated data

Experiments

We perform two kinds of experiments: monolingual and cross-language. For the monolingual experiments we use each of the four possible factorizations (Sec. 3.1) to train SST models with different costs on a single language. We evaluate each system against the most-frequent sense baseline (MFS), and against a regular structured perceptron without cost-sensitive training (BASELINE). The cross-language experiments assess whether some of the disagreement information captured by the factorizations can be used cross-lingually. To study this hypothesis, we run factorized systems using S DA (Sec. 3.1) on English, and viceversa.

Adapting S DA to English requires projecting back to the canonical supersense inventory, namely removing the adjective supersenses and treating, e.g., all cases of NOUN.VEHICLE as N.ARTIFACT, before calculating factorizations for the different confusion matrices.

Applying the complementary process-using English disagreement information to train costsensitive models for Danish SST-is more involved. We have converted all the Danish data to the English SST inventory to be able to use the coarser inventory of S EN by projecting the extended senses to their original sense. 4: F 1 scores for English and Danish supersense tagging, with language-wise macro-average.

an effect on the most frequent sense baseline, because the test data is effectively relabeled.

Results

Table 4 shows the performance of our system compared to the MFS baseline and the non-regularized baseline that does not use factorizations. Note that our baseline structured perceptron already beats the though MFS baseline. We mark results in bold when another system beats the BASELINE. Some factorizations are more favorable for certain datasets. For instance, all factorizations improve the performance on Ritter-eval, but only WHO-LETAGS aids on Ritter-dev. Over all in-language data sets, WHOLETAGS beats the macro-averaged baseline for English. However, the most reliable factorization overall is JUSTSENSE, which beats BASELINE for English and Danish.

For Danish-JUSTSENSE we observe that the adjective supersenses improve (A.MENTAL goes from 0.00 to 16.53 for a support of 15 instances, and A.SOCIAL goes from 48.87 to 56.75 for a support of 169 instances in the training data), but also other senses with much higher support improve, regardless of POS, like N.PERSON (from 49.72 to 52.66 for 951 instances) or V.COMMUNICATION (from 49.66 to 50.31 for 364 instances).

With regard to our cross-lingual investigation, only the direction of using Danish disagreement on English proves promising. Table 5 shows the results of using S DA when training and testing on English. While JUSTSENSE still helps defeat BASELINE, using NOPOS yields better re-sults in this setup, indicating that coarser information might be the easiest to transfer across languages. Indeed, we find that N.COMMUNICATION goes from 60.63 to 66.60 and V.COMMUNICATION goes from 71.34 to 72.05.

Unfortunately, we have not found the improvements across factorizations to be statistically significant using bootstrap test and p < 0.05. Some of the differences in performance for the two languages can spawn from the differences in size of the doubly-annotated sample. In fact, the amount of data in S DA is much larger than S EN (200 newswire sentences vs. 40 tweets).

The results indicate that there is supporting evidence that the systematicity of annotator disagreement in supersense annotation can be used for cost-sensitive training, in particular using the JUSTSENSE factorization. Notice that the improvements in Plank et al. (2014a) for tagging reach a maximum of 4 accuracy points over the regular baseline. It would be unrealistic to expect improvements of such a magnitude for SST instead of POS tagging, in particular when evaluating with label-wise micro-averaged F1 instead of accuracy.

Related Work

Statistical NLP has been aware of the importance of annotator bias for NLP models [START_REF] Yarowsky | Evaluating sense disambiguation across diverse parameter spaces[END_REF]. Ratnaparkhi and others (1996) already mentioned that annotator identity was a predictive feature for maximum-entropy POS tagging, thereby including annotator bias as a feature. Reidsma and op den Akker ( 2008) aim at finding ways to integrate subjective and consensual annotation in ensemble classifiers, while more recent studies [START_REF] Jurgens | Embracing ambiguity: A comparison of annotation methodologies for crowdsourcing word sense labels[END_REF][START_REF] Aroyo | Measuring crowd truth for medical relation extraction[END_REF][START_REF] Plank | Linguistically debatable or just plain wrong? In ACL[END_REF]Lopez de Lacalle and Agirre, 2015;Martínez Alonso et al., 2015a;Martínez Alonso et al., 2015c;[START_REF] Plank | Do dependency parsing metrics correlate with human judgments?[END_REF] have treated inter-annotator disagreement as potentially informative for NLP. Other research efforts advocate for models of annotator behavior [START_REF] Passonneau | Word sense annotation of polysemous words by multiple annotators[END_REF][START_REF] Rebecca | The benefits of a model of annotation[END_REF][START_REF] Cohn | Modelling annotator bias with multi-task Gaussian processes: An application to machine translation quality estimation[END_REF].

Conclusions

We presented an application of cost-sensitive learning (Plank et al., 2014a) to supersense tagging. Prior work only focused on syntactic tasks and single languages. We evaluate different factorizations of label disagreement, run monolingual experiment on languages, and attempted a crosslingual regularization experiment.

We identify a consistent factorization (JUST-SENSE) that beats the baseline in both monolingual scenarios and in the cross-lingual scenario of using Danish annotation disagreement to train an English SST model.

We believe that capturing semantic disagreement is even more adequate for cross-lingual studies as semantics is more abstract and should better carry over to other languages. However, our investigation is only preliminary, and we would like to test the approach on further semantic tasks for which doubly-annotated data is available.

  Function words receive the "other" tag O. Some examples of valid supersense tags are B-NOUN.PERSON, I-NOUN.PERSON or B-VERB.PERCEPTION. We abbreviate the POS block to its initial. To account for the various kinds of information captured by the supersense tags, we use four different factorizations, i.e., four different ways of factoring costs into the model training. Each factorization determines when two tags are considered different in terms of applying a different loss during cost-sensitive training. 1. WHOLETAGS: disagreement over whole tags. That is, all count as disagreement if any of their parts are different, e.g., B-N.PERSON = I-N.PERSON 2. JUSTSENSE: disagreement over the supersense, ignoring the BI prefix. That is, e.g., B-N.PERSON = I-N.PERSON, but B-N.COGNITION = B-V.COGNITION 3. NOPOS: Only the {SEMANTIC-TYPE} block is compared, disregarding the {B,I}{POS} prefix, e.g., I-N.COGNITION = B-V.COGNITION 4. BIOPREFIX: Only the {B,I} prefix is compared, e.g., B-N.PERSON = B-V.COGNITION

Table 1 :

 1 Disagreement examples. The table shows two multi-word sequences and four single words.

	The labels COMMUNICATION, PHENOMENON,
	and POSSESSION are abbreviated.

Table 2 :

 2 and the Twitter data presented in[START_REF] Johannsen | More or less supervised supersense tagging of Twitter[END_REF], RITTER-dev, RITTER-eval, and LOWLANDS. The two first Twitter data sets adds an additional layer of annotation to the corpus first introduced in[START_REF] Ritter | Named entity recognition in tweets: an experimental study[END_REF]. Table2provides an overview of all the individual data sets used for our supersense tagging experiments. Supersense tagging data sets, the first two are training data sets.

	lang data set	sentences tokens
	EN	SEMCOR	20132 434.7k
	DA NEWSWIRE-train	400	7k
	EN	RITTER-dev	118	2.2k
	EN	RITTER-eval	118	2.3k
	EN	LOWLANDS	200	3k
	DA NEWSWIRE	200	3.5k
	DA BLOG	100	1.6k
	DA CHAT	200	2.9k
	DA FORUM	200	4.1k
	DA MAGAZINE	200	3.9k
	DA PARLIAMENT	200	6.2k
	Tag inventory The English data uses the super-
	sense inventory determined by WordNet's lexicog-
	rapher files, while the Danish supersense inven-
	tory is larger, because it extends some supersenses
	into subtypes, e.g., N.VEHICLE, N.BUILDING and
	N.ARTIFACT whereas WordNet only provides
	N.ARTIFACT; additionally the Danish data set
	provides four coarse supersenses for adjectives:
	A.MENTAL, ADJ.PHYS, A.TIME, A.SOCIAL.

Table 3

 3

	provides statis-
	tics on the doubly-annotated data used to calculate
	disagreement factorizations, including annotator
	agreement scores. Note that the English doubly-
	annotated data is considerably smaller.

1 https://github.com/coastalcph/semdax

Table 3 :

 3 Statistics on the doubly-annotated data, incl. raw observed agreement A o and Cohen's κ.

	3.3 Model
	Supersense tagging is typically cast as a sequen-
	tial problem like POS tagging, but the class dis-
	tribution is more skewed with a majority class
	O. We use the structured perceptron RUNGSTED,
	which allows cost-sensitive training. 2 We use the
	same feature representation as Martínez Alonso et
	al. (2015b), which includes information on word
	forms, morphology, part of speech and word em-
	beddings. We use 5 epochs for training. All
	results are expressed in terms of micro-averaged
	F 1 -score, calculated using the official CONLLE-
	VAL.PL script from the NER shared tasks.

  Modifyingthe Danish data to harmonize with S EN has thus

	lang	dataset	MFS BASELINE WHOLETAGS JUSTSENSE NOPOS BIOPREFIX
	EN	Average	42.51	51.36	52.31	51.72	51.13	51.13
	EN	*SemCor	62.53	65.58	65.57	65.45	64.39	64.47
	EN	RITTER-dev	41.54	53.44	53.95	52.76	52.51	52.30
	EN	RITTER-eval	38.94	49.03	49.65	49.97	49.41	49.42
	EN	LOWLANDS	27.11	37.38	36.93	38.71	38.22	37.33
	DA	Average	33.63	40.53	39.95	40.70	39.94	39.08
	DA	NEWSWIRE-eval 31.47	42.13	42.21	42.78	41.27	40.93
	DA	BLOG	25.57	39.43	35.73	37.50	37.04	38.04
	DA	CHAT	36.06	38.18	39.12	38.79	39.81	38.72
	DA	FORUM	31.08	35.35	34.68	35.45	35.15	34.45
	DA	MAGAZINE	34.28	41.97	40.91	42.67	42.09	41.44
	DA	PARLIAMENT	38.57	43.04	42.81	42.84	41.32	39.20
	Table

Table 5 :

 5 F 1 s for English using cross-lingual costs calculated from S DA

	dataset	MFS	BASELINE	WHOLETAGS	JUSTSENSE	NOPOS	BIOPREFIX
	Average	42.51	51.36	50.86	51.32	52.52	49.70
	SemCor	62.53	65.58	64.56	64.69	65.69	65.06
	Ritter-dev 41.54	53.44	53.04	53.52	53.42	52.31
	Ritter-eval 38.94	49.03	49.17	49.58	49.55	48.90
	Lowlands 27.11	37.38	38.68	37.50	37.53	32.51
	Instead of training on annotator-specific data, we
	use disagreement to regularize over individual an-
	notators. Tomuro (2001) has used mismatching
	annotations between two sense-annotated corpora
	to find causes of disagreement such as systematic
	polysemy.

https://github.com/coastalcph/ rungsted


Héctor Martínez
email: hector.martinez-alonso@inria.fr

Daniel Zeman
email: zeman@ufal.mff.cuni.cz

Universal Dependencies for the AnCora treebanks Dependencias Universales para los treebanks AnCora

Keywords: AnCora, treebank, catalán, castellano, Dependencias Universales AnCora, treebank, Catalan, Spanish, Universal Dependencies

Resumen: Este artículo presenta la conversión de los treebanks AnCora del catalán y el castellano al formalismo de Dependencias Universales (UD). Describimos el proceso de conversión y estimamos la calidad de los treebanks resultantes en términos de sus resultados en análisis sintáctico automático en un esquema monolingüe, en un esquema trans-lingüístico y en un tercero trans-dominio. Los treebanks convertidos muestran un nivel de consistencia interna de anotación comparable a la de los datos originales de la distribución CoNLL09 de AnCora, e indican algunas diferencias en terminos del inventario de expresiones polilexemáticas con respecto al anterior treebank del castellano en UD. Los dos nuevos treebanks convertidos serán distribuidos con la versión 1.

Introduction

AnCora treebanks 1 [START_REF] Taulé | AnCora: Multilevel annotated corpora for Catalan and Spanish[END_REF] are consolidated treebanks for Catalan and Spanish, and have indeed been the canonical treebanks of these languages. Their smaller, preliminary versions were used in the CoNLL 2006 and 2007 shared tasks in dependency parsing; the much larger and mature AnCora 2.0.0 was used in CoNLL 2009 [START_REF] Hajič | The CoNLL-2009 shared task: Syntactic and semantic dependencies in multiple languages[END_REF], henceforth CoNLL09. The native AnCora syntactic annotation is based on constituents but an in-house conversion to dependencies is also available [START_REF] Civit | Cat3LB and Cast3LB: from constituents to dependencies[END_REF].

In this article we present the conversion of the AnCora treebanks to Universal Dependencies. There is a UD Spanish treebank since release 1.0 (January 2015). This corpus is a legacy of an older universal treebank 1 http://clic.ub.edu/corpus/ project [START_REF] Mcdonald | Universal dependency annotation for multilingual parsing[END_REF] and it is unrelated to AnCora. It is made up of web data and we refer to it as the Spanish Web UD treebank. However, according to the Web treebank documentation, its developers have made use of AnCora for lemmatization and morphological analysis. With our UD conversion of AnCora, appearing in UD release 1.3 (May 2016), the UD collection thus contains two treebanks for Spanish, as well as the first UD treebank for Catalan. Independent from our work, a Galician treebank is also scheduled to appear in UD 1.3. If we also consider the already existing Basque and Portuguese treebanks, UD 1.3 will allow parsing a great deal of the linguistic diversity of the Iberian peninsula.

Section 1.1 outlines the important characteristics of the UD formalism that we have taken into account for the conversion. Section 2 describes the conversion steps. Sec-tion 3 offers quantitative evaluation of the conversion results, and finally Section 4 offers conclusions and perspectives.

Universal dependencies

Universal Dependencies (UD) 2 [START_REF] Nivre | Universal dependencies v1: A multilingual treebank collection[END_REF] is a project that seeks to define crosslinguistically applicable annotation guidelines for morphology and syntax of natural languages. An integral part of this effort is frequent releases of annotated data (UD treebanks) in multiple languages, that conform to the UD guidelines and that are freely available to the research community.

UD uses a set of 17 universal POS, a set of 40 universal dependency relations, and a set of universal features to give account for lexical or grammatical information in terms of key-value pairs like Gen-der=Fem. The POS inventory is fixed across all languages-even though not all languages use all tags-whereas the formalism allows language-specific extensions of dependency relations and features.

A key aspect of the UD dependency formalism is the primacy of content over function words. While other conventions make auxiliaries the head of periphrastic verb tenses, or even determiners the head of noun phrases, content words are the preferred heads in UD. Notably, this analysis also demotes copula verbs to dependent status, and makes the attribute the head of the copula construction. This decision aims at harmonizing the representation across languages, including those that have no explicit copula. Figure 1 shows an example sentence from the original Spanish AnCora CoNLL09 corpus and its UD conversion. We describe the example in more detail in Section 2.5.

El error fue {haber lo} comprado en rebajas .

The mistake was to have -it bought on sales The main contribution of this conversion is to make the AnCora treebanks available for further research using the UD formalism, as they are treebanks that have been benchmarked for a decade. During conversion, we make the treebanks compliant with the specifications of the UD formalism, and we harmonize certain choices to increase compatibility with the other Romance languages, in particular aiming at making the choices of structure and part of speech as similar as possible between the already existing UD Spanish Web treebank and our conversion of Spanish AnCora.

Conversion

Recent work [START_REF] Kolz | From constituents to syntax-oriented dependencies[END_REF] describes a dependency conversion of the Spanish AnCora treebank. However, it used a syntax-driven formalism, where function words are more likely to be the heads. In this present work we take the complementary stance.

Moreover, the AnCora treebanks have already appeared in another multi-lingual treebank collection, namely HamleDT [START_REF] Zeman | Ham-leDT: Harmonized multi-language dependency treebank[END_REF], which is one of the predecessors of UD. 3 HamleDT provides an automatic conversion of over 40 treebanks by first converting them all to the formalism of the Prague Dependency Treebank, and later exporting them to either the Stanford dependency formalism in the first releases of HamleDT, or to UD in the current release 3.0 [START_REF] Zeman | HamleDT 3.0. LINDAT/CLARIN digital library at Institute of Formal and Applied Linguistics[END_REF]. However, HamleDT 3.0 does not follow some important UD guidelines, most notably those concerning tokenization. We take HamleDT as our starting point and extend the conversion to produce a fully UDcompliant release of the sibling corpora.

HamleDT conversion outline

We make use of the freely available Ham-letDT 3.0 conversion to incorporate the An-Cora treebanks to UD. This section provides an overview of the main operations carried out during the HamletDT conversion. For further details, cf. [START_REF] Zeman | Ham-leDT: Harmonized multi-language dependency treebank[END_REF]. First, HamleDT transforms the original CoNLL09 treebanks to Prague Dependencies [START_REF] Böhmová | The prague dependency treebank[END_REF] junct). This effectively means reverting to the approach taken in the original CoNLL09 data, except that now all coordination is explicitly and uniformly marked. For more details on the complexities of coordination conversion and the function-structure tradeoff in dependency syntax, cf. [START_REF] Popel | Coordination structures in dependency treebanks[END_REF]. 3. Invert prepositional phrases so that the nominal is the head and the preposition is attached to it using the case relation.

4. Invert copula constructions so that the attribute (adjective or nominal predicate) is the head and the copula is attached to it using the cop relation. The subject and adverbial modifiers are also re-attached to the attribute. 5. Detect controlled verbs and treat them as non-finite subordinate clauses, i.e. infinitives attached to other verbs, e.g. in va refusar donar més detalls ('refused to elaborate'), donar is attached to refusar with the relation xcomp.

Tokenization

Tokenization makes up the most of our adaptation from HamleDT 3.0 to full UD compliance. Notice that tokenization changes in an already-annotated treebank are not trivial, because they also imply rewriting the dependency structure of the sentences with modified tokens. We also implement other operations like feature and empty-sentence cleanup. The UD stance on tokenization is that dependency relations hold between syntactic words, which do not have to be identical with orthographic words. Surface tokens are split if their parts perform independent syntactic functions. For instance, del is the preposition de fused with the definite article el ; in UD, the preposition and the article are independent syntactic words corresponding to separate nodes in the dependency tree.

On the other hand, UD does not allow tokens to be made up of more than one orthographic word, i.e. "words with spaces" are disallowed. If a frozen expression of multiple orthographic words behaves as one syntactic unit (where the internal syntactic structure does not exist or has become vacant), each orthographic word will have its own node in the tree and technical relations such as mwe (for multiword expressions) or name (for proper names) will connect them. The head of these two kinds of structures is the leftmost token, and all other tokens are its dependents. Figure 2 provides an example of mwe in UD. The expression pel que fa a (lit. 'for that which does to', En. 'regarding') is a single token in the CoNLL09 data joined with underscores, and becomes a mwe subtree.

A key difference between mwe and name subtrees is that UD guidelines treat prepositions, articles and conjunctions in proper names as such, and not as tokens with the PROPN POS tag. This difference implies that tant (per el que fa) a elements naturals com d' ordenació [...] as for that which does to elements natural as of ordinance name subtrees like Ajuntament de Vilanova i la Geltrú will have more than one depth level where the words in bold will be leaves, whereas the depth of mwe is always one. The CoNLL09 treebanks make elliptic subjects explicit by giving them an empty token with pronoun POS and subject function, marked with an underscore as form. Elliptic subjects are not syntactic words, and we remove them from the sentences.

Moreover, UD allows providing the original tokens of certain constructions prior to being tokenized apart into syntactic words. These multiword tokens are provided as an additional annotation of the sentence and play no role in the syntax, but can be used for ease of reconstruction of the original text, to train tokenizers, etc. We apply languagespecific modifications to identify two kinds of multiword tokens in Catalan and Spanish, namely fused article-preposition tokens, and verbs with clitics.

Catalan-specific tokenization

The Catalan inventory of fused adpositionarticles is al, del, pel, and their plural forms als, dels, and pels, for a total of six. We split these tokens into their two forming syntactic words, and provide the original token as a multiword token.

Clitic tokenization in Catalan is simple because clitics are introduced by hyphens or apostrophes. Verbs with clitic pronouns are already tokenized apart in AnCora-Catalan. We identify verb-headed spans with clitics and add the multiword-token to the annotations of the sentence. The most common possessive determiner construction is a twoword periphrasis e.g. la meva casa ('my house'), where the first word is the definite determiner (la, 'the') and the second one is the possessive adjective (meva, 'mine'), placed prenominally and consecutive to the determiner. The original AnCora tokenization treats these two words together as a one, joined with underscores. We split these pretokenized possessive constructions into their two forming syntactic words, and make them both dependent of the noun they introduce. We inform of the possessiveness of the second word using the Poss feature.

Spanish-specific tokenization

The Spanish inventory of fused adpositionarticles is a set of two, namely al and del. We split them and keep the original fused for as a multiword token.

AnCora-Spanish does not provide split verbs with clitics like encontrándoselas or abridlo, cf. Table 1. We split away the clitics for these verbs and insert them as pronouns, with a POS tag PRON and the corresponding case, gender and number features, making them dependents of the verb. Moreover, we normalize the spelling of the verb form without clitics by removing diacritics. e.g. encontrándoselas vs. encontrando. This change in spelling is a consequence of the change of stress pattern when removing clitics from the verb. We add the original multiword token verb as a sentence annotation.

Conversion example

Figure 1 shows the original AnCora (dashed, below) tree and the converted UD tree for the Spanish sentence El error fue haberlo comprado en rebajas' (En. 'The mistake was to have bought it on sales'). We can observe how the names of the relations are all different, and the relations above use the UD inventory. In terms of the structure, the original main node fue is demoted to leaf status as a cop, a copula auxiliary of the predicate comprado, which is the main node in the UD tree. Note that fue does not license a passive reading, which would be marked as auxpass. The preposition en also becomes a leaf, in this case of the noun rebajas. Moreover, the verb-clitic multiword haberlo ('have+it') is split in two different tokens, and lo is a dobj dependent of the verb comprado.

Results

Treebank properties

There is of course the danger that each new conversion will lose more information or introduce errors. We dedicate this section to determining the consistency of the treebanks after UD conversion. Table 2 shows the properties of the AnCora treebanks at their three distributions, namely CoNLL09, HamleDT 3.0 and UD 1.3. The columns list the number of sentences (S ) and of words (W ), the POS ambiguity (PA), the average edge length (EL), the average root distance (RD), and the number of sentences that are not fully projective (NP ).

In terms of number of words and sentences, we keep the official test data split from the CoNLL 2009 shared task, where the training data is 80% of the corpus, and development and test data are 10% each. We can see that the number of sentences diminishes slightly as a result of empty-sentence removal, while the number of words increases in 10% as a consequence of splitting multiword expressions, fused preposition-articles, and verbs with clitics.

We measure POS ambiguity as the proportion of words that have more than one possible POS and a frequency above one. The conversion steps make PA increase. While an increase in ambiguity makes POS prediction harder using these datasets, it also indicates that the conversion process successfully applies a disambiguation of the original CoNLL09 POS inventory of 12 tags into the UD inventory of 17 tags by means of structure and feature analysis, notably incorporating the lexical verb / auxiliary verb distinction (VERB/AUX) and the common noun / proper name (NOUN/PROPN) distinction.

The average edge length (EL) increases monotonically on each conversion step, as relations across predicates are pulled up in the decision tree when e.g. a subordinate clause becomes headed by its verb and not by its subordinating conjunction. Parallel to this change, the average distance to the root node (RD) decreases because trees become flatter.

The CoNLL09 distribution of both An-Cora treebanks is fully projective. However, the conversion steps incorporate non projectivities into the structure. Upon manual inspection, we find that some non-projectivities are introduced by the splitting process of large proper-name multiwords that are internally connected by determiners and prepositions such as Les Terres de l'Ebre. Moreover, we also find legitimate case of nonprojectivity such as the Catalan example on Figure 2. The conjunction tant has scope over naturals com d'ordenació, and the intermediate word elements, higher in the tree, issues a crossing edge. The expression tant ... com is a double conjunction is a manner similar to 'as well ... as'.

Monolingual dependency parsing

Dependency parsing evaluation allows estimating the consistency of a treebank's annotations. We use TurboParser [START_REF] Martins | Turbo parsers: Dependency parsing by approximate variational inference[END_REF] for all the parsing experiments in this section. We have trained all the models using the local, arc-factored feature model for the parser. While a richer feature model would improve performance, we use the arcfactored model for speed reasons. The goal of the parsing experiments in the following sections is to assess the relative consistency of the different versions of the treebanks, and not to benchmark the parser itself. Nevertheless, arc-factored TurboParser obtains scores comparable to the best systems for Catalan and Spanish in the CoNLL09 shared task.5 Table 3 shows the parsing results for the three steps in the conversion of the treebanks, namely the original CoNLL09 AnCora distribution, the HamleDT 3.0 UD-compatible conversion, and our UD conversion.

These scores are not strictly comparable, given that all treebanks have different tokens, part-of-speech tags, and dependency relations. However, we provide them as an indication of the general reliability of the conversion. This approach has also been used in previous conversion works, who also report scores in the 80-85% range [START_REF] Johannsen | Universal dependencies for Danish[END_REF][START_REF] Pyysalo | Universal dependencies for Finnish[END_REF][START_REF] Silveira | Does universal dependencies need a parsing representation? an investigation of English[END_REF].

In spite of these differences, some relations are straightforward to compare. Spanish CoNLL09 treebanks have an average sentence accuracy of 93% and, and their UD conterparts have a root accuracy of 90%. This degradation is a result of i.a. the promotion of lexical tokens to the head of the copulas, which penalizes the general tendency to make verbs the heads of clauses.

Complementarily, the LAS of prepositions, tagged s in CoNLL09 and ADP in UD, goes from 79% to 97% after the conversion. This improvement is a result of preposition attachment becoming more local in UD, and easier to resolve, while noun attachment becomes more difficult to predict, and goes from 90% to 76%. Indeed, UD transfers most of the important relations to relations between content words, and makes function words easier to attach: auxiliaries, determiners and prepositions have all attachment accuracies above 96% in both UD AnCora treebanks.

Dependency parsing between UD languages

We use cross-lingual parsing as a way to estimate the consistency with the other treebanks, and thereby with the current state of UD as a whole. In order to do so, we apply a delexicalized transfer scenario, removing form and lemma information from the training data, and we train Turbo parser in unlabeled mode. While it is customary to also remove the feature information, we de-cide to keep all the morphological features of the source and target data, because they belong to the harmonized UD inventory.

Table 4 shows the results on training on Catalan or Spanish and testing on itself (Self ), on the other converted AnCora treebank (Sibling), i.e. training on Catalan and testing on Spanish. The three last columns show the results on delexicalized parsing the test section of whole set of UD1.2 languages. The All column provides the macro-average for all 32 languages, while the Romance column is the macro-average score for French, Italian, Portuguese and Romanian, as well as the pre-existing Spanish Web treebank. The Other column shows the average results for all the non-Romance UD languages. We compare the Spanish Web and the Spanish An-Cora treebank in more detail in Section 3.4.

Self Sib. Rom Other All Ca 84.5 81.7 66.2 49.5 52.0 Es 83.5 82.6 62.5 46.9 49.6

Table 4: mean UAS for delexicalized transfer.

The drop in UAS from full lexicalized to delexicalized is only of 5%. The high delexicalized parsing scores for Self indicate that, in spite of the chain of conversions, the An-Cora UD treebanks have a well-coupled mapping between the POS tags and features, and dependency structure. The AnCora UD treebanks are internally very consistent, and the parser achieves comparatively high UAS when trained on one sibling and applied to the other. However, the results are 20 points lower in average when parsing the other Romance languages. For Italian and Portuguese the score is around 71% for both sources, while for French it is around 53%. The internal variation between the Romance language test bench can have a linguistic basis, but it is also caused by divergences in the treebank's annotation. If we compare with the Other set, we observe the differences are even larger, and the drop from Romance to Other is of 13 points. Regardless of the variation in dependency annotation, there is more consistency between the new AnCora treebanks and the Romance languages, which confirms the linguistic basis for better parsing scores for e.g. Italian and Portuguese.

Dependency parsing between

AnCora and Web Spanish

We assess the similarity of the Ancora Spanish conversion to UD with the preexisting Spanish Web UD using dependency parsing.

If the two treebanks were as similar as possible, the differences in parsing accuracy when e.g. parsing with AnCora and testing with Web would be due to dataset size and domain change, and not to differences in dependency convention. Table 5 shows the attachment accuracies when using one Spanish treebank to parse the (Other ), along with intratreebank evaluation for comparison (Self ).

Self Other LAS UAS LAS UAS AnCora 84.9 87.3 64.0 71.8 Web 81.7 84.5 69.6 78.7

Table 5: Labeled and Unlabeled Attachment Scores (LAS and UAs, in grey) for the four possible source/target pairs for Spanish.

There is a severe drop in performance when changing training treebank, e.g. when using Web to parse AnCora, the performance drops in about 15 points, from 84.9% to 69.6% LAS. A similar drop of 17 points appears when using AnCora to predict Web.

These differences are large enough not to be exclusively an effect of domain change. UD treebanks encode some lexical information such as multiword expressions in the dependency structure (cf. Section 2), and the inventory of multiword expressions is different across treebanks.

In AnCora UD, the elements marked as multiwords are the tokens that were underscored together in the CoNLL09 data, and that were not proper names. AnCora UD has 521 word types that are attached with a mwe relation, whereas Web has 113. While AnCora has a larger mwe inventory, it is not a perfect superset of the mwe expressions in Web, because it only covers 80% of the expressions in the Web corpus. Some of the common expressions are treated in the same fashion in both treebanks, such as sin embargo, ni siquiera, or a través de ('nevertheless', 'not even', 'through'), but the difference in multiword inventory make the parser predict mistmatching structures across datasets.

Both treebanks have a lenient definition on auxiliary verbs. Besides the auxiliares that are used to form verb tenses, namely haber for compound tenses, ser for passive forms, and estar for gerund forms, the treebanks also license an AUX reading for verbs that indicate modality (poder, querer), aspect (continuar, terminar), and also other verbs used for support constructions like llegar in llegar a causar ('come to cause'). These choices are semantically motivated and aim at promoting the lexical verb of the construction to the head of the structure (cf. Section 1.1, instead of treating light verbs as syntactic heads. However, Romance languages do not have a family of modal verbs as distributionally well-defined as Germanic languages do, and the criteria for labeling a semantically impoverished verb as AUX can be revised in further releases of the treebanks.

Another major difference between the two Spanish treebanks is the interpretation of the word que as either a subordinating conjunction or a pronoun (SCONJ / PRON), which gives a very low attachment score to pronouns (35%) in the cross-treebank (Other ) setup, in spite of the very high accuracy in the intra-treebank setup (85%).

The AnCora Spanish corpus is largely made up of newswire from Spain, whereas the Web Spanish corpus potentially holds any of the variants of Spanish. We find sentences like Olvidate todo, seguí tu vida ('Forget about everything, get on with your life'), with verb usage characteristic of Rioplatense Spanish. A more detailed study on the differences between both Spanish corpora would shed light on the relevance of regional specificity in corpus choice for Spanish processing.

Conclusion

We have presented the conversion of the Catalan and Spanish AnCora treebanks to the Universal Dependencies formalism. We use the freely available HamleDT 3.0 as a starting point for POS and dependency conversion, and we apply a set of operations to tune tokenization to UD, tackling language-specific phenomena like fused article-prepositions like del and verb-clitic multiword tokens like encontrársela.

We have evaluated the consistency of the resulting converted treebanks by means of dependency parsing. We obtain parsing scores comparable to other converted UD treebanks (cf. Section 3.2), and we assess the variation between UD languages in terms of typological proximity and annotation convention using delexicalized transfer parsing 3.3. The fairly large loss of unlabeled attachment score for the other languages is much less dramatic for the Romance languages.

We also analyze the differences between the Spanish Ancora UD-converted treebank and the preexisting Spanish Web treebank. While the parsing between the two Spanish UD treebanks fares above the delexicalized transfer setup, the differences in multiword treatment and some POS particularities indicate that the treebanks need further harmonization.

Further work

Universal Dependencies is a constantly improving effort, and the guidelines are refined before each release. In further releases, we expect to harmonize the two AnCora UD treebanks with regards to the treatment of auxiliary verbs across all Romance languages, revise the non-projective sentences and keep the legitimate examples, and in particular improve the comparability of the two UD Spanish treebanks, namely AnCora and Web.

Figure 1 :

 1 Figure1: Example of dependency tree before and after conversion. Above: UD, below: CoNLL09 (dashed).

2

  http://universaldependencies.org/

Figure 2 :

 2 Figure 2: UD Catalan example with a multiword expression subtree (dashed) and a nonprojectivity caused by coordination (thick edge) crossing another edge.

  -plur 3-m-s-a

Table 1 :

 1 Spanish clitic-verb examples.

Table 3 :

 3 The sentence relation in CoNLL09 maps to the root relation in UD. Both the Catalan and Labeled and Unlabeled Attachment Scores (LAS and UAs, in grey) for the three different conversion stages of the treebanks.

			S	W	PA	EL RD NP
		Ca CoNLL09 16,786 497k 0.10 3.66 4.60	0
		HamleDT 16,786 497k 0.13 3.86 4.07 76
		UD	16,678 547k 0.16 4.00 4.12 468
		Es CoNLL09 17,709 528k 0.11 3.69 4.76	0
		HamleDT 17,709 528k 0.13 3.90 4.22 327
		UD	17,680 569k 0.15 3.99 4.19 624
			Table 2: Treebank statistics
	C09	HDT	UD
	LAS UAS LAS UAS LAS UAS
	Ca 86.7 89.6 85.4 87.7 85.4 87.9
	Es 86.1 88.9 85.0 87.1 84.9 87.3

http://ufal.mff.cuni.cz/hamledt/

http://universaldependencies.org/tagsetconversion/index.html

https://ufal.mff.cuni.cz/CoNLL09-st/ results/results.php


Taus Brock-Nannestad
email: taus.brock-nannestad@inria.fr

Space-efficient Planar Acyclicity Constraints A Declarative Pearl

Many constraints on graphs, e.g. the existence of a simple path between two vertices, or the connectedness of the subgraph induced by some selection of vertices, can be straightforwardly represented by means of a suitable acyclicity constraint. One method for encoding such a constraint in terms of simple, local constraints uses a 3-valued variable for each edge, and an pN `1q-valued variable for each vertex, where N is the number of vertices in the entire graph. For graphs with many vertices, this can be somewhat inefficient in terms of space usage. In this paper, we show how to refine this encoding into one that uses only a single bit of information, i.e. a 2-valued variable, per vertex, assuming the graph in question is planar. We furthermore show how this same constraint can be used to encode connectedness constraints, and a variety of other graph-related constraints.

Introduction

In this paper, we aim to present an "encoding pearl" that shows how to encode various graph constraints in terms of an acyclicity constraint, and also how to decompose such an acyclicity constraint into a space-efficient (in terms of the combined sizes of the variable domains) collection of low-level constraints.

Our acyclicity constraint can be seen as a refinement of an intuitive, obviously correct, but space-inefficient constraint, which, to the best of our knowledge, is due to Tamura [START_REF] Tamura | Solving puzzles with sugar constraint solver[END_REF], although it is an obvious enough encoding that it may simply be folklore. To the best of our knowledge, the space-optimised constraint we present here is novel.

We will present our constraints both using a high-level, prose description, but also in terms of the more explicit language of finite linear integer constraints. We choose this as the target for our encoding because of its flexibility -we will freely make use of the fact it straightforwardly permits the encoding of e.g. conditionals and reified constraints.

In many cases, using a specialised acyclicity constraint, such as the one presented by Gebser et al. [START_REF] Gebser | Sat modulo graphs: Acyclicity[END_REF], will be more efficient for finding solutions to constraint satisfaction problems, as it can use domain-specific knowledge to propagate constraints in a way that a naïve encoding may not be able to.

On the other hand, there are often large gains to be had from encoding a problem using high-level constraints into e.g. a boolean satisfiability (SAT) problem, as seen in the Sugar CSP solver [START_REF] Tamura | Compiling finite linear csp into sat[END_REF].

Given the above considerations, we make no claims about the real-world efficiency of the solution we present in this paper, and rather present it as a neat theoretical curiosity.

The remainder of the paper is structured as follows. In Section 2, we show how acyclicity plays a crucial rôle in encoding path constraints. In Section 3, we present a straightforward but space-inefficient encoding of such a constraint, in a subset of planar graphs which we call grid graphs, followed by a few improvements in Section 4. In Section 5, we present our optimised encoding, and we prove its correctness in section 6. In Section 7, we show how to extend the results concerning grid graphs to general planar graphs without a loss in efficiency. Section 8, we consider other kinds of graph constraints, and show how these can also be encoded using our acyclicity constraint. Finally, in Section 9, we conclude and discuss future work.

Making use of acyclicity

In this section, we will show exactly how an acyclicity constraint can be used to correctly enforce certain constraints on graphs. First, let us assume we are given some fixed graph G with two distinguished vertices s and t, and that we wish to select some subset of the edges so that they make up a single simple path from s and t. We will associate a variable to each edge of the graph, and say this variable has the value 1 if the edge is selected, and 0 otherwise. To ensure that the path is simple, we can add constraints that restrict the number of selected edges meeting a vertex as follows:

-Around s and t, we require that there is exactly one selected edge.

-For any other vertex v, we require that the number of selected edges around v is either 0 or 2.

These constraints already eliminate many incorrect selections, but unfortunately not all of them. The problem is that the above constraints ensure that the solution must be path-like around each vertex, but this is not enough:

s t ù s t
Any part of a cycle is also path-like around each vertex in the cycle, hence we may get spurious cycles with just the above constraints. At this point it should hopefully be clear that if we find some way of preventing cycles from appearing in our assignment of edges, we may ensure that the solution consists of only a single, simple path. Before we present a way of encoding such an acyclicity constraint, we will briefly remark on two simplifying assumptions we can make in this setting. First of all, we may assume that the graph in question is simple, i.e. there is at most one edge between any two vertices, and no edges from a vertex to itself. This can be justified by noting that if we have selected two edges that have the same start and end vertices, then we have already created a cycle. Similarly, any edge that is not part of any cycle of the graph can also be disregarded for the purposes of enforcing acyclicity. Thus, in the remainder of this paper, we will assume that the underlying graph is simple and bridgeless.

A basic encoding of the acyclicity constraint

First, we'll describe an inefficient, but hopefully intuitive encoding of an acyclicity constraint. To simplify the presentation, we'll only present the results in this section for a very simple and well-behaved graph. The graph we will consider has a vertex for each point pi, jq P Z ˆZ, and edges between any two vertices that are a unit distance apart. For the variables representing these paths, we will use h i,j for the horizontal edge extending rightwards from the vertex at pi, jq, and v i,j for the edge extending vertically at this vertex. Furthermore, we will in certain situations rely on these edges having values that indicate not just whether they are selected, but also marking them with a specific direction. In this case, we will assume that the variables h i,j and v i,j may take on values from the set t´1, 0, 1u. A negative value indicates that the direction of the edge is to the left or down, and a positive value indicates that the direction of the edge is to the right or up. Thus,

0 1 2 0 1 2 is represented by h 1,1 " ´1, v 1,1 " 1, h 1,2 " 1, v 2,1 " ´1
To avoid having to consider truly infinite graphs, we will assume that all variables that are indexed by positions pi, jq take on the default value 0 on all but finitely many points. This essentially restricts us to working within a finite subgraph of the grid graph. The benefit of doing this, as opposed to working with finite graphs to begin with, is that this presentation allows for a uniform presentation of the constraints, and in particular avoids nasty boundary conditions that might otherwise arise.

Essentially, the constraints we will add have the following effect:

-First, all paths are forced to be simple -paths may not touch or cross each other: @i, j.

|h i,j | `|v i,j | `|h i´1,j | `|v i,j´1 | P t0, 1, 2u.
-Secondly, all paths are forced to be directed. If a vertex has two edges connected (which is the maximum as per the previous constraint), then one edge must be pointing towards the vertex, and the other must point away from the vertex. This can be encoded as follows:

@i, j. |h i,j ´hi´1,j `vi,j ´vi,j´1 | ď 1

This constraint may seem a bit unintuitive, but it is a straightforward matter to check that this (along with the preceding constraint) forces paths to be directed.

Next, we associate a variable u i,j to each vertex pi, jq. This variable will take on values from the set t0, . . . , N u where N is the number of vertices of the subgraph we are considering. These variables are constrained as follows:

-Along any directed edge, the value of the source vertex must be strictly greater than the value of the target vertex: @i, j. ph i,j ą 0q Ą pu i,j ą u i`1,j q @i, j. ph i,j ă 0q Ą pu i,j ă u i`1,j q @i, j. pv i,j ą 0q Ą pu i,j ą u i,j`1 q @i, j. pv i,j ă 0q Ą pu i,j ă u i,j`1 q

The effect of these constraints is the following: first, all cycles must become directed cycles, as enforced by the first constraint. Second, the vertices appearing in a directed path must have values that are strictly decreasing along this path. Having both of these constraints thus precludes any cycles from appearing in the graph. Of course, this constraint might be too strict, for instance by excluding paths that should be allowed, but it's easy to see that any directed path can have strictly decreasing values assigned to it, since the domain of these values is larger than the number of vertices in the graph.

The main problem with this encoding is the size of the domain of the values. We require that each vertex pi, jq has a unique variable u i,j associated to it, and that these variables may take on values from the domain t0, . . . , N u where N is the total number of vertices in the graph. Thus, the more vertices our graph has, the greater this domain must be, leading to a quadratic growth in terms of space.

Potential refinements

In this section, we will explore a few possible refinements that unfortunately do not quite improve matters. Although it is not customary to present approaches that do not work, we believe that in this case it gives a useful glimpse into the genesis of the encoding that will be presented in the next section.

The first and most obvious way of reducing the domains of the vertex variables would be to just reduce the domain. Unfortunately, this will in general also exclude some paths, which is not always desirable. The main problem with this approach is that the values along a path must still be strictly decreasing, hence whatever bounds we put on the values will also be a bound on the lengths of the paths it is possible to represent in the graph.

Of course, it is not necessary to strictly decrease the value along every edge in the graph. We could instead require that the values are non-increasing everywhere, as long as we have some guarantee that it will be strictly decreasing along at least one edge of any given cycle.

One way of enforcing this would be to pick a subset of the edges in advance, and tailor the constraints to be enforce a strict decrease along these edges, and allow any kind of decrease everywhere else.

How should one choose such a subset? An easy way to do so is to find a spanning tree of the graph, and then select all the edges that are not in this spanning tree to be the strictly decreasing ones. This works because any cycle must contain at least one of these edges, since the tree by definition cannot contain any cycles.

How much of an improvement is this? In a graph with N vertices, the spanning tree will contain N ´1 edges, and hence the number of strictly decreasing edges will be E ´pN ´1q where E is the number of edges in the graph. In the worst case, there exists a path that traverses all of these edges, and hence the domain of values associated to the vertices must have at least as many elements as the length of this path. In the case of the grid graph, we can define a spanning tree by taking all of the vertical edges, and a single horizontal line of edges. This leaves roughly half the edges of the graph as strictly decreasing.

Instead of choosing the strictly decreasing edges in advance, we might also select them in a more dynamic fashion. The basic idea is the following: if we can identify some feature (or set of features) that is guaranteed to be part of every cycle, we can use this to add strictly decreasing edges only at the points where these features occur. For instance, every cycle must contain at least one top-left corner, hence we could choose to make the vertical edge of each such corner strictly decreasing. This is again an improvement on the previous situation, as the number of such corners in any path can be bounded in advance. Note that any top-left corner cannot have a similar corner immediately below or to the right, hence in a grid with N vertices, N {3 is certainly an upper bound on the number of top-left corners. Unfortunately, we can still construct paths that contain many top-left corners, hence this is not an asymptotic improvement on the efficiency of the encoding.

Here are two examples of paths that have many top-left corners, which we have marked using circles:

If we consider these and other examples, it quickly becomes apparent that any path that contains many top-left corners must also contain many bottom-right corners, which are marked with squares above. Moreover, if we follow the paths given by these examples, we find that we alternate between top-left and bottomright corners.

An optimised encoding

As the refinements in the previous section hinted, there seems to be a relationship between the number of top-left corners and bottom-right corners.

First, we will change our encoding slightly. Instead of requiring a set of values to be (strictly) decreasing along the edges, we will instead keep just a single bit of information at each vertex. Our goal will be to give conditions that impose either equality or disequality constraints between vertices that are connected by an edge, in such a way that any cycle must contain an odd number of disequality constraints. If we can ensure this behaviour, then we will have succeeded in disallowing all cycles. Intuitively, we can imagine walking along the cycles with a single bit, following the directed edges, and flipping the value of our bit whenever we encounter a certain configuration of edges. As long as we make an odd number of flips, we are guaranteed to end up with the opposite parity when we return to the starting position. Naturally, paths with be unaffected by these constraints.

To encode these constraints, we first assign a binary-valued variable p i,j to each vertex pi, jq. We next add the following constraints:

-For all edges directed downwards or to the left, we simply enforce equality between the values at each end: @i, j. ph i,j ă 0q Ą pp i`1,j " p i,j q @i, j. pv i,j ă 0q Ą pp i,j`1 " p i,j q -For edges directed upwards or to the right, we similarly constrain the values at each end, but choose whether to enforce equality or disequality depending on whether the edges in question form an "up-then-right" or "right-then-up" corner: @i, j. ph i´1,j ą 0q Ą pp i´1,j " p i,j ' pv i,j ą 0qq @i, j. pv i,j´1 ą 0q Ą pp i,j´1 " p i,j ' ph i,j ą 0qq

Here, ' is the "exclusive or" operation.

Note that these four constraints cover all the possibilities for which the value of h i,j and v i,j is non-zero. Moreover, the four constraints are also disjoint, i.e. for any given edge, at most one of the above constraints apply. Here is an example that shows how the above constraints force the assignment of the p i,j values for a particular directed path (where we have arbitrarily set the value of p at the beginning of the path to 0):

0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1
The circles and squares indicate the vertices at which the flips take place. Observe that if we were to close the cycle by adding an extra edge going left, there would be no way of reconciliating the values of p.

All that remains now is to show that closed simple cycles must always contain an odd number of corners at which the parity flips. This will be the subject of the next section.

Turning number parity

In this section we will prove that the turning number of a simple closed cycle is always equal to either 1 or ´1.

This result is known already for suitably well-behaved curves in the plane [START_REF] Whitney | On regular closed curves in the plane[END_REF] and also for polygons [START_REF] Grünbaum | Rotation and winding numbers for planar polygons and curves[END_REF], but to keep this paper somewhat self-contained, we will present a proof from first principles.

First, we must define precisely what kinds of directed paths we allow.

Definition 1. A directed path consists of a sequence of steps of unit length going either up, right, left or down. We furthermore require that whenever a path changes direction, it does so by ˘90 ˝. We say a path is closed if the last step of the path ends at the beginning of the path. We say a path is simple if it does not cross or touch itself, that is, every point is the source or target of at most two segments of the path.

Definition 2. A corner of a given path is any point at which the path makes a turn. We use the notation é for a corner at which the path moves up and then right, and define

In arithmetic expressions, we use the same notation to represent the number of such corners in the path in question. Thus, é `é represents the total number of é and é corners in the given path.

We will first present a way of calculating the turning number of a path, i.e. the number clockwise rotations a person following the path would make. Note that this need not be a whole number.

Intuitively, whenever the path turns to the right locally (é, é , é or é ), the turning number increases by1 ⁄4, and conversely whenever it turns to the left locally ( é, é , é or é ), the turning number decreases by 1 ⁄4. Based on this, we define the turning number of a path as follows: Definition 3. The turning number of a path is defined as Of course, this definition is a bit cumbersome to work with, but luckily there is an easier way to calculate the turning number in the case of closed paths. To see this, we first need the following lemma: Lemma 1. For any closed path, the following equalities hold:

é ´é " é ´ é " é ´é " é ´é
Proof. Consider any é or é corner. Following the path in the direction of the arrow, we must eventually end up at a é or é corner, since the path is closed. A similar argument shows that any é or é corner is preceded by a é or é corner. Thus, we have the following equality relating the number of such corners in the path:

é `é " é `é .

By rearranging this equality, we get

é ´é " é ´é,
which gives us one part of the desired equality. The remaining equalities follow in the same way.

[ \ Corollary 1. The turning number of a closed path is given by é ´é .

Proof. Rearranging the definition of the turning number, we find that it is equal to 1 ⁄4ppé ´é q `p é

´ éq `p é ´é q `pé ´éqq.

By the preceding lemma, each of the four differences is equal to é ´é , and hence the entire expression reduces to simply é ´é .

[ \ In addition to this, we also have the nice result that the turning number of a closed path is well-behaved with regard to various transformations of this path:

Corollary 2. Rotating a closed path does not change the turning number. Mirroring or reversing the direction of a closed path inverts the turning number.

Proof. We show here one of the cases. Consider a given closed path. By the previous corollary, it has turning number equal to é ´é . If the direction of the path is reversed, every é corner becomes a é corner, and every é corner becomes a é corner. Thus, the value of é ´é is equal to é ´ é after reversing the direction of the path. We now have é

´ é " ´p é ´é q, and from the previous lemma, it follows that é ´é is the turning number of the reversed path. We thus conclude that reversing the direction of the path inverts the turning number. The remaining cases are similar.

[ \ Next, we need to show that any closed, simple path has a turning number of either `1 or ´1. We prove this in two steps. First, we show that any closed, simple path can be reduced to a path with only four edges (i.e. a square) by a sequence of local reductions. By observing that the local reductions preserve the turning number, we get the desired result.

Theorem 1. Any closed, simple path with length greater than 4 can be reduced using local reductions to a closed, simple path with a strictly smaller length and with the same turning number.

Proof. Formally, we prove this by induction on the length of the path. We will leave these appeals to the induction hypothesis implicit, however, and simply present the reductions. Additionally, we will present the reductions in terms of undirected paths, and only consider the turning number once we've established exactly what the reductions are. First, we want to find an appropriate place to reduce the path. This will be a horizontal segment of some length where each end of the segment points downwards:

First, however, we must establish that there must exist such a segment. We do this with a sequence of observations:

Observation 1: There is at least one horizontal segment. As the path has length greater than 4, it must contain some segment, either horizontal or vertical.

If the segment is horizontal, we are done. If the segment is vertical, we can follow it upwards until it turns (which it must, as the path is closed), and there we will find a horizontal segment. Observation 2: The topmost horizontal segment must turn downwards at each end. If at either end it turns upwards, we may follow the path upwards until it turns again. At this point, we will have found a horizontal segment which is higher up than the topmost horizontal segment, and this is a contradiction.

Having now established the existence of the desired segment, we will pick a segment of this form for which the length is minimal, i.e. no segment of this form with strictly smaller length exists. It is this segment we will reduce locally. We first consider the case where the left end of the segment turns under the segment. We ignore the right end of the segment for now:

The dotted lines at the bottom indicate the directions in which the path may proceed. Note that the path cannot turn up, as this would make it either nonsimple or of length exactly 4.

In this case, we reduce the path as follows:

ù

In a similar fashion, we can reduce the right end of the segment in the cases where it too turns underneath the segment. This leaves the following remaining case:

We would like to reduce it as follows:

ù

To do so, however, we need to argue that this does not make the path intersect itself, otherwise we would be unable to apply the induction hypothesis. We will therefore establish that there cannot be any horizontal segments immediately below the given horizontal segment. Assume for the purposes of contradiction that there exists such a segment. Following the segment to the left, it must eventually turn downwards. Turning upwards would make the path intersect itself. Similarly, the right end of the segment must also turn downwards. At this point, however, we would have a horizontal segment, turning down at both ends, and with a length that is strictly smaller than the length of the segment we started with, and this is a contradiction. As we have now established that there are no horizontal segments directly beneath our chosen segment, we may now reduce it as previously shown. This takes care of all possible cases. All that remains now is to note that the above reductions preserve the turning number. This can either be done the hard way, by checking every single case separately, or it can be done the clever way, by using Corollary 2. Note that rotating the path does not change the turning number, and reversing and mirroring it only changes the sign of the turning number, hence it is sufficient to observe that all the configurations seen in the reductions above can be rotated, mirrored or reversed in such a way that there are no é or é corners either before or after the reduction. It is then immediate that all the reductions preserve the turning number.

[ \ Armed with the above theorem, we may now prove that the desired property of closed, simple paths indeed holds.

Corollary 3. The turning number of a closed, simple path is either 1 or ´1.

Proof. Using the previous theorem, any closed, simple path of length greater than 4 may be reduced to one with a strictly smaller length, without changing the turning number. All that remains, then, is to check that all closed paths of length at most 4 have turning number ˘1. There are exactly two of these paths, and the result thus follows from a simple inspection of these.

[ \ Now that we have established that é ´é " ˘1, and thus é `é " 1 mod 2

we have shown that the constraint presented in the previous section indeed has the property that any closed simple cycle induces an odd number of disequalities, and thus leads to a contradiction.

From grid graphs to general planar graphs

In this section, we will show how to extend the results of the previous section to general planar graphs. One obvious way of doing this would be to use the fact that any planar graph can obviously be approximated by a suitable subgraph of the grid graph, by suitably "rasterising" an embedding of the planar graph. This would not be particular efficient, however, as the approximation might use many more vertices than the original graph.

Instead, we will show how a certain kind of planar graph embedding gives rise to a straightforward way of assigning appropriate turning number parity constraints to a general planar graph.

Our main tool for this purpose will be the so-called visibility representation [START_REF] Otten | Graph representations in interactive layout design[END_REF][START_REF] Rosenstiehl | Rectilinear planar layouts and bipolar orientations of planar graphs[END_REF] of a planar graph. Put briefly, any planar graph can be represented in a form where every edge is a vertical line, and every vertex is a horizontal line: Now, this is already a much better representation than simply approximating an arbitrary planar embedding. First, note that the turning number parity does not change along any vertical edge, hence we can simply think of these as very tall single edges. Thus, we can easily represent any planar graph as one that is locally grid-like, by putting d vertices for each vertex of degree d in the original graph. However, we can in fact do better still. To see this, consider the ways in which a path can traverse a vertex in the visibility representation. If the path crosses the vertex without changing direction from up to down or vice versa, it is clear that the turning number parity does not change. This takes care of four of the possibilities. If, on the other hand, the path changes direction at the vertex, we must consider whether it moves leftwards or rightwards across said vertex. In the former case, the parity is unchanged, and in the latter case, it is flipped. This fully sums up the local behaviour of paths going through a vertex.

The key observation now is that we can enforce exactly this behaviour on any straight-line embedding of the planar graph. To do this, we will mark each vertex in the original graph embedding with information from the visibility representation that will enable us make the former act exactly as the latter. We will mark this as a small dotted arrow traversing each vertex. Every edge to the left of the arrow (when looking in the direction the arrow is pointing) will be among the edges above this vertex in the visibility representation, and dually the edges on the right of the arrow will be the edges below the vertex. Similarly, the edges will be ordered according to which order they occur around the vertex, using the direction of the arrow to distinguish between the possibilities. Essentially, one can think of this representation as one in which all the vertices in the visibility representation have been contracted into a single vertex again. The question of whether the parity should flip when traversing a vertex in this graph can now be easily explained in terms of this additional arrow: if the path "bounces off" the arrow, and is travelling in the direction the arrow is pointing, the parity should flip. In all other cases, the parity should remain the same.

Further graph constraints

In this section, we will consider a variety of further graph constraints that may be achieved by adapting our acyclicity constraint.

First, let us consider the problem of connectedness. Given a subset of the vertices, we would like to enforce that the subgraph containing exactly these vertices (and the edges that connect them with each other) is in fact connected. For the sake of simplicity, we will assume that we have selected one vertex r that is guaranteed to be in the subset. We now enforce the constraint as follows:

we associate a 2-valued variable s i,j to each vertex, representing whether said vertex is part of the selected subset. -For each vertex in this subset, except for the vertex r, we require that at exactly one of its edges is selected, and that it points away from the vertex: @pi, jq P Z ˆZztru. ph i,j ą 0q `pv i,j ą 0q `ph i´1,j ă 0q `pv i,j´1 ă 0q " 1

This constraint subsumes the constraints from Section 3 that forced the solution to contain only simple, directed paths, hence we discard these constraints.

The effect of these requirements is that our selected edges now induce a tree structure on the subgraph induced by the selected vertices. The vertex r then acts as the root of this induced tree. As there is only one root vertex, and as the tree will contain only edges from the subgraph, it is immediate that the subgraph in question must be connected. Again, the acyclicity constraint becomes crucial -without it, a tree may end in a cycle, and thus might fail to be eventually connected to the root. All that remains, then, is to ensure that the possibility of having multiple edges entering a vertex does not break the acyclicity constraint we have already defined. The only way this could happen is if there were some way to constrain a given edge to take on two unequal values at the same time. As we only constrain the value of an edge entering a vertex based on the local configuration of it and the edge (if any) leaving the vertex, and as there is at most one edge leaving a vertex, it is impossible for the acyclicity constraint to overconstrain the variables. Note that this is not the case if we allow more than one edge to exit a given vertex.

Single-cycle constraints

Previously, we have seen how to constrain the solution to consist of a single path. We will now consider how to constrain the solution to consist of a single cycle instead. Off-hand, this may seem a bit strange, as we would then simultaneously constrain the solution to contain no cycles, and yet also a single cycle, which would be a contradiction.

To get the desired behaviour, we will first adapt the acyclicity constraint to allow this constraint to be broken at exactly one vertex in the graph. We first associate a 2-valued variable b i,j to each vertex. This variable will be constrained as follows:

-Among all the vertices, at most one of them can have b i,j " 1. This is easily enforced by the following constraint:

ÿ i,j b i,j " 1
-At any vertex, the acyclicity constraint is only enforced if the value of b i,j is equal to zero. For each constraint Cpi, jq concerning the vertex pi, jq this amounts to adding a precondition as follows:

@i, j. pb i,j " 0q Ą Cpi, jq

At this point we have enough to encode the single-cycle constraint, but in fact we can do even better in this particular situation. One drawback of the acyclicity constraint we presented previously is that it requires a domain of size 3 for the variables associated to edges. If, on the other hand, our solution is known to consist of only cycles, we do not need this extra information to be encoded in the edges. The crucial observation is the following: if the solution consists of only cycles, we can keep track of the number of cycles (modulo 2) that any given face of the graph is inside. This allows us to associate a direction to each edge by stating that the face to the left of a given edge (as seen in the implicit direction of the edge) is always the outside face. The benefit of this optimisation is clear: instead of constraining the 3-valued edges to ensure that they give rise to directed cycles, we may assume they are 2-valued, and simply add a single 2-valued variable f i,j for each face of the graph. As there are generally more edges than faces in a given planar graph, this is an improvement. If we define that f i,j is the face that is immediately above h i,j and immediately to the right of v i,j , it is a straightforward matter to propagate the inside/outside information by the following constraints (recall that the edges now have domain t0, 1u): @i, j. f i,j´1 " f i,j ' h i,j @i, j. f i´1,j " f i,j ' v i,j

Where we previously used, say, h i,j ă 0, we may now instead put pf i,j´1 " 0q ^pf i,j " 1q, and thus restate the constraints from Section 5 in terms of the f i,j variables.

In fact, by doing this, we can eliminate the h i,j and v i,j variables entirely, and rewrite any expression referring to these variables into one using the f i,j variables instead.

Conclusion and Future Work

In this paper, we presented a novel way of encoding acyclicity constraints for planar graphs by means of a notion of turning number parity.

Although this encoding is efficient in terms of space, it is less clear whether it is actually practical to use. One benefit of the basic encoding is that cycles may be detected by simple interval constraint propagation where x P tk, . . . , u, y P tm, . . . , nu, x ă y immediately induces the constraints k ă y and x ă n, and thus constrains the domain of x and y to be tk, . . . , minp , n ´1qu and tmaxpk `1, mq, . . . , nu respectively. If moreover we know that y ă x, propagating the above constraint will eventually exclude all possibilities in the domain of either x or y, and thus create a contradiction.

For the refined constraint, the picture is less clear. Essentially, we induce a sequence of equalities and disequalities between the parity variables in our directed cycle. If we decide on the parity of some variable in a path, the consequences of this choice will immediately propagate to every other vertex in the path, and if the path is in fact a cycle, this propagation will ultimately fail. If, on the other hand, no such choice has been made, the constraint propagation engine may fail to detect the contradiction. Consider for instance the following (dis)equalities: a ‰ b, b " c, c " d, d " a, a, b, c, d P t0, 1u With these constraints, there is no local way to make progress by pruning the domains of the variables.

On the other hand, only a small bit of propagation is required to obtain a contradiction. If we add the following propagation rules x ‰ y, y " z ùñ x ‰ z

x ‰ y, y ‰ z ùñ x " z, and apply it to the above example, it will eventually derive a ‰ a, and get a contradiction. In fact, for path and cycle constraints, we can use the above as simplification rules, and allow them to consume both of the input constraints (for the connectedness constraint, this is no longer valid).

As we have shown, there exists an efficient encoding for planar graphs. It would be interesting to see how one might adapt the present constraints to handle non-planar graphs as well. One thing that should be noted is that the present approach does not immediately extend to more general graphs. Consider for instance the following graph embedded on the following planar representation of the torus (where the top and bottom edges are identified, and likewise for the

⁄4pé `é ` é `é q ´1⁄4p é `é `é `é q.

Acknowledgements This work is funded by the ERC Advanced Grant ProofCert.

left and right edges).

Here, it is easy to construct cycles that e.g. have no corners at all -in which case the turning number parity certainly doesn't change -or an even number of corners: Thus, it is necessary to add further constraints to ensure that these cycles are also excluded.