Shuya Zhang

The history of the polyfunctional 𗗙 jij

Keywords: case syncretism, differential object marking, locative, Tangut, Rgyalrongic languages

How did the accusative/genitive syncretism come about?

 [START_REF] Sun | Parallelism in verb morphology of Sidaba Rgyalrong and Lavrung in Rgyarongic[END_REF][START_REF] Lai | Tangut as a West Rgyalrongic language[END_REF]The most important functions of the postposition 𗗙 1139 jij 1 include differential object marking (i.e. accusative), and the genitive. It reflects the Proto-Rgyalrongic yod postposition =*j(V), the functions of which vary across different sub-groups. No modern Rgyalrongic varieties exhibit the same accusative/genitive syncretism as the Tangut 𗗙 1139 jij 1 . Before discussing the source of 𗗙 1139 jij 1 and the processes leading to its accusative/genitive syncretism, I will first briefly introduce the phenomenon of differential object marking and the sources of its markers.

Differential object marking

'Differential object marking' (henceforth DOM) refers to the non-uniform marking of objects within the same language, depending on their semantico-pragmatic properties [START_REF] Aissen | Differential Object Marking: Iconicity vs. economy[END_REF][START_REF] Bossong | Empirische universalienforschung: Differentielle objektmarkierung in den neuiranischen Sprachen[END_REF][START_REF] Dalrymple | Object and information structure[END_REF][START_REF] Naess | What markedness marks: The markedness problem with direct objects[END_REF]etc.), as illustrated by the pair of examples from Hindi given in [START_REF] Meyer | The morpheme yä-in Muher[END_REF].

hindi (indo-european)

(1) a. Ilaa-ne Ila-erg ek one bacee-ko child-acc uṭʰaayaa lift-perf 'Ila lifted a child. ' b. Ilaa-ne

Ila-erg ek one haar necklace.nom uṭʰaayaa lift-perf [START_REF] Mohanan | Argument structure in Hindi[END_REF]: 79) 'Ila lifted a necklace. ' DOM is often used as an umbrella term, 2 most frequently including systems exhibiting optional object marking, in which an object marker can optionally be present or absent without affecting its grammatical function, as is the case in Hindi, and those showing alternating marking, where two morphological case markers alternatively mark the object (for a detailed discussion on this issue see [START_REF] Zhang Chappell | Optional and alternating case marking: Typology and diachrony[END_REF].

Recurrent parameters of DOM involve animacy (humanness), definiteness, specificity, and information structure of the object [START_REF] Aissen | Differential Object Marking: Iconicity vs. economy[END_REF][START_REF] Dalrymple | Object and information structure[END_REF][START_REF] Sinnemäki | A typological perspective on Differential Object Marking[END_REF]etc.). In many languages DOM operates under a synergy of multiple parameters. In Hindi, accusative marking is related to animacy and definiteness, while animate and definite inanimate objects receive overt marking (Mohanan 1994: 84). In Dolakha Newar (Tibeto-Burman), DOM is coregulated by the animacy and topicality of the object. Its distribution can be described by two probabilistic trends: (i) topic animate objects often receive case marking; (ii) inanimate objects can occasionally be case-marked if they refer to a salient entity [START_REF] Genetti | Object relations and dative case in Dolakha Newari[END_REF](Genetti , 2007, cited in , cited in Dalrymple & Nikolaeva 2011: 137-139).

1.2 Sources and grammaticalization of DOM markers [START_REF] Bossong | Empirische universalienforschung: Differentielle objektmarkierung in den neuiranischen Sprachen[END_REF][START_REF] Bossong | Differential object marking Romance and beyond[END_REF] points to datives and other spatial related markers such as locatives, allatives as common sources for DOM markers, as found in Romance and Semitic languages. This observation is also relevant to the Tibeto-Burman languages in which 'locative-allative-dative-accusative' syncretism prevails [START_REF] Lapolla | Anti-ergative' Marking in Tibeto-Burman[END_REF][START_REF] Lapolla | On Nominal Relational Morphology in Tibeto-Burman[END_REF].

The spatial and dative sources of DOM markers seem to be further compatible with a widely attested grammaticalization chain which accounts for the evolution of the accusative, with the allative as a starting point, and the dative as an intermediate stage (Heine 2009: 467-468;Heine & Kuteva 2002: 38-39;Lehmann 2015: 119; among others), as illustrated in (2).

(2) Common grammaticalization chain of case functions (Heine 2009: 468) allative > dative > accusative (O)

Genitive syncretism

It is typologically rare for the dative/accusative morpheme to be isomorphic with the genitive. Yet in the Gunnän Gurage (Ethio-Semitic) languages, a highly polyfunctional case marker jä-is used as the (optional) accusative, dative, and genitive [START_REF] Meyer | Gurage[END_REF](Meyer : 1243)), as shown by the examples from Ezha given in (3).

ezha (ethio-semitic)

(3) a. abza Abza jə-mɨss-we acc-man-def k'ət't'ər-ə-n-ɨm kill.pfv-3m.sg.sj-m.sg.oj-cm ' Abza killed the man' b. abza Abza jə-dəsta dat-Desta

x w ett two bɨrr Birr ab-ə-n-m give.pfv-3m.sg.sj-3m.sg.oj-cm ' Abza gave two Birr to Desta. ' c. jə-dəsta gen-Desta gred girl.pl (Endalew 2017: 25, 27, 28) 'Desta's daughters'

In Tshangla (Bodish), the ending -ga falls into two functional domains, the locative-dative-(limited) accusative, and the genitive (Andvik 2010: 155-160). Both Gurage and Tshangla differ from languages like modern Mongolic [START_REF] Janhunen | On the taxonomy of nominal cases in Mongolic[END_REF], in which the accusative/genitive morpheme does not involve other abstract case functions [START_REF] Baerman | Case syncretism[END_REF] Type 2, i.e case syncretism of a core case and a non-core case).

The question of whether dative-accusative-genitive syncretism resulted from a single source or represents an accidental isomorphy remains controversial in both Gurage and Tshangla. For Gurage, Hetzron (1977: 54) assumed an accidental syncretism due to the phonetic fusion of two distinct case morphemes -*lä-'to, for' for the accusative/dative, and *zä-'for' for the genitive. However, later scholars [START_REF] Endalew | Multifunctional Morpheme jə-and -m in Ezha: An Ethio-Semitic Language[END_REF][START_REF] Meyer | The morpheme yä-in Muher[END_REF]) prefer a common source for all of these functions, though a clear grammaticalization pathway leading to this syncretism has yet to be proposed. Concerning Tshangla, Andvik (2010: 161;2017: 425) expresses uncertainty about a single source on the basis of dialectal evidence suggesting a proto-locative form *-gu probably distinct from the genitive *-ga.

This paper focuses on the case of Tangut (Rgyalrongic), in which a polyfunctional case marker 𗗙 1139 jij 1 exhibits an accusative/genitive syncretism similar to that observed in Gurage and Tshangla. I will argue that such syncretism in Tangut has resulted from the multi-path grammaticalization of a single locative source. Tangut is also unique in that the accusative/genitive morpheme 𗗙 1139 jij 1 (i) exhibits functional overlap with the dative 𘋩 5447 do 2 , and (ii) its locative source is obscure and can only be reconstructed through comparative data from modern Rgyalrongic languages. The aim of the paper is to illustrate that a typological rarity of extreme syncretism among abstract case functions can arise due to the superimposing of divergent grammaticalization pathways stemming from a spatial case, even if each individual pathway is typologically frequent.

The rest of the paper is organized as follows. In Section 2, I describe relevant morpho-syntactic features of Tangut. In Section 3, I analyze the clausal functions of the Tangut 𗗙 1139 jij 1 , paying special attention to comparison with the dative 𘋩 5447 do 2 . Section 4 provides comparative data from West Rgyalrongic and core Rgyalrong, laying a framework for Section 5, which attempts to explain accusative/genitive syncretism as resulting from multiple grammaticalizations of the Proto-Rgyalrongic general locative *=j(V). Section 6 offers concluding remarks.

Morpho-syntactic profile of Tangut

Tangut is a verb final language, exhibiting templatic verbal morphology. The verbal template of Tangut is much simpler than those of modern Rgyalrongic languages [START_REF] Jacques | The Structure of the Tangut verb[END_REF], and can be divided into three domains, as summarized in

Transitivity

Since transitivity is crucial to understanding the clausal functions of 𗗙 1139 jij 1 , which will be discussed in this paper later on Section 3, this section briefly introduces transitivity in Tangut.

As in other Rgyalrongic languages, transitivity in Tangut can be determined through indexation patterns, with intransitive and transitive verbs in Tangut following different indexation patterns [START_REF] Beaudouin | Tangut verb agreement: optional or not? Linguistics of the Tibeto[END_REF][START_REF] Gong | Xīxià yǔ dòngcí de rénchēng hūyìng yǔ yīnyùn zhuǎnhuàn [Personal Agreements and Phonological Alternations in the Tangut Verb[END_REF]Jacques 2014: 216-224, etc.). Intransitive subjects (S) are pronominally represented by three suffixes: 𗧓 2098 -ŋa 2 1sg, 𘉞 4601 -nja 2 2sg, and 𗐱 4884 -nji 2 1/2pl. The third person is unmarked. 3Transitive verbs have a maximum of two indexation slots, one for the subject (A) and one for the object (O). Alignment distinguishes three scenarios: (i) in a non-local scenario (3→3), the verb is always unmarked; (ii) in a local scenario (1→2, 2→1), the verb agrees with the patient; (iii) in a mixed domain (1/2→3, 3→1/ 2), the SAP argument is always pronominally represented on the verb, independent of its syntactic role. Table 2 illustrates the Tangut transitive paradigm with the causative auxiliary verb 𗟻 0749 phji 1 'to send, cause to do' .

A small number of transitive verbs have an additional stem [B] form, occurring in 1/2sg→3 forms [START_REF] Gong | Xīxià yǔ dòngcí de rénchēng hūyìng yǔ yīnyùn zhuǎnhuàn [Personal Agreements and Phonological Alternations in the Tangut Verb[END_REF][START_REF] Jacques | The origin of vowel alternations in the Tangut verb[END_REF][START_REF] Jacques | Esquisse de phonologie et de morphologie historique du tangoute[END_REF][START_REF] Gong | Verbs stems in Tangut and their orthography[END_REF]

𗉘 1374 tɕhjɨ 1 -pot … 𗧓 2098 -ŋa 2 1sg … … 𗭪 3916 -Sji 2 ifr … dir2: … … 𗭊 3989 jij 1 - … opt 𘀆 3846 njij 2 - … …
1sg 1pl 2sg 2pl 3 1sg 𗟻 0749 𘉞 4601 phji 1 -nja 2 𗟻 0749 𗐱 4884 phji 1 -nji 2 𗠔 4568 𗧓 2098 phjo 2 -ŋa 2 1pl 𗟻 0749 𗐱 4884 phji 1 -nji 2 2sg 𗟻 0749 𗧓 2098 phji 1 -ŋa 2 𗟻 0749 𗐱 4884 phji 1 -nji 2 𗠔 4568 𘉞 4601 phjo 2 -nja 2 2pl 𗟻 0749 𗐱 4884 phji 1 -nji 2 3 𗟻 0749 𘉞 4601 phji 1 -nja 2 𗟻 0749 𗐱 4884 phji 1 -nji 2 𗟻 0749 phji 1
Tangut also differs from modern Rgyalrongic languages in the emergence of non-finite forms in chained clauses [START_REF] Jacques | Tangut, Gyalrongic, Kiranti and the nature of person indexation in Sino-Tibetan/Trans-Himalayan[END_REF][START_REF] Beaudouin | Tangut verb agreement: optional or not? Linguistics of the Tibeto[END_REF]. As in (5), verbal inflections are only present in the final clause, and are neutralized in the preceding clauses.

(5) 𘋨 The neutralization of verbal inflections leads to ambiguities in transitivity marking in Tangut texts. Where there is an absence of morphological evidence, transitivity can be indicated on the basis of syntactic criteria, such ergative marking by 𘝦 5604 𘃡 5113 dʑjɨ.wji 1 , 4 as in (5).

Status of 𗗙 1139 jij 1 in Tangut case system

In contrast to its simplified verbal inflections, Tangut is rich in dependent case marking (cf. Table 3), which distinguishes itself from languages with their dominant head marking. The 𗗙 1139 jij 1 is versatile and is available for two functional domains (Kepping 1985: 145-148;[START_REF] Kotaka | Seikago no kakujoshi ni kansuru tōgoronteki kenkyū[A synthetic study of Tangut case particles[END_REF]etc.). First, it functions as a genitive marker, express-4. The ergative 𘝦 5604 𘃡 5113 dʑjɨ.wji 1 is optional after transitive subjects (Kepping 1985: 231), and its distribution still awaits further investigation. [START_REF] Nishida | Seikago [Tangut][END_REF][START_REF] Nishida | Seikago [Tangut][END_REF]) analyzes 𘝦 5604 𘃡 5113 as an 'emphasizing' agentive (強調主格), suggesting that its distribution could be related to semantico-pragmatic factors, as is widely observed in Tibeto-Burman (DeLancey 2011).

ing adnominal possession linking two noun phrases, or a noun phrase and a pronominal phrase (e.g. ( 6)). ( 6 Second, it occurs following a wide range of clausal functions, which can be subsumed under two labels, the accusative, marking indexable objects, or the oblique, occurring after various non-indexable functions. 5 In terms of clausal functions, the distribution of 𗗙 1139 jij 1 partially overlaps with that of the dative 𘋩 5447 do 1 , in particular after the R of ditransitive verbs. 6 Beaudouin (2021) argues that the dative use of 𘋩 5447 do 1 developed from its allative source, i.e. marking the endpoint of a motion. 7 The clausal functions of 𗗙 1139 jij 1 will be detailed in comparison with 𘋩 5447 do 2 in Section 3.

Clausal functions of 𗗙 1139 jij 1

This section examines the clausal functions of the case morpheme 𗗙 1139 jij 1 across three syntactic constructions, (i) object (O) marking with monotransitive verbs 5. 𗗙 1139 jij 1 was previously described as an 'anti-ergative' marker (Jacques 2014, etc.), a term introduced in the field of Sino-Tibetan linguistics by [START_REF] Lapolla | Anti-ergative' Marking in Tibeto-Burman[END_REF][START_REF] Lapolla | On Nominal Relational Morphology in Tibeto-Burman[END_REF] as a kind of semantico-pragmatically-based marking of grammatical relations, opposed to the ergative. This label is not used in this article, as one of the objectives of the paper is to specify the precise syntactic distribution of a particular case marker in order to trace its historical development. Given its flexible syntactic distribution, 𗗙 1139 jij 1 will be glossed here as gen, acc or obl, according to the syntactic function it marks. 6. The understanding of ditransitive verbs here follows Malchukov et al. (2010: 1) and refers to verbs having three arguments, prototypically associated with the semantic roles of Agent (A), recipient (R), and Theme (T). 7. There is no consensus on the case morpheme 𘋩 5447 do 2 . [START_REF] Nishida | Seikago [Tangut][END_REF][START_REF] Nishida | Seikago [Tangut][END_REF]: 479) and Arakawa (2010: 158) analyzed it as a pure locative case (場所格), expressing stative location as well as the endpoint of a motion. At the same time, they recognized 𘕿 5856 ɣa 2 as an accusative/ dative (對格/與格) case, co-existing with its locative source. Such differences could be relevant to corpus types. In my own corpus, since 𘋩 5447 do 2 is attested with a dative use while 𘕿 5856 ɣa 2 does not have significant dative/accusative functions, I follow the analysis of [START_REF] Beaudouin | Localiser en tangoute: entre continuums et bipartitions[END_REF]. Systematic analyses of these two case morphemes awaits future investigation.

(Section 3.1), (ii) recipient (R) marking with (non-derived) ditransitive verbs (Section 3.2), and (iii) non-subject argument marking in auxiliary causative constructions, involving argument promotion (Section 3.3).

Monotransitive verbs: Optional O marking

One of the most common uses of 𗗙 1139 jij 1 in Tangut is as a DOM marker. The presence or absence of 𗗙 1139 jij 1 does not affect object indexation, with the latter following syntactic rules.

Optional O marking with 𗗙 1139 jij 1 occurs on the basis of semantico-pragmatic properties of objects, and can thus be described as a prominence-based 8 rule coregulated by humanness, as noted in previous studies (Arakawa 2010: 161;Kotaka 2000: 79-80), definiteness, and the discourse topicality of the object.

Examples ( 7) and ( 8) illustrate the effect of definiteness on the distribution of 𗗙 1139 jij 1 . With the same monotransitive verb 𗜍 4225 sja 1 'to kill' , overt case marking is present for a definite human object in (7), but is absent for an indefinite human object in (8). ( 7 The prominence-based rule of Tangut optional O marking shows three probabilistic tendencies: (i) human/definite objects are most likely to take overt case marking; (ii) animate and definite objects are occasionally found bearing case marking; (iii) inanimate objects are not excluded from case marking (Arakawa 2010: 161) (e.g. ( 10)), but are the least frequently marked type.

(10) 𗪘 2104 𗥓 2857 𗗙 1139 𗇐 3832

[ɕji 1 Previous

ŋo 2 ] O =jij 1 illness=acc djị 2 to.heal [A] (心経03a-1-1, r Arakawa 2010: 161) 'Cure the previous illness (先の病治す)'

Ditransitive verbs: Alternating R marking

Typical ditransitive verbs in Tangut include 'Give'-and 'Say'-verbs, which are morphologically transitive, with two indexation slots for A and O. Most of them are morphologically indirective, 10 with the T indexed on the verb as the object (T=O). 11 The R, though non-indexable, receives obligatory case marking with the dative 𘋩 5447 do 2 or the oblique 𗗙 1139 jij 1 .

The distribution of 𗗙 1139 jij 1 and 𘋩 5447 do 2 in R marking tends to be complementary in Tangut. The postposition 𗗙 1139 jij 1 shows idiosyncratic distribution 9. Topicality can be measured by referential distance (Givón 1994: 10), as no antecedent is found in the three preceding sentences in the text. A corpus-based study measuring the referential distance and topical persistence of unmarked objects in Tangut is beyond the scope of this paper, but is an anticipated line of inquiry for future studies. 10. This paper follows Malchukov et al. 's (2010) distinction between secundativity and indirectivity. In Rgyalrongic languages, secundative and indirective verbs are distinguished through verbal morphology, see Table 5, and Lai (2017: 424-426;2021) for a detailed discussion. 11. Due to the neutralization of verbal inflections in Tangut texts (cf. Section 2.1), morphological indirectivity is not always obvious.

with a few Give-verbs, such as 𘓯 1105 khjow 1 ([B] 𘎾 5644 khjɨj 1 )12 'to give, grant' and 𘈈 2047 mji 1 'to grant' . The dative 𘋩 5447 do 2 is found with many other 'Give'-verbs, among which are 𗼒 2815 khu 1 'to tribute, consecrate' , or 𗨳 3175 tjị 1 'to return' (for a list of verbs selecting 𘋩 5447 do 2 , see Beaudouin 2021).

However, there are verbs of which the R can be marker with either the oblique 𗗙 1139 jij 1 or the dative 𘋩 5447 do 2 , as exemplified by the verb 𘎪 5612 tshiij 1 ([B] 𘀽 3974 tshjii 2 ) 'to say, speak ' . In Example (11), the addressee (R), Chen Zheng, is marked with 𘋩 5447 do 2 . ( 11 Note that in ( 12), the argument marked by 𗗙 1139 jij 1 is the addressee (R), as well as the beneficiary of the event. In the example above, extracted from the story of Goujian Miewu, King Goujian of Yue is faced with the threat of Wu's invasion and asks his minister Fan Li for counsel. The addressee, the King Goujian, is also the one who would benefit from the speaker's counsel. The alternating R marking in ( 11) and ( 12) is a potential indicator of prototypical semantic values of 𗗙 1139 jij 1 and 𘋩 5447 do 2 , a hypothesis which will be developed in Section 3.4.1.

Auxiliary causative

In Tangut, productive causativization is built with the auxiliary verb 𗟻 0749 phji 1 (Stem [B] 𗠔 4568 phjo 2 , cf. Table 2), originally a motion verb meaning 'to send' [START_REF] Arakawa | Seika-go no shieki ni tsuite [On the causative construction in Tangut[END_REF]Shi 2020: 290). The derived causative compound shows bipartite morphology, with the base verb and the causative auxiliary sharing TAM marking and argument indexation.

The case postposition 𗗙 1139 jij 1 is particularly frequent in Tangut auxiliary causatives. While previous studies (Arakawa 2019: 141-142;Kotaka 2000: 73;Shi 2020: 304) mention the optional presence of 𗗙 1139 jij 1 after the causee, case marking for non-subject arguments in causative compounds is more complicated. I distinguish three such situations below.

3.3.1

Optional causee marking with 𗗙 1139 jij 1 The syntax of causative compounds in Tangut distinguishes two situations according to the transitivity of the base verb.

Causative compounds derived from an intransitive base are bivalent, with the causer, the transitive subject (A), and the original S as the causee. In this case, the causee is also the syntactic object ([A causer , O causee ]). Both the causer and causee can be indexed on the verb. The causee optionally receives overt case marking with 𗗙 1139 jij 1 , in accordance with the same prominence-based rules observed for non-derived monotransitive verbs (cf. Section 3.1).

Example (13) shows a causative compound derived from the intransitive verb 𗈦 1336 lhạ 2 'be confused' . In addition being indexed (suffix 𘉞 4601 -nja 2 marks the causer, and the stem [B] form of the causative auxiliary reflects the causee), the causee, common people is also case marked with 𗗙 1139 jij 1 . ( 13 The postposition 𗗙 1139 jij 1 is not dedicated only to optional causee marking. Though infrequent, it is also possible for the oblique argument to be overtly marked with 𗗙 1139 jij 1 . As evidenced by ( 15 (Shi et al., 1993: 39) 文侯怒, 使人捕師經。 (Leilin, 03.06A.5) 'Wenhou became angry, and sent people to catch Shijing. ' Although the presence of 𗗙 1139 jij 1 can be explained by the discourse prominence of the argument Shijing as the protagonist of the story, we also notice that Shijing is the maleficiary, 13 affected by the causative event.

13. One of the reviewers points out that Examples (15) and ( 17) do not have a maleficiary in a typical sense, but a highly 'affected patient' . The suggestion is not adopted, since there is no clear morphological evidence indicating that the arguments marked by 𗗙 1139 jij 1 in the two examples are objects. Moreover, the term 'affectee' is avoided in the paper, as it is reminiscent of the theory of affectedness in DOM [START_REF] Naess | What markedness marks: The markedness problem with direct objects[END_REF]), which might be relevant to DOM in Tangut but is beyond the scope of the current paper. Terminological clarification is expected for future works, as the term 'affectee' is used as an umbrella term subsuming both beneficiary and maleficiary in Geshiza Horpa (Honkasalo 2019: 494-495).

[14] Shuya Zhang

Alternative causee marking with 𘋩 5447 do 2

There are very few examples in my corpus in which the causee is marked by the postposition 𘋩 5447 do 2 . One such example is given in ( 16). ( 16 The occurrence of 𘋩 5447 do 2 instead of 𗗙 1139 jij 1 after the causee in ( 16) could be motivated by semantic factors. In (16) Chunyu Zhi is not the argument affected by the causative event; it is the causer, Zhang Ben, asking after the fortune of his sick mother, who would benefit from the causative event. The functional overlap between 𗗙 1139 jij 1 and 𘋩 5447 do 2 in three-place predicates, including non-derived ditranstive verbs (Section 3.2) and causative constructions (Section 3.3) indicates potential semantic overlap in that they are goal-oriented. However, alternations after the R and the causee also suggest that they differ from each other semantically. The arguments marked by the yod postposition 𗗙 1139 jij 1 are also associated with the semantic role of a bene-/maleficiary, which is affected by the event denoted by the predicate. Therefore, I propose Figure 3 to illustrate the prototypical semantic values of 𗗙 1139 jij 1 and 𘋩 5447 do 2 in Tangut.

Interim summary

This hypothesis is tested in Example ( 17), which contains a verb-noun incorporated predicate 𘞝 0031 -𗢯 3190 dzjwɨ 1 -lhjwa 1 'to speak ill of ' . The predicate involves two non-subject arguments: King Fuchai, the addressee, marked by the dative 𘋩 5447 do 2 , and Wu Zixu, marked by 𗗙 1139 jij 1 . Although the syntactic status of the argumet marked with 𗗙 1139 jij 1 is ambiguous and could be either an object or an oblique, it is clear that Wu Zixu is the maleficiary, affected by the action of Minister Pi's slandering.

14. Shi et al. (1993: 132) provided a nearly word-to-word translation, 張本就淳于智處卜, in which 𘋩 5447 do 2 is translated as 處 chù 'place' , reminiscent of its original allative function. From the context we know that Zhang Ben seeks divination from someone skilled, Chuyu Zhi. The ambiguity here is in line with the functional continuum of 𘋩 5447 do 2 after an NP human, ranging from the endpoint of a motion to an abstract goal. For a detailed account of the grammaticalization of 𘋩 5447 do 2 , see [START_REF] Beaudouin | Localiser en tangoute: entre continuums et bipartitions[END_REF].

The history of the polyfunctional 𗗙 jij 1 15. Kepping (1985: 229-230) also mentioned the occurrence of 𗗙 1139 jij 1 after intransitive subjects. Due to a scarcity of examples, the phenomenon is still unclear and should await further studies. Optional intransitive subject marking also exists in other Tibeto-Burman languages. In Lhasa Tibetan, the dative can optionally occur after intransitive subjects, which could be related to both event semantics of controllability and information structure (Simon 2016: 340-341). On the other hand, the use of a subject marker for objects is also observed sporadically, for example in Burmese, for which Chappell & Verstraete (2019) suggest a possible reanalysis of a relevant morpheme as a general marker of information structure. In addition, I also found optional T(heme) marking with very few ditransitive verbs in my corpus. These may be described as examples of [START_REF] Kittilä | Object-, animacy-and role-based strategies: A typology of object marking[END_REF] 'extended differential object marking' . Both phenomena remain to be investigated with a larger corpus.

The most active range of 𘋩 5447 do 2 lies in the non-indexable interval. As Beaudouin (2021) remarks, within the source function of allative (i.e. goal of motion verbs), 𘋩 5447 do 2 already shows a preference to combine with human participants, which suggests a clear grammaticalization from allative to dative.

In contrast, 𗗙 1139 jij 1 shows a decreasing distribution from indexable to nonindexable functions. There is no internal evidence from Tangut suggesting a spatial related source for 𗗙 1139 jij 1 , except for the fact that it is goal-oriented (cf. Figure 3). Furthermore, it is also difficult to suggest any directionality between the accusative and the genitive, although there are cases where 𗗙 1139 jij 1 exhibits a genitive/oblique ambiguity (see Section 4.1.2 for the same phenomenon in modern Rgyalrongic). In general, reanalysis of possessors as accusatives is typologically rare, and is considered counter-directional grammaticalization (Narrog 2014: 80).

The following sections examine comparative data from modern Rgyalrongic languages, in hopes of unveiling the origins of the postposition 𗗙 1139 jij 1 and explaining genitive/accusative syncretism.

Cross-Rgyalrongic comparison

The Tangut 𗗙 1139 jij 1 reflects the Proto-Rgyalrongic yod postposition *=j(V) (Jacques 2014: 210). Reflexes of this postposition are still productive in modern West Rgyalrongic languages and Situ Rgyalrong (i.e. the eastern branch). 16 However, the yod postpositions in these modern relatives of Tangut function very differently. In modern West Rgyalrongic languages, the yod postpositions show a genitive/oblique syncretism (Section 4.1), and those in Situ basically function as general locatives (Section 4.2).

Despite their functional differences, the productive uses of the yod postpositions in modern Rgyalrongic languages can offer clues to possible sources of the Tangut 𗗙 1139 jij 1 and the associated genitive/accusative syncretism discussed in Section 5.

Modern West Rgyalrongic: Genitive/oblique =jV

The yod postpositions in modern West Rgyalrongic languages present genitive/ oblique syncretism. For the genitive function, =jV serves to express adnominal 16. Japhug (Northern Rgyalrong) preserves traces of the yod locative. The word qhuj 'tonight' is potentially a fossilized locative form of the relator noun ɯ-qhu 'after' (Jacques 2021: 330-331).

The history of the polyfunctional 𗗙 jij 1 in Tangut [17] possession, as exemplified in (18). This clearly corresponds to the Tangut genitive 𗗙 1139 jij 1 (e.g. Example 6).

wobzi khroskyabs (west rgyalrongic) (18) genitive =ji

[tʂɑɕî] PR =ji pn:Bkra.shis=gen

[pîr] PE pen (Lai 2017: 185) 'Bkrashis' pen'

The oblique function of the yod postposition should be understood with respect to verb classification in modern Rgyalrongic languages (cf. Table 5), which is strictly based on morphological transitivity (i.e. indexation patterns) and case frames. In general, three non-subject categories can be distinguished, (i) the accusative (i.e. the indexable O), (ii) the dative, which is in most cases nonindexable, but is indexable with secundative verbs, and (iii) the oblique, which is non-indexable.

In the non-indexable domain, we also notice competition between the dative and the oblique in marking extended arguments in two constructions: (i) extended intransitive verbs, and (ii) indirective verbs.

Extended intransitive verbs

The dative that marks extended arguments shows idiosyncratic distribution, and is found with verbs such as 'to help' (ɣə̂r in Khroskyabs, ɣor in Geshiza), 'to fear' (nscə̂r in Khroskyabs, stɕaer in Geshiza) (Honkasalo 2019: 472;Lai 2017: 234-235).

[18] Shuya Zhang

The distribution of the oblique =jV is rarely idiosyncratic, and is associated with a predictable semantic role of experiencer (Honkasalo 2019: 494). It is typically found with stative verbs, alternating between basic intransitive [S=ø] and extended intransitive [S=ø, E=obl]. 17 This is exemplified by the modal verb ró 'be necessary, should' in Khroskyabs, which is intransitive and basically involves an impersonal subject, as in (19a). It can be 'supplemented' with an additional nonsubject argument marked by the oblique =ji, expressing the meaning 'to want, need; be necessary to ' , as in (19b)

Indirective verbs

The dative is the most important means for R marking. It occurs after the R of all secundative (e.g., 'to feed': Khroskyabs bə̂, Geshiza mə) and most indirective (e.g., 'to ask': Geshiza rjae, Khroskyabs rɣǽ) verbs in modern West Rgyalrongic languages. Only a small proportion of indirective verbs with their R marked by the oblique, are typically associated with the semantic role of a bene-/maleficiary (Honkasalo 2019: 494-496). First, manipulation verbs (e.g. Khroskyabs vǽ 'to bring' , tʰǽ 'to take away (to)'; Geshiza mbe 'to carry away' , nʑae 'to bring' are subsumed under a larger semantic class of orientable verbs, further details of which are discussed in Section 4.2) consist a particular subtype of indirective verbs in Rgyalrongic languages. They denote an induced motion, the R of which can be understood as an abstract goal intrinsically required by the verb's semantics. As in (20), the oblique =je, merged with plural marker ɲi, serves to mark the R of the verb nʑae 'to bring' . 17. Productive alternations between intransitive and extended intransitive could ultimately give rise to idiosyncrasies. The Geshiza verb ɖʐaen 'to miss (someone)' , requiring an experiencer marked by the oblique =je (Honkasalo 2019: 468) Second, the oblique can occur with a group of monotransitive verbs which do not denote a motion event, and optionally 'supplement' a third argument acting as the bene-/maleficiary of the denoted action (Honkasalo 2019: 483). In ( 21), the yod postposition =je supplements a beneficiary, the Balang villagers, of the action denoted by the verb v-qʰlə 'to divide' . (Honkasalo 2019: 495) and divided it for Balang villagers. ' Some transitive verbs can be extended to become quadrivalent, associating with three non-subject arguments: a non-casemarked Theme, a Recipient marked with the oblique, and a Source argument marked with the dative (Lai 2017: 187;Honkasalo 2019: 485-486). In ( 22), with the manipulation verb (rə)-vǽd (Stem II zə́m) 'to bring' in Khroskyabs, the dative =kʰe yields an ablative reading and marks the source of the transfer event. The ablative reading, which seems to be semantically contradictory with the dative one, originates from its original adessive function 'near, at the place of…' (Lai 2017: 187) 22) the yod postposition =ji is ambiguous due to the contiguity of the R and the T and could be either an oblique (encoding the beneficiary) or a genitive (encoding the possessor), its goal-oriented property is obvious, and the inverse case alignment is ungrammatical.

Situ Rgyalrong: General locative =j

The yod postposition occurs in a non-syllabic form =j in most Situ dialects (Lin 1993: 325-330;Lin 2017: 63-64;Prins 2016: 259-260;Zhang 2020: 339-341;etc.). Like its syllabic cognates =jV in the West branch, it also operates at the phrasal level. 18 As a general locative, =j in Situ has two identifiable interpretations: as a locative expressing stative location (e.g. ( 23a)) and as an allative indicating the end point of a motion (e.g. ( 23b)). The allative reading is triggered with orientable 19 verbs, including (i) motion verbs such as 'to go' and 'to come' , (ii) manipulation verbs denoting an induced motion, such as 'to take' , and (iii) orienting verbs denoting a fictive motion. These verbs morpho-syntactically require a goal argument obligatorily marked with the locative. 23a); (23b)), or as an adjunct. Two locative phrases can occur successively, with an 'outer' locative adjunct providing background information and preceding an 'inner' locative, as in (24). Note that though not obligatory, the 'outer' locative is followed by the prominence marker kə, which developed from an ergative source (Prins 2016: 217-237;Zhang 2020: 25-26).

18. In some varieties, the yod postpositions develop new functions as clause subordinators. The Khroskyabs =ji has developed the function of a relativizer from a genitive [START_REF] Lai | Relativisation in Wobzi Khroskyabs and how genitivisation enters it[END_REF]. In Brag-bar (Situ), the locative =j can occur after nominalized adverbial clauses. 19. Orientable verbs in Rgyalrongic languages constitute a semantic class exhibiting distinct morphological behaviors. While most verbs have one or two directional prefixes which have lexicalized for the perfective and imperative as pure tame markers, orientable verbs are free to select directional prefixes, encoding both spatial orientations and tame values. See Zhang (2020: 369-399) for details on directional prefixes and orientability in Situ, and Jacques (2021: 621-681) for the Northern branch. The general locative =j in Situ has various non-spatial uses, all of which are related to the two syntactic positions of adjunct and oblique.

Delimitative adjuncts

The yod postposition =j in Situ can be used to encode sentence topics, roughly equivalent to English 'as for' topics. This function originates from the clauseexternal function of the locative =j, which is typically associated with the sentence initial position, as exemplified in (25). ipfv.pst-be II ' As for each catty (of Iris), it sells for about one or two yuan. '

Oblique

The oblique function of the Situ locative =j is similar yet not identical in terms of its distribution to the oblique =jV of modern West Rgyalrongic languages.

As shown in Table 6, the Situ locative =j is mainly found in constructions with (i) extended intransitive and (ii) indirective verbs. The locative and the dative also compete in the marking of extended arguments in these two constructions. However, the Situ dative wo-phá=j is only a semi-grammaticalized locative phrase, comprising (i) a possessive prefix, pronominally representing the possessor, (ii) a nominal base *pha 'vicinity' , 20 and (iii) the yod locative =j. 21

Extended intransitive verbs

With extended intransitive verbs, the Situ =j functions in the same way as does the oblique =jV in modern West Rgyalrongic languages (Sections 4.1.1). The yod locative =j in Situ is also found with stative verbs, to which it optionally introduces an experience (e.g. kə-râ V[S=ø] 'be necessary'; V[S=ø, E=loc] 'be necessary to').

20.

Reconstruction of this root awaits further revision. Dative relator nouns within Situ show irregular correspondences, with an aspirated labial ph-in Brag-bar wo-phá=j, and a softened labial approximant w-in Cogtse wə-wâ=j (Lin 2016: 20). 21. In Brag-bar the yod locative can be replaced or followed by the locative tɕɐ in Brag-bar (Zhang 2020: 345). In Cogtse it can be replaced by the sibilant locative =s [START_REF] Lin | Jiāróngyu ̌ Zhuókèji ̄huà yu ̌fǎ biāozhu ̀ wénběn [Cogtse Rgyalrong texts: Fully analyzed spontaneous narratives with an updated sketch grammar of the language[END_REF].

[22] Shuya Zhang

V[A,O] A(=erg) O=ø Secundative ditransitive V[A,R=O] A(=erg) T=ø R=ø Indirective ditransitive V[A,T=O] A(=erg) A(=erg)
O=ø T=ø R=dat R=loc

Indirective verbs

A major distributional difference between the locative =j in Situ and the oblique =jV in modern West Rgyalrongic languages exists in ditransitive constructions.

With indirective verbs, the Situ locative =j is reserved for manipulation verbs intrinsically involving a goal argument. The argument marked by =j can either be the concrete goal of motion, or the abstract goal of a bene-/maleficiary (typically a human participant). As exemplified by ( 26), =j marks the maleficiary of manipulation verb ka-sə-bʑê 'to induce (a disaster)' , derived from the cislocative verb kabʑê 'to come' with the causative prefix sə-.

brag-bar situ (26) wo-ŋkhú=j 3sg.poss-after=loc təɟə̂=j oneself=loc máksən like.that ma-kə-bdɐn eg-ptcp:s/a-be.good ɲo pl ma-ka-nə-sə́-bʑe neg-inf-autoben-caus-come wo-rɟô 3sg.poss-words nə́-ŋɐs. sens-be I '(This story is about) not bringing bad things to oneself in the future. ' Unlike modern West Rgyalrongic languages (Section 4.1.2), the yod postposition in Situ is not available for non-orientable monotransitive verbs, such as 'to buy' , or 'to divide' , since they do not intrinsically involve a goal argument. For these verbs, bene-/maleficiary encoding relies on pronominal possessive prefixes. As in ( 27), the beneficiary of the action of buying is encoded by pronominal possessive prefixes, with ŋə-occurring on the theme, which is indexed on the verb as the syntactic O.

brag-bar situ (27) ka-kî 'to buy' (2sg→3)

The history of the polyfunctional 𗗙 jij 1 The restriction of locative encoding of bene-/maleficiary to orientable verbs in Situ reflects a very common extension of the allative; from a concrete goal to an abstract goal (cf. Heine 2009).

Locative =j and possession

In core Rgyalrong languages, possession is predominantly expressed through prefixing morphology. Most nouns are inalienably possessed, lexically taking an indefinite possessive prefix tə-or ta-. Definite possession is expressed by replacing the indefinite possessive with a set of pronominal possessive prefixes (cf. Jacques 2021: 108; Zhang 2020: 27; etc.). The possessive prefixes occur on the possessee NP, and agree with the person and number of the possessor, which can often be omitted, for instance: brag-bar situ [START_REF] Gong | Xīxià yǔ dòngcí de rénchēng hūyìng yǔ yīnyùn zhuǎnhuàn [Personal Agreements and Phonological Alternations in the Tangut Verb[END_REF] tə-mí → (ŋá) ŋə-mí poss.indf-daughter 1sg 1sg.poss-daughter 'daughter (default form)' 'my daughter'

In addition to the prevailing prefixing possessive, the locative =j in Situ can also serve to express possession in three constructions, as discussed below.

Locational possessive

One important function of the locative-existential clauses in Situ is to express the 'locational possessive' (cf. Stassen 2009: 49-50). 22The locational possessive in Situ comprises three elements: (i) the existential predicative ndó 'exist' , occurring in an invariant form; (ii) the possessor (pr), occurring as an oblique argument, marked by the locative =j; and (iii) the possessee (pe), which is the intransitive subject of the existential copula, as in (29). Note that the possessee NP does not agree with the possessor NP in this example, and occurs in its default form with the indefinite possessive prefix tə-. The distribution of the locational possessive varies across Situ dialects. For instance, it is used for kinship relations in Cogtse Situ (Lin 1993: 49-50), but such uses are not attested in Brag-bar Situ.

Locative pronouns

In Situ, the locative =j can be directly attached to personal and interrogative pronouns, causing them to function like possessive pronouns (Nagano 2018: 165-166;Prins 2016: 121;etc.). Situ locative pronouns often occur in equative copula clauses, and serve to emphasize a possessive relationship (Lin 1993: 329).

For instance, in (30), the singular first person locative pronoun ŋá=j appears with the equative copula ŋɐ̂s 'be' . The construction expresses a meaning similar to the dative possessive in French (c'est à moi). (Zhang 2020: 341) 'That (burden) on my back is as heavy as (the one) on you. '

'Double marking'

Situ also has a 'double marking' pattern, in which the possessor has an encliticized locative =j, and is indexed on the possessee NP with a possessive prefix. As in (32), the possessor NP, tə-rmî ɲo 'people' , is both case marked by the yod locative =j, and pronominally represented on the possessee NP by the plural third person possessive prefix ɲi-. ifr-be I ' After that, he made human food like that. '

As Heine (1997: 148) remarks, the phenomenon of 'double marking' of a possessor could be related to a 'Topic Schema' '(As for X), X's Y' . As for Situ, the double encoding of possessors might have originated in constructions in which a possessor is also encoded as a sentence topic. In (33), the possessor NP marked by the locative occurs as the sentence topic. The possessive prefix ɲi-occurring on the possessee NP reflects the person and number of the topic possessor, and serves as morphological evidence that distinguishes the Topic possessive (33) from the Locational possessive (cf. Section 4.2.3.1). In (33), the sentence topic and the possessee NP are separated by the optional determiner tə, which is used as a contrastive marker. The absence of this element could easily lead to contiguity of topic possessor and possessee, resulting in the 'double marking' pattern.

brag-bar situ

Multi-directional development of the yod postposition

The unidirectionality hypothesis of grammaticalization predicts increasing grammaticalization from spatial concepts to more abstract case functions (Heine et al. 1991: 156). Among the three Rgyalrongic branches discussed in this paper, it is appropriate to postulate that the Situ locative represents one of the more archaic uses of the Proto-Rgyalrongic yod postposition. The yod postposition's development towards genitive/oblique syncretism in modern West Rgyalrongic, and towards genitive/accusative syncretism in Tangut can be explained through two main grammaticalization pathways. They are summarized in (34).

(34) a. From allative to accusative (Section 5. [START_REF] Meyer | The morpheme yä-in Muher[END_REF] b. From locative to genitive (Section 5.2)

From allative to accusative

The promotion of the Proto-Rgyalrongic yod locative postposition to an accusative could have occurred in two steps. First, the allative was reanalyzed as an oblique case in Proto-West Rgyalrongic (Section 5.1.1), then the oblique was further promoted to an accusative in Tangut (Section 5.1.2).

From allative to oblique in West Rgyalrongic

One of the major functions of the oblique case =jV in modern West Rgyalrongic languages is to mark bene-/maleficiaries in indirective constructions (cf. Section 4.1.2). This function is also attested with the Situ locative =j as an extension of its allative function, albeit with a slightly different distribution (cf. Section 4.2.2.2). The transition from the Proto-Rgyalrongic allative function to the West Rgyalrongic oblique function (with bene-/maleficiary related meanings) may have involved: (i) the loss of the original spatial meaning, and (ii) reanalysis of the allative as a marker of bene-/maleficiaries. This hypothesis finds support in the morpho-syntactic properties of motion verbs in West Rgyalrongic languages, which alternate between semitransitive, taking an unmarked goal argument ([S=ø, E=ø]), and extended intransitive, with a postpositional goal argument ([S=ø, E=post]) (cf. Table 5). At the synchronic level, differential goal marking is regulated by semantico-pragmatic factors: default goals are unmarked (e.g. (35a)), and overt marking occurs when there is a need for topological specification (e.g. ( 35b), (35c)). 35a)) correspond to strict locative marking in Situ (Section 4.2), and can be considered to represent a gap left by the loss of the original allative (spatial) function of the yod postposi-tion. 23 However, the yod postposition =jV did not completely disappear following the goal arguments of motion verbs in West Rgyalrongic languages. Rather, it is restricted to human goals. In [START_REF] Zhang Chappell | Optional and alternating case marking: Typology and diachrony[END_REF], the yod postposition =ji occurs after a human goal, which can be understood as a metaphorical goal of the fictive motion denoted by the verb və̂a 'to go' , which in this case can be translated to 'to go well with, to fit' . khroskyabs (west rgyalrongic) [START_REF] Zhang Chappell | Optional and alternating case marking: Typology and diachrony[END_REF] 36) also helps to explain its occurrence in ditransitive constructions with manipulation verbs (cf. Section 4.1.2). On the one hand, manipulation verbs are orientable and intrinsically include a goal argument; on the other hand, the R of a ditransitive construction is often a human participant. Under these circumstances, in extending to non-orientable verbs, such as 'to buy' , it is likely that =jV develops into a genuine bene-/maleficiary marker.

khroskyabs (west

(37) Therefore data from modern West Rgyalrongic languages support an increasing grammaticalization from allative to oblique, with bene-/maleficiary related functions (as summarized in 37); a typologically frequent grammaticalization pathway (Heine et al. 1991: 151;[START_REF] Heine | Grammaticalization of cases[END_REF][START_REF] Narrog | The grammaticalization chain of case functions: Extension and reanalysis of case marking vs. universal of grammaticalization[END_REF]etc.).

Promotion of oblique to accusative in Tangut

Although it is widely accepted that the dative is a transit stage for the second grammaticalization of a spatial case to the accusative (cf. Section 1.2), the promotion of the Proto-West-Rgyalrongic oblique to the Tangut accusative seems to be an exception.

23.

In Situ, topological specifications are realized by locative phrases based on spatial relator nouns such as wo-liɛ́=j 'in the middle of ' . Despite the semantic discrepancy, in West Rgyalrongic languages, some spatial case postpositions with topological specification have transparent sources cognate with spatial relator nouns in Situ. For example, Khroskyabs =lɑ 'locative:inside' is cognate with Brag-bar wo-liɛ́'middle' , and =gə 'loctaive:inside' with Brag-bar wo-ŋgú 'inside' .

The yod postposition did not develop into a dative in any modern Rgyalrongic languages; on the contrary we observe that datives developed independently in different branches: (i) Khroskyabs and most Horpa languages have velar datives [START_REF] Honkasalo | A grammar of Eastern Geshiza: A culturally anchored description[END_REF][START_REF] Gates | A grammar of Mazur Stau[END_REF][START_REF] Lai | Grammaire du khroskyabs de Wobzi[END_REF][START_REF] Sun | Huò' ěr yǔ géxī huà dòngcí duìxié[Verb agreement in Gexi Horpa[END_REF]; (ii) the Horpa of Stodste and Rtsangkhog have a dental dative =do [START_REF] Sun | Morphological causative formation in Shangzhai Horpa[END_REF][START_REF] Lai Lai | Jiāróngyǔzǔ yǔyán dòngcí de fēnlèi -yǐ Chuòsījiǎ (Lāwùróng) yǔ wéilì[The classification of verbs in Rgyalrongic languages, from a Khroskyabs perspective[END_REF]) cognate with the Tangut allative/dative 𘋩 5447 do 2 ; (iii) Situ has less grammaticalized dative relator nouns (cf. Section 4.2.2). This formal diversity suggests that dative as a dedicated case category was formed very late in Rgyalrongic languages. In Tangut, it is unclear whether or not 𗗙 1139 jij 1 underwent a dative stage. Its limited occurrences after the R of non-derived ditransitive verbs still fall within the functional domain of the oblique.

An alternative hypothesis is that the Tangut accusative developed from oblique. This development is likely to have been realized via bridging syntactic constructions involving argument promotion, such as the auxiliary causative (cf. Section 3.3). For one thing, the causative auxiliary in Tangut 𗟻 0749 (stem [B] 𗠔 4568 ) is originally an orientable verb which means 'to send' and syntactically involves a goal argument. Therefore, the optional causee marking with 𗗙 1139 jij 1 can be considered to have been initially driven by semantics properties, and in particular by humanness, as observed with =jV in modern West Rgyalrongic languages (e.g. Example 36). For another, since the auxiliary causative in Tangut is an argument promotion mechanism, it can promote the causee, which can be marked by the yod postposition, to a syntactically indexable O. In this case, 𗗙 1139 jij 1 , which was originally a marker for a human goal, would have been reanalyzed as an accusative marker.

Since an auxiliary causative based on a motion verb is Tangut innovation and is not found in any other Rgyalrongic languages, this also explains why the yod postposition did not develop an accusative in other West Rgyarongic languages.

Information structure and accusative marking

Unlike the Romance languages, where DOM first emerges as a topic marking device [START_REF] Iemmolo | Towards a typological study of differential object marking and differential object indexation[END_REF], information structure is likely to have been a contributor in the grammaticalization of the yod postposition in Rgyalrongic languages.

The existing data only allow us to speculate that information structure may have promoted the spreading of DOM in Tangut. In modern West Rgyalrongic, the two semantic roles that are associated with the oblique =jV, the experiencer and the bene-/maleficiary, are typically human and definite. Although Tangut DOM shows a strong tendency to appear with human and definite objects, it is not limited to them. Tangut DOM can potentially be grouped into the Type 3 of Dalrymple & Nikolaeva's (2011: 215) typology, wherein DOM first applies to topic and non-topic arguments with the semantic features of human and definite, and then spreads to other topic-worthy arguments. Needless to say, the relationship between information structure and DOM in Tangut is worthy of further study.

From locative to genitive

Since the genitive function of the yod postposition is shared by all West Rgyalrongic languages, reanalysis from the locative as a genitive should predate the West-Rgyalrongic split.

Reanalysis of spatial and directional markers as genitives is a typologically frequent occurrence (Heine 1997: 145;Stassen 2009: 122). For the Rgyalrongic languages, the reanalysis of a locative as a genitive could be the result of multiple different pathways. Among the five source schemes that Heine (1997: 144) postulates for the expression of attributive possession, at least two (i) the Location Schema (Y at X), and (ii) the Topical Schema (as for X, X's Y ) that are relevant to the present discussion. Both schema involve the reanalysis of constituency (Stassen 2009: 113-135): two noun phrases occurring in adjacency in an original predicative possessive construction are reanalyzed as a single noun phrase, with the preceding noun phrase becoming the adnominal modifier of the subsequent noun phrase.

Location schema

The locational possessive, as observed in Situ (cf. Section 4.2.3.1), is the bridging construction which has allowed the reanalysis of a locative possessor as a genitive in West Rgyalrongic.

As illustrated in [START_REF] Zhang Malchukov | Ditransitive constructions: A typological overview[END_REF], due to the contiguity, the locative possessor, originally an oblique argument, is reanalyzed as an adnominal modifier of the subsequent possessee, which is the original subject of the copula predicate. A locational possessive with the yod postposition can be traced back to Proto-Rgyalrongic. Tangut has a dozen existential verbs [START_REF] Ikeda | Verbs of Existence in Tangut and Mu-nya[END_REF]Shi 2020: 318-355), among which 𘟣 0930 dju 1 , a common Rgyalrongic etymon (cognate with Khroskyabs də́, Situ ndó), demonstrates idiosyncratic combination with the yod

[30] Shuya Zhang postposition when expressing possession (Kotaka 2000: 74;Ikeda 2012: 196), as evidenced in [START_REF] Sun | Morphological causative formation in Shangzhai Horpa[END_REF]. 24 [START_REF] Sun | Morphological causative formation in Shangzhai Horpa[END_REF] The transition from stage (41b) to (41c) was achieved through the loss of possessive prefixes, which is a shared morphological innovation of the West branch. Although there are no clear traces of personal possessive prefixes left in any West Rgyalrongic languages, indefinite possessive prefixes *tV-can be found as fossilized preinitials in a few lexical forms, such as the preinitial t-in Khroskyabs tvə' fist' (Proto-Khroskyabs *t[ə]-C.kut, Lai 2017: 155), cognate with Brag-bar Situ tərkút.

24. Tangut has another locational possessive predicated by the existential verb 𘂬 5670 o 1 , but the locative possessor is encoded by the general locative 𘕿 5856 ɣa 2 . Heine (1997: 146) also suggests a Goal Schema, namely a unidirectional grammaticalization from markers of allative, dative, or benefactive to genitive. Yet in West Rgyalrongic languages, it is not clear whether the bene-/maleficiary meaning historically precedes the genitive meaning.

Beneficiary possessor

Bene-/maleficiary encoding for non-orientable verbs with the yod postposition may have been a simple analogy from orientable verbs, and a side effect of the increasing grammaticalization of the allative in West Rgyalrongic (Section 5.1.1). However, we cannot preclude an alternative hypothesis that the newly developed genitive =jV occurs in compensation for the loss of possessive prefixes in West Rgyalrongic. Note that Core Rgyalrong languages use the possessive prefixes to encode the bene-/maleficiary of non-orientable verbs (cf. Section 4.2.2.2, see also Jacques 2021: 112-113, 317 for Northern Rgyalrong languages). The ambiguity between the bene-/maleficiary and genitive always exists.

Figure 4 summarizes all the assumed historical developments of the yod postposition in Rgyalrongic languages presented in research to date.

Conclusion

This paper explained the historical development of a polyfunctional case marker 𗗙 1139 jij 1 in Tangut, and attributed its genitive/accusative syncretism to multiple grammaticalization from a proto general locative case. This syncretism appears confusing in Tangut owing to the complete loss of the original locative function, which can only be reconstructed through comparison with more conservative sister languages (Section 4).

The two main grammaticalization pathways assumed in this paper, from allative to accusative, and from locative to genitive with the help of constructional change (Section 5), confirm the hypothesis of unidirectional grammaticalization [START_REF] Heine | Grammaticalization: A conceptual framework[END_REF]. Grammaticalization from a spatial concept to an accusative, and to a genitive are both recurrently attested. However, the case of Tangut shows that typological rarity can also arise through the layering of various well-attested grammaticalization pathways.

The Tangut case can contribute to typological studies of case functions in at least two ways. First, it seems that Tangut, together with Gurage languages and Tshangla, can be classified as demonstrating maximum syncretism of abstract case functions (oblique/dative, accusative, genitive). They can also be classified as a new subtype of Type 2 case syncretism (between a core case and a non-core case) in [START_REF] Baerman | Case syncretism[END_REF] typology.

Second, the development of postpositional accusative marking in Tangut, as well as in modern West Rgyalrongic languages, challenges the 'function continuity' hypothesis, that states 'If an adposition occurs as both Object marker and Allative marker, it also occurs as Dative marker' (Blansitt 1988: 186). Dedicated dative markers were formed after the branching-off of West Rgyalrongic, since in Core Rgyalrong the dative is expressed by semi-grammaticalized relator nouns; even inside the West branch etymological diversity of dative postpositions can be observed. In Tangut, it is unclear whether a dative stage preceded the accusative in the increasing grammaticalization of 𗗙 1139 jij 1 . Postpositional accusative marking also emerges in modern West Rgyalrongic languages. In Khroskyabs, objects of transitive verbs denoting actions involving surface contact are marked by the superessive postposition =tʰɑ [START_REF] Lai | Grammaire du khroskyabs de Wobzi[END_REF]. In Dgebshes Horpa [START_REF] Sun | Huò' ěr yǔ géxī huà dòngcí duìxié[Verb agreement in Gexi Horpa[END_REF] and Mazur Stau [START_REF] Gates | A grammar of Mazur Stau[END_REF], the locative/allative =ʁɑ is developing towards an object marker. In both cases, the relevant morphemes have not passed through a dative stage.

One final remark should be made concerning the diachronic development of morpho-syntax in Rgyalrongic languages. In West Rgyalrongic languages, we observe a correlation between the simplification of verbal inflections and the emergence of dependent marking. Prevailing optionality is observed with case marking in Tangut, which has the most innovative and simplified verbal system (a few other cases of optional object marking are reported in Horpa, which has also undergone a partial collapse of its verbal system, cf. Gates 2021; Honkasalo 2019). Lexicalized case frames developed in Khroskyabs, a language which well preserves the verbal inflections. If we assume that adposition case marking emerges in compensation for the disintegration of old inflectional systems, as [START_REF] Bossong | Differential object marking Romance and beyond[END_REF] hypothesized for the Romance and Semitic languages, then the factors leading to optionality, as found in Tangut, and split marking, as found in modern West Rgyalrongic, are still in need of investigation.

Figure 2 .

 2 Figure 2. Stammbaum of Rgyalrongic languages[START_REF] Sun | Parallelism in verb morphology of Sidaba Rgyalrong and Lavrung in Rgyarongic[END_REF][START_REF] Lai | Tangut as a West Rgyalrongic language[END_REF]

3. 4 . 1

 41 Prototypical semantic values of 𗗙 1139 jij 1 and 𘋩 5447 do 2

  grandsons are at home. ' b. Allative: endpoint of a motion [a-tiɛ́=j] prox-up=all rɐ-bʑê-n imp:up-come I -2sg (Lit: come to the upper part) 'Come up. ' Locative phrases in Situ often occur in one of the two syntactic positions: as an oblique argument (e.g. (

  farm=all na-tɕhê-n imp:down-to.go I -2sg '(You) go down to the farm at Kyom-kyo. '

  three houses (Lit: to me, there are three houses)'

  is mine. 'The possessive reading of locative pronouns could have originated from the structures where the figure is omitted, and the locative phrase has a contextual referential status, as in (31).

  Somang (people), they had their (own) king. '

( 38 )

 38 Genitive possessive reanalyzed from locational possessive a. Locational possessive [pr=loc] [pe] [cop.ex] b. Adnominal possessive [pr=gen pe] ([cop.ex])

Figure 4 .

 4 Figure 4. Diachronic development of the yod postposition in Rgyalrongic Languages

Table 1 :

 1 (i) the verb stem (including noun-verb and verb-verb compounds), (ii) verbal prefixes, including directional prefixes, encoding TAM values as well as certain orientation meanings (cf. Arakawa 2012; Beaudouin Accepted), negation, and other modal prefixes, and (iii) argument indexation suffixes (cf. Jacques 2011;[START_REF] Kepping | Subject and Object agreement in the Tangut Verb[END_REF]).

Table 1 .

 1 . As shown in Table 2, the verb 𗟻 0749 phji 1 has a distinct stem [B] 𗠔 4568 phjo 2 , showing vowel alternation with the basic stem [A]. Jacques (2009) hypothesizes that vowel alter-nations in stem [B] originate from a third person patient suffix *-w (well attested in modern Situ, see Prins 2016: 390), which merged with the basic stem [A]. Simplified verbal template of Tangut (based on[START_REF] Jacques | The Structure of the Tangut verb[END_REF]Jacques , 2014: 266) : 266)

	(4) Reconstructed stems of 'to send, cause to do'
			Tangut	Pre-Tangut	(Jacques 2014: 84)
	Stem [A]	𗟻 0749 phji 1	*phja
	Stem [B]	𗠔 4568 phjo 2	*phja-w
	Directional			Noun	Verb
	prefixes		Negation Modal	stem	stem Auxiliary Person	tame
	dir1:	𗈪 5981	𗅋 1918
	pfv	a-	mji 1 -
		𗱢 1452	𘖑 5643
		nja 1	mjɨ 1

Table 2 .

 2 Person indexation of 𗟻 0749 phji

1

(stem [B] 𗠔 4568 phjo 2 ) 'to send, cause to do'

(Gong 2017: 31)

  5306 𘝦 5604 𘃡 5113 𗴢 3419 𘇒 4063 𘉁 1979 𗁦 3506 𘓺 0510 𘜹 4447 𗞞 4342 𗨻 2226 [dzjwɨ 1 =dʑjɨ.wji 1 emperor=erg

	bjuu 1 -wier 1 ]	[mjii 1	bjịj 1 ]	[ŋwǝr 1 .dzow 1
	to.respect-to.cherish	rank	to.raise	empress
	dja 2 -we 2 ]
	dir1:pfv-to.become
	' …The Emperor respected and loved her, and elevated her rank, she became
	the empress. '		(Cixiaozhuan, Jacques 2007: 103)

Table 3 .

 3 Tangut case system (adapted from Beaudouin 2021)

		Abstract cases	Spatial cases	Non-spatial cases
	𘝦 5604 𘃡 5113 dʑjɨ .wji 1 Ergative	𘋩 5447 do 2	Allative	𗳒 5880 ŋwu 2 Instrumental
	𗗙 1139 jij 1	Genitive	𘕿 5856 ɣa 2	Locative	𗑠 4950 rjir 2 Comitative
	𗗙 1139 jij 1	Accusative, oblique 𗅁 2983 u 2	In-essive	𗖵 0433 bju 1 Instrumental
	𘋩 5447 do 2	Dative	𘂤 5993 kha 𘇂 1136 gu 2	Med-esssive
			…	…

1

Mid-essive 𗸒 1473 su 1 Comparative 𗀔 0089 tɕhjaa 1 Super-essive 𗯴 5399 khju 1 Sub-essive

𘝨 4861 𘋨 5306 𘊶 3894 𘓺 0510 𘁤 5549 𗩍 2221 𗷬 1449 𘝦 5604 𘃡 5113 𗾞 2440 𗇸 1421 𘓐 2541 𗖌 0448 𗞞 4342 𗜍 4225 zjọ 2 time

  ) 𗕾 1484 𗍁 0289 𘓐 2541 𘝦 5604 𘃡 5113 𗉋 1259 𗺉 4018 𗗙 1139 𗞞 4342 𗜍 4225

	instance, it is a non-topical object mentioned in an account as incidental informa-
	tion at the ending of a story. 9
	(9) 𘜶 4456 𗂸 3508 𗁡 2923 𘂆 5815 𗜍 4225
	[tha 2 .bji 2	phji 1 ] O	tsjɨ 1	sja 1
	Minister	Pi		also	kill
	又殺大臣嚭					(Shi et al. 1993: 55)
	'(Finally, the King of Yue destroyed the country of Wu, exiled the King Fuchai
	of Wu) also killed the Minister Pi. '	(Leilin, 03.22A.1)
	[kju 1 .we 2	dzjwo 2 ] A =dʑjɨ.wji 1	[tɕiow 1 .tɕhji 2 ] O =jij 1	dja 2 -sja 1
	Ju.city	people=erg	pn:Zhuochi=acc	dir1:pfv-to.kill
	莒城人殺卓齒。			(Shi et al., 1993: 79)
	'The people of Ju city killed Zhuochi. '	(Leilin 04.08A.3)
	(8) [dzjwɨ 1	njɨ 1	ŋwǝr 1 .tɕhjiw 2	wǝə 1 .tɕhjwor 2 ] A =dʑjɨ.wji 1	njɨɨ 2	zji ɨ ̣ 1	[dzjwo 2
	emperor	aunt	royal.woman	servant=erg	day	time	people
	gjɨ 2 ] O	dja 2 -sja 1
	one	dir1:pfv-to.kill
	時帝姑公主奴白日殺一人。	(Shi et al. 1993: 42)
	' At that time, the servant of the emperor's aunt killed a person in the daytime. '
								(Leilin 03.08A.2-3)
	Human and definite objects are not marked if they do not have discourse promi-
	nence. In (9), the human and definite object the Minister Pi is unmarked. In this
	8. The term 'prominence' in this paper is used in a similar way as in Aissen (2003) and de
	Swart (2007) and refers to features triggering DOM. The only difference is that here promi-
	nence also includes topicality in addition to humanness/animacy and definiteness/specificity.

  ) 3→3 𘄴 1319 𘟙 3830 𗋕 2019 𗳷 1796 𗂧 2937 𘒏 1531 𘆝 0764 𘅣 1183 𘔜 0298 𗑃 5055 𘋩 5447 𘙇 0795 𗂸 3508 𗅉 1906 𘟙 3830 𘜶 4456 𗗙 1139 𗤱 3248 𗖌 0448 𘀽 3974 𗧓 2098

	𘎪 5612
	[tshji 1	njij 2 ] A	thja 1	[tɕhjụ 1	lhjịj 2	gia 1	rjijr 1	dạ 2 ] T	[tɕhjĩ 1 .tɕjĩ 1 ] R =do 2
	Qi	king	dem	Chu	country	army	horse	affaire	pn:Chen.Zheng=dat
	rjɨr 2 -tshjiij 1
	[bji 2 ] A		nioow 1	[njij 2	tha 2 ] R =jij 1	[rjɨj 2	gjɨ 2 ] T	tshjii 2 -ŋa 2
	your.servant 臣更與大王說一計。 lnk king	grand=obl	stratagem	one	to.say [b] -1sg (Shi et al. 1993: 61)
	'I'll tell your majesty a counsel (to save yourself from Wu's invasion). '
										(Leilin, 03.27B.6)

dir1:pfv-to.say

[A]

'The king of Qi spoke about the affair of the army of Chu to Chen Zheng. ' (Twelve Kingdoms, Solonin 1995: 43, cited by Beaudouin 2021)

However, in (

12

), the addressee (R), your majesty, is marked by 𗗙 1139 jij 1 . Note that morphological indirectivity is clearly indicated in (12): the verb occurs in its stem [B] form 𘀽 3974 tshjii 2 (< Pre-Tangut *tshjeej-w, Jacques 2014: 170-171), indicating that the theme, a counsel, is indexed as the direct object.

(12) 1sg→3

  ) 2sg→3 𗍳 4028 𗩱 2620 𘝦 5604 𘕣 5688 𗲉 1075 𗏹 2513 𘓐 2541 𗗙 1139 𗈦 1336 𗠔 4568 𘉞 4601 With a transitive base, causativization derives a three-place predicate ([A causer , O causee , oblique]). It introduces a new agent as the causer (A causer ), and the original A becomes the causee (O causee ). Both the causer and the causee are indexable. The original O becomes an oblique of the derived causative compound, which is nonindexable. The phenomenon of optional causee marking is also observed with trivalent causative compounds. Example (14) has a trivalent causative compound 𘟀 0046 𗟻 0749 'to cause to see, to show' , based on the transitive verb 𘟀 0046 ljij 2 'to see' . The plural first person causee is pronominally represented on the verb by the plural suffix -nji 2 , and is also case marked with 𗗙 1139 jij 1 . (14) 2→1pl 𗧓 2098 𘆄 0724 𗗙 1139 𘙌 1326 𘟀 0046 𗟻 0749 𗐱 4884 [ŋa 2 .njɨ 2 ] CAUSEE =jij 1 1pl=acc Optional marking on the oblique argument with 𗗙 1139 jij 1

				kjɨ 1 -ljij 2 -phji 1 -nji 2
	'Show it to us. '		dir1:imp-to.see-caus [a] -1pl (Kepping 1985: 228, citing Nevskij 1960: 591)
	3.3.2
	nji 2	njwi 2 .dʑjɨ	wa 2	dʑjo 2	[ ju 2	dzjwo 2 ] CAUSEE =jij 1
	2sg lhạ 2 -phjo 2 -nja 2 skill what	to.have [B]	common	people=acc
	be.confused-caus [B] -2sg 汝有何術, 而誣惑常人?		(Shi et al. 1993: 115)
	'What technique do you have to cause confusion in common people?'
						(Leilin, 05.21B.3-4)

  ), with the causative verb 𗯹 5754 -𗟻 0749 'to cause to catch' , case marking occurs after the oblique argument Shijing. (15) 𗩇 2872 𗺹 3379 𗈪 5981 𗕣 0945 𘓐 2541 𘒫 5871 𘏸 5442 𘊐 2219 𗗙 1139 𗯹 5754 𗟻 0749

	wẽ 1 .xew 1	a-tshjạ 1	dzjwo 2	zeew 2	ɕiə 1 .kjij 1 =jij 1	lju 2 -phji 1
	pn:Wenhou	dir1:pfv-be.angry	people	to.send	pn:Shijing=obl	to.catch-caus [a]

  ) 𘑲 1030 𗦵 2177 𗢄 4609 𗘼 0775 𗶃 1733 𘋩 5447 𗋚 2590 𗄾 2931 𗟻 0749

	tɕjow 1 .pǝ 1	ɕjwã 2 .giuu 1 .tɕji 2 =do 2	wjɨ 2 -sej 1 -phji 1
	pn:Zhang.ben '(Zhang Ben's mother was seriously ill) Zhang Ben sought divination from pn:Chunyu.zhi=dat dir1:pfv-to.calculate-caus [a]
	Chuyu Zhi. ' 14		(Leilin 06.14B.3-4)

in Tangut [15] Figure 3.

  Prototypical semantic values of 𗗙 1139 jij 1 and 𘋩 5447 do 2 (17) 𘜶 4456 𗂸 3508 𗁡 2923 𘕘 5925 𗍏 0586 𗗙 1139 𗥑 3118 𗉪 1409 𘋩 5447 𘙌 1326 𘞝 0031 𗢯 3190 [tha 2 .bji 2 .phji 1 ] Minister.Pi [tsǝ 1 .sju 2 ]=jij 1 Syntactic distribution of 𗗙 1139 jij 1 and 𘋩 5447 do 2

pn:Wu.Zixu=acc/obl [xu 1 .tɕhiəj 2 ]=do 2 pn:Fuchai=dat kjɨ 1 -dzjwɨ 1 -lhjwa 1 dir1:pfv-to.slander-tongue (Shi et al., 1993: 55) 大臣嚭谗子胥於夫差。 'The Minister Pi slandered Wu Zixu to the King Fuchai. ' (Leilin, 03.21A.7-21B.1) 3.4.2

Table 4

 4 summarizes the syntactic distribution 15 of 𗗙 1139 jij 1 and 𘋩 5447 do 2 in marking clausal functions.

Table 4 .

 4 Syntactic distribution of 𗗙 1139 jij 1 and 𘋩 5447 do 2

Object (indexable) Non-indexable Patient Causee Oblique (caus, etc.) recipient; addressee Goal of motion

	𗗙 1139 jij 1 ✓	✓	rare	✓
	𘋩 5447 do 2	rare		✓	✓

Table 5 .

 5 Verb classification, indexation types and case frames in modern West Rgyalrongic languages (based on Lai 2017: 2021) *

	Verb type	Indexation Case frame
	Intransitive	V[S]	S=ø	E=ø
	Semi-transitive		S=ø	E=dat
	Extended intransitive		S=ø	E=obl
	Transitive Indirect transitive V[A,O]	A(=erg)	O=ø
			A(=erg)	O=dat
			A(=erg)	O=loc:surface (Khros)
	Secundative	V[A,R=O] A(=erg) T=ø	R=dat
	Indirective	V[A,T=O] A(=erg)	T=ø	R=dat
			A(=erg)	T=ø	R=obl
	Multitransitive	A(=erg)	T=ø	R(E 1 )=obl	E 2 =dat
	* E stands for the extended argument (cf. Dixon & Aikhenvald 2000).

  .

	wobzi khroskyabs (west rgyalrongic)
	(19) a. ró [S=ø] 'be necessary, should'
	aegae	jdə̂=ɣə	tsʰâtsʰâ	rʑət	ró
	lnk 'Then, one should wash them well with water. (Lit: washing them well water=ins well should o.wash I
	with water is necessary)'	(Lai 2017: 586)
	b. ró [S=ø, E=obl] 'want, be necessary to'
	nû=ji	tʰǽ=ɟae	rə-ró
	2sg=obl 'You want too much (Lit: Too much things are necessary to you)' whatever=many npst-be.necessary I
						(Lai 2017: 371)

  , could be lexicalized from the alternating structure [S, E=obl] of a basic intransitive verb *ɖʐaen 'to lack'[S].

	geshiza (west rgyalrongic)
	(20) nʑae 'to bring' [S=erg, T, R=obl]
	gəɕʰo	ŋae=ɲi	vdʑae=wo	<tiaenxua>	dae-nʑae-sʰi
	evening	1=pl.obl	friend=erg	phone.call	pfv-bring.3-ifr
	'In the evening, our friend called us. '	(Honkasalo 2019: 372)

  He has killed a bear. When killing the bear he brought it down (to Balang),

	geshiza (west rgyalrongic)
	(21) v-qʰlə 'to divide' [S=erg, T, R=obl]
	lmo	wo	ae-lə		dae-v-sae	zda
	3.erg	bear	one-clf.indf.abs	pfv-inv-kill.pst.3	aux.exp.perf
	dae-v-sae			tɕʰa=rae	nae-v-tae=rae	bəra
	pfv-inv-kill.pst.3	when=lnk	pfv.dir-inv-bring.pst.3=lnk	topn
	stɕəpa=je		dae-v-qʰlə-sʰi	ŋuə
	villagers=obl	pfv-inv-divide.pst.3-nmlz	cop.3
	'

  .

	wobzi khroskyabs (west rgyalrongic)
	(22) zə̂m 'to bring'
	tʂɑɕî=ɣə	nû=ji	kɑpəb	ŋɑ̂=kʰe	k-u-zə́m
	Bkra.shis=erg 'Bkrashis brought you a book from me. ' 2sg=obl/gen ook 1sg=abl	pst-inv-to.bring II	(Lai 2017: 187)
	Although in (

Table 6 .

 6 Verb classification, case marking and indexation types in Brag-bar Situ

	Verb type	Indexation Argument structure
	Intransitive	V[S]	S=ø
	Semi-transitive		S=ø	E=loc
	Extended intransitive		S=ø	E=dat
			S=ø	E=ø
	Transitive

  in Tangut [23]

	ŋá	ŋə-wô	na-mə́ŋam,	ŋə-smɐ̂n	rə	rɐ-kî-n
	1sg 'My head aches, buy me some medicine. ' 1sg.poss-head sens-be.painful I 1sg.poss-medicine	one (Lit: buy my medicine) imp-to.buy I -2sg

  TANGUT (WEST RGYALRONGIC) 𗡸 0243 𗗙 1139 𗥃 2205 𗣼 2748 𘟣 0930 sji 2 =jij 1 woman=gen , through semantic extension from the Location Schema, could also be assumed. This would have happened with locative phrases with referential status (cf. Section 4.2.3.2), and in particular with pronouns, as illustrated in (40).

	ljɨr 1	tɕhja 2		dju 1
	four	integrity	ex
	婦有四德			(Shi et al. 1993: 234, cited in Ikeda 2012: 195)
	'Women have four integrity. '	(Leilin, 09.25B.4)
	A second pathway(40) Metaphorical extension from the Location Schema
	pron=loc 'what is at X' > pron=gen 'X's'
	5.2.2 Topic Schema
	Section 4.2.3.3 illustrated that the 'double marking' pattern in Situ might have
	developed from the topic possessive, which suggests that a reanalysis from topic
	possessor to genitive possessor was a possibility in Situ, though it remained a mar-
	ginal phenomenon. (from (41a) to (41b)). Additionally, the 'double marking' pat-
	tern itself (41b) can be reconstructed as an intermediate stage in the reanalysis
	from topic possessive to genitive in West Rgyalrongic.
	(41) Genitive possessive reanalyzed from the Topic Schema
	a. Topic possessive	[pr=loc] [pref.poss-pe] predicate
	b. Double marking	[pr=loc pref.poss-pe]
	c. Adominal possessive [pr=gen pe]

  The history of the polyfunctional 𗗙 jij1 in Tangut [35]

	1	first person	indf	indefinite
	2	second person	inf	infinitive
	3	third person	ins	instrumental
	i	Stem I	inv	inverse
	ii	Stem II	ipfv	imperfective
	i'	Stem I'	lnk	linker
	ii'	Stem II'	loc	locative
	[a]	Stem A	m	masculine
	[b]	Stem B	neg	negative
	a	transitive subject	nmlz	nominalizer
	abl	ablative (before/above ABS)	npst	non-past
	abs	absolutive	o(j)	object
	acc	accusative	obl	oblique
	ade	adessive	opt	optative
	all	allative	pe	possessor
	autoben autobenefactive	perf	perfect
	aux	auxiliary	pfv	perfective
	caus	causative	pl	plural
	clf	classifier	pm	prominence marker
	cm	clause marker	pn	person name
	cop	copula	pot	potential
	dat	dative	poss	possessive
	def	definite	pr	possessor
	dem	demonstrative	prox	proximate
	det	determiner	pref	prefix
	dir	directional prefix	pron	pronoun
	dis	distal	pst	past
	dom	differential object marking	ptcp	participle
	down	downward direction	r	recipient
	du	dual	red	reduplication
	e	extended argument	s	intransitive subject
	erg	ergative	sg	singular
	ex	existential predicate	sens	sensory
	exp	experiential	sj	subject
	fac	factual	t	theme
	gen	genitive	tame	tense-aspect-modality-evidentiality
	ifr	inferential	topn	toponym
	imp	imperative	up	upward direction

The history of the polyfunctional 𗗙 jij 1 in Tangut[5]

Tangut also has an infrequent dual suffix 𘙌 1326 -kjɨ 1 (Arakawa 2018).[6] Shuya Zhang

The history of the polyfunctional 𗗙 jij 1 in Tangut[7]

Alternation between khjow 1 and khjɨj 1 is not due to the merger of the third person patient suffix *-w(Jacques 2014: 200-201).[12] Shuya Zhang

[20] Shuya Zhang

The phenomenon prevails in Tibeto-Burman languages, for further discussions seeStassen (2009: 316-321) andChappell & Lü (2022).[24] Shuya Zhang

The history of the polyfunctional 𗗙 jij1 in Tangut [25]

[26] Shuya Zhang

The history of the polyfunctional 𗗙 jij1 in Tangut [29]

The history of the polyfunctional 𗗙 jij1 in Tangut [33]

Acknowledgements

I would like to thank Guillaume Jacques, Lai Yunfan, Mathieu Beaudouin, Arakawa Shintaro, Shirai Satoko, Sawada Hideo, Hayashi Norihiko, Agnes Conrad, Nikita Kuzmin, and the anonymous reviewers for their valuable comments and suggestions. All errors are my own.

Funding

This research was funded by the Grant-in-Aid for JSPS Research Fellow (21F20303).

Abbreviations


Guillaume Damiand
email: guillaume.damiand@liris.cnrs.fr

Colin De La Higuera

Jean-Christophe Janodet
email: janodet@univ-st-etienne.fr

Émilie Samuel
email: emilie.samuel@univ-st-etienne.fr

Christine Solnon
email: christine.solnon@liris.cnrs.fr

⋆⋆

A Polynomial Algorithm for Submap Isomorphism -Application to Searching Patterns in Images

In this paper, we address the problem of searching for a pattern in a plane graph, i.e., a planar drawing of a planar graph. To do that, we propose to model plane graphs with 2-dimensional combinatorial maps, which provide nice data structures for modelling the topology of a subdivision of a plane into nodes, edges and faces. We define submap isomorphism, we give a polynomial algorithm for this problem, and we show how this problem may be used to search for a pattern in a plane graph. First experimental results show the validity of this approach to efficiently search for patterns in images.

Introduction

In order to manage the huge image sets that are now available, and more particularly to classify them or search through them, one needs similarity measures.

A key point that motivates our work lies in the choice of data structures for modelling images: These structures must be rich enough to describe images in a relevant way, while allowing an efficient exploitation. When images are modelled by vectors of numerical values, similarity is both mathematically well defined and easy to compute. However, images may be poorly modelled with such numerical vectors that cannot express notions such as adjacency or topology.

Graphs allow one to model images by means of, e.g., region adjacency relationships or interest point triangulation. In either case, graph similarity measures have been investigated [START_REF] Conte | Thirty years of graph matching in pattern recognition[END_REF]. These measures often rely on (sub)graph isomorphism -which checks for equivalence or inclusion-or graph edit distances and alignments -which evaluate the cost of transforming a graph into another graph. If there exist rather efficient heuristics for solving the graph isomorphism problem4 [START_REF] Mckay | Practical graph isomorphism[END_REF][START_REF] Sorlin | A parametric filtering algorithm for the graph isomorphism problem[END_REF], this is not the case for the other measures which are often computationally intractable (NP-hard), and therefore practically unsolvable for large scale graphs. In particular, the best performing approaches for subgraph isomorphism are limited to graphs up to a few thousands of nodes [CFSV01,ZDS + 07]. However, when measuring graph similarity, it is overwhelmingly forgotten that graphs actually model images and, therefore, have special features that could be exploited to obtain both more relevant measures and more efficient algorithms. Indeed, these graphs are planar, i.e., they may be drawn in the plane, but even more specifically just one of the possible planar embeddings is relevant as it actually models the image topology, that is, the order in which faces are encountered when turning around a node.

In the case where just one embedding is considered, graphs are called plane. Isomorphism of plane graphs needs to be defined in order to integrate topological relationships. Let us consider for example the two plane graphs drawn in Fig. 1(a) and 1(b). The underlying graphs are isomorphic, i.e., there exists a bijection between their nodes which preserves edges. However, these plane graphs are not isomorphic since there does not exist a bijection between their nodes which both preserves edges and topological relationships. Now by considering this, the isomorphism problem becomes simple [START_REF] Cori | Un code pour les graphes planaires et ses applications[END_REF], but the subgraph isomorphism problem is still too hard to be tackled in a systematic way. Yet we may argue that when looking for some pattern in a picture (for example a chimney in a house, or a wheel in a car) we may simplify the problem to that of searching for compact plane subgraphs (i.e., subgraphs obtained from a graph by iteratively removing nodes and edges that are incident to the external face). Let us consider for example the plane graphs of Fig. 1.

The bold edges in Fig. 1(c) constitute a compact plane subgraph. However, the bold edges in Fig. 1(d) do not constitute a compact plane subgraph because edge (4, 3) separates a face of the subgraph into two faces in the original graph.

Contribution and outline of the paper. In this paper, we address the problem of searching for compact subgraphs in a plane graph. To do that, we propose to model plane graphs with 2-dimensional combinatorial maps, which provide nice data structures for modelling the topology of a subdivision of a plane into nodes, edges and faces. We define submap isomorphism, we give a polynomial algorithm for this problem, and we show how this problem may be used to search for a compact graph in a plane graph. Therefore we show that the problem can be solved in this case in polynomial time.

We introduce 2D combinatorial maps in Section 2. A polynomial algorithm for map isomorphism is given in Section 3 and submap isomorphism is studied in Section 4. We relate these results with the case of plane graphs in Section 5, and we give some experimental results that show the validity of this approach on image recognition tasks in Section 6.

Combinatorial Maps

A plane graph is a planar graph with a mapping from every node to a point in 2D space. However, in our context the exact coordinates of nodes matter less than their topological organisation, i.e., the order nodes and edges are encountered when turning around faces. This topological organisation is nicely modelled by combinatorial maps [START_REF] Edmonds | A combinatorial representation for polyhedral surfaces[END_REF][START_REF] Tutte | A census of planar maps[END_REF][START_REF] Cori | Un code pour les graphes planaires et ses applications[END_REF].

To model a plane graph with a combinatorial map, each edge of the graph is cut in two halves called darts, and two one-to-one mappings are defined onto these darts: the first to link darts belonging to two consecutive edges around a same face, the second to link darts belonging to a same edge.

Definition 1. (2D combinatorial map [START_REF] Lienhardt | Topological models for boundary representation: a comparison with n-dimensional generalized maps[END_REF]) A 2D combinatorial map, (or 2-map) is a triplet M = (D, β 1 , β 2 ) where D is a finite set of darts; β 1 is a permutation on D, i.e., a one-to-one mapping from D to D; and β 2 is an involution on D, i.e., a one-to-one mapping from D to D such that β 2 = β -1 2 . We note β 0 for β -1 1 . Two darts i and j such that i = β k (j) are said to be k-sewn. Fig. 2 gives an example of a combinatorial map.

In some cases, it may be useful to allow β i to be partially defined, thus leading to open combinatorial maps. The intuitive idea is to add a new element ǫ to the set of darts, and to allow darts to be linked with ǫ for β 1 and/or β 2 . By definition, ∀0 ≤ i ≤ 2, β i (ǫ) = ǫ. Fig. 3 gives an example of open map (see [START_REF] Poudret | Cartes combinatoires ouvertes[END_REF] for precise definitions).

Finally, Def. 2 states that a map is connected if there is a path of sewn darts between every pair of darts. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 β1 2 3 4 5 6 7 1 9 10 11 8 13 14 15 12 17 18 16 β2 15 14 18 17 10 9 8 7 6 5 12 11 16 2 1 13 4 3

Definition 2. (connected map) A combinatorial map M = (D, β 1 , β 2 ) is con- nected if ∀d ∈ D, ∀d ′ ∈ D, there exists a path (d 1 , . . . , d k ) such that d 1 = d, d k = d ′ and ∀1 ≤ i < k, ∃j i ∈ {0, 1, 2}, d i+1 = β ji (d i ).

Map Isomorphism

Lienhardt has defined isomorphism between two combinatorial maps as follows.

Definition 3. (map isomorphism [Lie94]) Two maps M = (D, β 1 , β 2 ) and M ′ = (D ′ , β ′ 1 , β ′ 2 ) are isomorphic if there exists a one-to-one mapping f : D → D ′ , called isomorphism function, such that ∀d ∈ D, ∀i ∈ {1, 2}, f (β i (d)) = β ′ i (f (d))
. We extend this definition to open maps by adding that f (ǫ) = ǫ, thus enforcing that, when a dart is linked with ǫ for β i , then the dart matched to it by f is also linked with ǫ for β ′

i . An algorithm may be derived from this definition in a rather straightforward way, as sketched in [START_REF] Cori | Un code pour les graphes planaires et ses applications[END_REF]. Algorithm 1 describes the basic idea which will be extended in section 4 to submap isomorphism: We first fix a dart d 0 ∈ D; then, for every dart d ′ 0 ∈ D ′ , we call Algorithm 2 to build a candidate matching function f and check whether f is an isomorphism function. Algorithm 2 basically performs a traversal of M , starting from d 0 and using β i to discover new darts from discovered darts. Initially, Input: two open connected maps M = (D, β1, β2) and

f [d 0 ] is set to d ′ 0 whereas f [d] is set to nil for all other darts. Each time a dart d i ∈ D is discovered, from another dart d ∈ D through β i so that d i = β i (d), then f [d i ] is set to the dart d ′ i ∈ D ′ which is linked with f [d] by β ′ i . Complexity issues. Algorithm 2 is in O(|D|). Indeed,
M ′ = (D ′ , β ′ 1 , β ′ 2 ) Output: returns true iff M and M ′ are isomorphic choose d0 ∈ D 1 for d ′ 0 ∈ D ′ do 2 f ← traverseAndBuildMatching(M, M ′ , d0, d ′ 0 ) 3 if f is a bijection from D ∪ {ǫ} to D ′ ∪ {ǫ} and 4 ∀d ∈ D, ∀i ∈ {1, 2}, f [βi(d)] = β ′ i (f [d]) then return true 5 return false 6 Algorithm 2: traverseAndBuildMatching(M, M ′ , d 0 , d ′ 0 )
Input: two open connected maps M = (D, β1, β2) and

M ′ = (D ′ , β ′ 1 , β ′ 2 ) and an initial couple of darts (d0, d ′ 0 ) ∈ D × D ′ Output: returns an array f : D ∪ {ǫ} → D ′ ∪ {ǫ} for every dart d ∈ D do: f [d] ← nil 1 f [d0] ← d ′ 0 2
let S be an empty stack; push d0 in S 3 while S is not empty do

4 pop a dart d from S 5 for i ∈ {0, 1, 2} do 6 if βi(d) = ǫ and f [βi(d)] = nil then 7 f [βi(d)] ← β ′ i (f [d]) 8 push βi(d) in S 9 f [ǫ] ← ǫ 10 return f 11 Algorithm 1 is O(|D| 2
). Note that it may be optimised (without changing its complexity), e.g., by detecting failure while building matchings.

(2) = b but β ′ 2 (b) = ǫ and f -1 (β ′ 2 (b)) is not empty because f -1 (d) = 4.
inition of an isomorphism function

∈ D, ∀i ∈ {1, 2}, if β i (d) = ǫ then β ′ i (f (d)) = f (β i (d)) else either β ′ i (f (d)) = ǫ or f -1 (β ′ i (f (d))
) is empty. This definition derives from the definition of isomorphism. The only modification concerns the case where d is i-sewn with ǫ. In this case, the definition ensures that f (d) is i-sewn either with ǫ, or with a dart d ′ which is not matched with a dart of M , i.e., such that f -1 (d ′ ) is empty (see example in Fig. 4).

Note that if M is isomorphic to a submap of M ′ , then M is isomorphic to the map M ′′ obtained from M ′ by restricting the set of darts D ′ to the set of darts

D ′′ = {d ∈ D ′ |∃a ∈ D, f (a) = d}.
Algorithm 3 determines if there is a submap isomorphism between two open connected maps. It is based on the same principle as Algorithm 1; the only difference is the test of line 4, which succeeds if f is a subisomorphism function instead of an isomorphism function. The time complexity of this algorithm is in O(|D| • |D ′ |) as traverseAndBuilMatching is called at most |D ′ | times and its complexity is in O(|D|). Note that the subisomorphism test may be done in linear time.

′ = (D ′ , β ′ 1 , β ′ 2 ) Output: returns true iff M is isomorphic to a submap of M ′ choose d0 ∈ D 1 for d ′ 0 ∈ D ′ do 2 f ← traverseAndBuildMatching(M, M ′ , d0, d ′ 0 ) 3 if f is an injection from D ∪ {ǫ} to D ′ ∪ {ǫ ′ } and 4 ∀d ∈ D, ∀i ∈ {1, 2}, βi(d) = ǫ ⇒ f (βi(d)) = β ′ i (f (d)) and ∀d ∈ D, ∀i ∈ {1, 2}, βi(d) = ǫ ⇒ ∃e ∈ D, f (e) = β ′ i (f (d)) then return true 5 return false 6
Concerning correctness, note that proofs and evidences given for isomorphism are still valid: We solve the submap isomorphism problem with the same method as before, except that function f is now an injection instead of a bijection.

From Plane Graphs to Maps

In this section, we show how to transform the problem of finding a compact plane subgraph inside a plane graph into the problem of finding a submap in a map, thus allowing to use our polynomial algorithm.

Let us first precise what we exactly mean by (compact) plane (sub)graph isomorphism. Let us consider two graphs G 1 = (N 1 , E 1 ) and G 2 = (N 2 , E 2 ) that are embedded in planes and let us note o(i, j) the edge which follows edge (i, j) when turning around node i in the clockwise order. We shall say that -G 1 and G 2 are plane isomorphic if there exists a bijection f : N 1 → N 2 which preserves (i) edges, i.e., ∀(i, j)

∈ N 1 ×N 1 , (i, j) ∈ E 1 ⇔ (f (i), f (j)) ∈ E 2 and (ii) topology, i.e., ∀(i, j) ∈ E 1 , o(i, j) = (k, l) ⇔ o(f (i), f (j)) = (f (k), f (l)); -G 1 is a compact plane subgraph of G 2 if G 1 is plane isomorphic to a compact
subgraph of G 2 which is obtained from G 2 by iteratively removing nodes and edges that are incident to the external face.

Note that the pattern may be a partial subgraph of the target. Let us consider for example Fig. 1c. Edge (1, 5) needs not to belong to the searched pattern, eventhough nodes 1 and 5 are matched to nodes of the searched pattern. However, edge (4, 3) must belong to the searched pattern; otherwise it is not compact.

To use submap isomorphism to solve compact plane subgraph isomorphism, we have to transform plane graphs into 2-maps. This is done by associating a face in the map with every face of the graph except the external face. Indeed, a 2-map models a drawing of a graph on a sphere instead of a plane. Hence, none of the faces of a map has a particular status whereas a plane graph has an external (or unbounded) face. Let us consider for example the two graphs in Fig. 1a and Fig. 1b: When embedded in a sphere, they are topologically isomorphic because one can translate edge (d, c) by turning around the sphere, while this is not possible when these graphs are embedded in a plane. In order to forbid one to turn around the sphere through the external face, graphs are modelled by open 2-maps such that external faces are removed: Only β 2 is opened, and only external faces are missing. Such open 2-maps correspond to topological disks.

Finally, a strong precondition for using our algorithms is that maps must be connected. This implies that the original graphs must also be connected. However, this is not a sufficient condition. One can show that an open 2-map M modelling a plane graph G without its external face is connected if G is connected and if the external face of G is delimited by an elementary cycle.

Hence, submap isomorphism may be used to decide in polynomial time if G 1 is a compact plane subgraph of G 2 provided that (i) G 1 and G 2 are modelled by open 2-maps such that external faces are removed, and (ii) external faces of G 1 and G 2 are delimited by elementary cycles.

This result may be related to [JB98,JB99] which describe polynomial-time algorithms for solving (sub)graph isomorphism of ordered graphs, i.e., graphs in which the edges incident to a vertex are uniquely ordered.

Experiments

This section gives some preliminary experimental results that show the validity of our approach. We first show that it allows to find patterns in images, and then we study scale-up properties of our algorithm on plane graphs of growing sizes. Experiments were run on an Intel Core2 Duo CPU at 2.20GHz processor.

Finding patterns in images

We have considered the MOVI dataset provided by Hancock [START_REF] Luo | Spectral embedding of graphs[END_REF]. This dataset consists of images representing a house surrounded by several objects. We consider two different kinds of plane graphs modelling these images. First, we have segmented them into regions and compute the 2D combinatorial map of the segmented image using the approach described in [START_REF] Damiand | Topological model for twodimensional image representation: definition and optimal extraction algorithm[END_REF]. Second, we have used the plane graphs provided by Hancock. They correspond to a set of corner points extracted from the images and connected by Delaunay triangulation. These graphs were then converted into 2D combinatorial maps. In both cases, we have extracted patterns from original images, and used our approach to find these patterns.

The left part of Fig. 5 shows an image example, together with its plane graph obtained after segmentation. This graph consists of 2435 nodes, 4057 edges and 1700 faces. The pattern extracted from this image corresponds to the car, composed of 181 nodes, 311 edges and 132 faces. This pattern has been found by our algorithm in the original image, even when submitted to rotation, in 60ms.

The Delaunay graph corresponding to the corner points is shown on the right part of Fig. 5. It has 140 nodes, 404 edges and 266 faces. The graph corresponding to the car has 16 nodes, 38 edges and 23 faces. This pattern has been found by our algorithm in the original image in 10ms.

Experiments show that our approach always allows one to find these patterns in the image they have been extracted from.

Scale up properties

To compare scale-up properties of our approach with those of subgraph isomorphism algorithms, we have performed a second series of experiments: We have randomly generated 3 plane graphs, g 500 , g 1000 and g 5000 which have 500, 1000 and 5000 nodes respectively. These plane graphs are generated by randomly picking n 2D points in the plane, then by computing Delaunay graph of these points. For each plane graph g i , we have generated 5 sub-graphs, called sg i,k% , which have k% of the number of nodes of the original graph g i , where k belongs to {5, 10, 20, 33, 50}.

Table 1 compares CPU times of our approach with those of Vflib2 [CFSV01], a state-of-the-art approach for solving subgraph isomorphism (we present only results of Vflib2 which is, in our experiments, always faster than Vflib and Ullmann). It shows the interest of using submap isomorphism to solve compact plane subgraph isomorphism. Indeed, if both approaches spend comparable time for the smaller instances, larger instances are much quickly solved by our approach. In particular, instances (g 5000 , sg 5000,k% ) are solved in less than one second by our approach whereas it is not solved after one hour of computation by Vflib2 when k ≥ 20.

It is worth mentionning here that the two approaches actually solve different problems: Our approach searches for compact plane subgraphs whereas Vflib2 searches for induced subgraphs and do not exploit the fact that the graphs are planar. Hence, the number of solutions found may be different: Vflib2 may found subgraphs that are topologically different from the searched pattern; also our approach may found compact plane subgraphs that are partial (see Fig. 1c) whereas Vflib2 only searches for induced subgraphs. For each instance considered in Table 1, both methods find only one matching, except for sg 5000,10% which is found twice in g 5000 by vflib2 and once by our approach.

Discussion

We have defined submap isomorphism, and we have proposed an associated polynomial algorithm. This algorithm may be used to find compact subgraphs in plane graphs. First experiments on images have shown us that this may be used to efficiently find patterns in images.

These first results open very promising further work. In particular, our approach could be used to solve the subgraph isomorphism problem in polynomial time for classes of planar graphs which admit polynomial numbers of planar embeddings. Also, generalisation to 3 and higher dimensional combinatorial maps is immediate. Hence, our approach could be used to find subsets of compact volumes in 3D images.

Submap isomorphism leads to exact measures, which may be used to check if a pattern belongs to an image. We plan to extend this work to error-tolerant measures such as the largest common submap, which could be used to find the largest subset of edge-connected faces, and map edit distances, which could be used to measure the similarity of maps by means of edit costs.

Finally, more relevant results in the image field could be obtained by integrating geometric information: combinatorial maps may be labelled by features extracted from the modelled image such as, e.g., the shape or the area of a face, the angle between two segments, or the length of a segment. These labels may be used to measure map similarity by quantifying the similarity of labels associated with matched cells.

⋆Fig. 1 .

 1 Fig. 1. (a) and (b) are not isomorphic plane graphs; bold edges define a compact plane subgraph in (c), but not in (d).

Fig. 2 .

 2 Fig. 2. Combinatorial map example. Darts are represented by numbered black segments. Two darts 1-sewn are drawn consecutively, and two darts 2-sewn are concurrently drawn and in reverse orientation, with little grey segment between the two darts.

  Fig. 3. Open combinatorial map example. Darts a, b, d, f and g are not 2-sewn.

Correction of Algorithm 1 .Fig. 4 .

 14 Fig.4. Submap example. M is a submap of M ′ as it is obtained from M ′ by deleting darts k to r. M ′′ is not a submap of M ′ as the injection f : D ′′ → D wich matches darts 1 to 10 with darts a to j does not verify Def. 4:β2(2) = ǫ and f (2) = b but β ′ 2 (b) = ǫ and f -1 (β ′ 2 (b)) is not empty because f -1 (d) = 4.

  map M is a submap of M ′ if M can be obtained from M ′ by removing some darts. When a dart d is removed, we set β i (d ′ ) to ǫ for every dart d ′ such that β i (d ′ ) = d. Definition 4. (submap) An open combinatorial map M = (D, β 1 , β 2 ) is isomorphic to a submap of an open map M ′ = (D ′ , β ′ 1 , β ′ 2 ) if there exists an injection f : D ∪ {ǫ} → D ′ ∪ {ǫ}, called a subisomorphism function, such that f (ǫ) = ǫ and ∀d

Algorithm 3 :

 3 checkSubIsomorphism(M, M ′ ) Input: two open connected maps M = (D, β1, β2) and M

Fig. 5 .

 5 Fig. 5. Finding a car in an image: The original image is on the left. The plane graph obtained after segmentation is on the middle; the car has been extracted and rotated on the right and it has been found in the original image. The graph obtained by Delaunay triangulation and the corresponding combinatorial map are on the right; the car has been extracted and it has been found in the original image.

  the while loop is iterated |D| times as (i) exactly one dart d is removed from the stack S at each iteration; and (ii) each dart d ∈ D enters S at most once (d enters S only if f [d] = nil, and before entering S, f [d] is set to a dart of D ′ ). In Algorithm 1, the test of line 4 may also be performed in O(|D|). Hence, the overall time complexity of Algorithm 1: checkIsomorphism(M, M ′ )

Table 1 .

 1 Comparison of scale-up properties of submap and subgraph isomorphism algorithms. Each cell gives the CPU time (in seconds) spent by Vflib2 and our submap algorithm to find all solutions. > 3600 means that Vflib2 had not finished after one hour of computation.

		sg i,5%	sg i,10%	sg i,20%	sg i,33%	sg i,50%
	gi	vf2 map vf2 map	vf2	map	vf2	map	vf2	map
	g500 0.08 0.07	0.04 0.10	0.47 0.03	0.7 0.02	10.4 0.10
	g1000 4.7 0.21	2.54 0.07	0.55 0.05	7.31 0.06	12.7 0.06
	g5000 12.3 0.28 156.5 0.31 ¿3600.	0.31 ¿3600.	0.31 ¿3600.	0.31

The theoretical complexity of graph isomorphism is an open question: If it clearly belongs to NP, it has not been proven to be NP-complete.