An application of persistent homology and the graph theory to linguistics: The case of Tifinagh and Phoenician scripts

Bouazzaoui, Haja ; Eloma y, Mohamed Abdou; Mamouni, My Ismail A icle An applica ion o pe sis en homology and he g aph heo y o linguis ics: The case o Ti inagh and Phoenician sc ip s S a is ics in T ansi ion New Se ies P o ided in Coope a ion wi h: Polish S a is ical Associa ion Sugges ed Ci a ion: Bouazzaoui, Haja ; Eloma y, Mohamed Abdou; Mamouni, My Ismail (2021) : An applica ion o pe sis en homology and he g aph heo y o linguis ics: The case o Ti inagh and Phoenician sc ip s, S a is ics in T ansi ion New Se ies, ISSN 2450-0291, Exeley, New Yo k, Vol. 22, Iss. 3, pp. 141-156, h ps://doi.o g/10.21307/s a ans-2021-031 This Ve sion is a ailable a : h ps://hdl.handle.ne /10419/266275 S anda d-Nu zungsbedingungen: Die Dokumen e au EconS o dü en zu eigenen wissenscha lichen Zwecken und zum P i a geb auch gespeiche und kopie we den. Sie dü en die Dokumen e nich ü ö en liche ode komme zielle Zwecke e iel äl igen, ö en lich auss ellen, ö en lich zugänglich machen, e eiben ode ande wei ig nu zen. So e n die Ve asse die Dokumen e un e Open-Con en -Lizenzen (insbesonde e CC-Lizenzen) zu Ve ügung ges ell haben soll en, gel en abweichend on diesen Nu zungsbedingungen die in de do genann en Lizenz gewäh en Nu zungs ech e. Te ms o use: Documen s in EconS o may be sa ed and copied o you pe sonal and schola ly pu poses. You a e no o copy documen s o public o comme cial pu poses, o exhibi he documen s publicly, o make hem publicly a ailable on he in e ne , o o dis ibu e o o he wise use he documen s in public. I he documen s ha e been made a ailable unde an Open Con en Licence (especially C ea i e Commons Licences), you may exe cise u he usage igh s as speci ied in he indica ed licence. h ps://c ea i ecommons.o g/licenses/by-nc-nd/4.0/ STATISTICS IN TRANSITION new se ies, Sep embe 2021 Vol. 23, No. 3, pp. 141–156, DOI 10.21307/s a ans-2021-031 Recei ed – 21.11.2019; accep ed – 03.03.2021 An applica ion o pe sis en homology and he g aph heo y o linguis ics: The case o Ti inagh and Phoenician sc ip s Haja Bouazzaoui1,Mohamed Abdou Eloma y2,My Ismail Mamouni3 ABSTRACT As he o igin o he Ti inagh sc ip emains unce ain, his wo k aims a explo ing i s p oba- ble ela edness wi h he Phoenician sc ip . Using ools om wi hin opological da a analysis and g aph heo y, he simila i y be ween he wo sc ip s is s udied. The clus e ing o hei le e shapes is pe o med based on he pai wise dis ances be ween hei opological signa- u es. The ideas p esen ed in his wo k can be ex ended o s udy he simila i y be ween any wo w i ing sys ems and as such can se e as he i s s ep o linguis s o de e mine he possibly ela ed sc ip s be o e conduc ing u he analysis. Key wo ds: opological da a analysis, pe sis en homology, g aph heo y, w i ing sys ems, Abjad sc ip s, Alphabe sc ip s, Ti inagh sc ip , Phoenician sc ip . 1. In oduc ion Li ing beings - humans and animals alike, ha e a need o sys ems o communica ion o ensu e hei su i al. Humans, by hei ingenui y, ha e de eloped w i ing sys ems as a con- en ional isual mode o ep esen hei o al communica ion. While w i ing and alking a e bo h ools o ansmi ing messages, w i ing has he ad an age o being a eliable o m o da a s o age ha obeys he usual coding and decoding ules, which imply a sha ed unde - s anding by he au ho and he eade o he se s o cha ac e s composing he used w i ing sys em. Ti inagh, which is he w i ing sys em o in e es in his pape , is he sc ip adop ed o Tamazigh o Be be languages mo e b oadly. Be be has been o iginally spoken in e i o ies anging om he A lan ic coas o Egyp be o e he a abisa ion o No h A ica. Millions o Ti inagh insc ip ions o a ious s yles and e as a oo he ocks o No h A ica and he Saha a. A long p ocess o cul u al and iden i y changes begun wi h he eme gence o Islam in he se en h cen u y, concu en ly, he linguis ic map o Ti inagh (see Figu e 1) e ac ed o e he cen u ies un il i s p esen o m, b oken in o islands dis an om each o he . 1Hassan I Uni e si y, Depa men o Ma hema ics and Compu e Science FST de Se a , IMII Labo a- o y. Add ess: Km 3, B.P.: 577 Rou e de Casablanca, Mo occo. E-mail: [email p o ec ed], ORCID: h ps://o cid.o g/0000-0003-1860-9757 2Hassan I Uni e si y, Depa men o Ma hema ics and Compu e Science FST de Se a , IMII Labo a o y. Add ess: Km 3, B.P.: 577 Rou e de Casablanca, Mo occo. E-mail: [email p o ec ed] 3Depa men o Ma hema ics, Resea ch Team o Ma hema ics, Didac ic and i s Applica ions (M@DA), CRMEF RABAT, A enue Allal Al Fassi, Madina Al I ane, 10000, Raba , Mo occo. E-mail: [email p o ec ed] 142 Bouazzaoui H., Eloma y M. A., Mamouni M.: An applica ion o pe sis en ... Figu e 1: Cu en Ti inagh speaking map in A ica. So a , he e is no conclusi e heo y abou he o igin o he Ti inagh sc ip . The majo i y o schola s suppo one hese h ee heo ies (Blanco 2014): • Sou h-Semi ic o igin (A abian and La in sc ip s); • No h-Semi ic o igin (Phoenician and/o Punic); • Independen in en ion wi h Phoenician in luence. Ou aim in he p esen wo k is o e i y whe he he Ti inagh and he Phoenician sc ip s a e indeed ela ed. F om a linguis ic poin o iew, he s udy o sc ip e olu ion is no independen om his o ical, geog aphic and cul u al ac o s. One canno hen demons a e he ela ionship be- ween sc ip s based solely on he s udy o indi idual g aphemes (B iquel-Cha onne 1997). Howe e , analyzing and compa ing le e shapes emains an impo an cons i uen o ha s udy. In o de o demons a e linguis ic ela edness and o econs uc a hypo he ical common ances al sys em o languages, linguis s ely, among o he s, on he compa a i e me hod as a echnique o s udy language de elopmen and pe o m compa isons on hese languages (McMahon, A. and McMahon, R. 2011). Howe e , he languages o compa e a e no chosen a andom, and an ini ial s age o deciding whe he some languages a e ela ed is equi ed. The p esen wo k, which s udies he ela edness o he Phoenician and Ti inagh sc ip s, ely on me hods ha could be ex ended o s udy he ela edness o any wo o he sc ip s, and as such, se e as a i s s ep o he compa a i e me hod, a leas o he ex en whe e only le e shapes a e conside ed. We belie e ha his is he i s wo k ha in es iga es he isual ela ionship be ween sc ip s using opological da a analysis (TDA). A p e ious wo k (Sadouk e al. 2020) es ab- lished a possible ela ionship be ween Phoenician and Ti inagh sc ip s using deep lea ning. The au ho s ained a classi ie on a da ase o Phoenician le e s and used a ans e lea ning sys em based on hese shapes o imp o e he pe o mance o Ti inagh handw i en cha ac e STATISTICS IN TRANSITION new se ies, Sep embe 2021 143 ecogni ion he eby in e ing a possible ela ionship be ween he wo sc ip s. S ill, as wi h all deep lea ning sys ems, la ge samples o da a we e equi ed. TDA, on he o he hand, can p o ide obus esul s wi h only small samples o da a. To e i y he ela edness o he wo sc ip s, we adop a opological da a analysis ap- p oach based on pe sis en homology and g aph heo y. We ep esen each le e o he w i ing sys ems we a e s udying as a g aph. Ou aim is o s udy he simila i y be ween he g aphs co esponding o Phoenician le e s and hose co esponding o Ti inagh le e s. In he li e a u e, many g aph simila i y measu es we e s udied among which we ci e maximum common subg aph (Fe nández and Valien e 2001), he numbe o misma ching edges (Zhu e al. 2012) and g aph edi dis ance (GED) (Gouda and Hassan 2016). GED has been he mos adop ed one. I is he leas expensi e sequence o edi ope a ions ha can ans o m a g aph G1 o a g aph G2. In p ac ice, howe e , inding he minimal edi dis ance is an NP-ha d p oblem and has he d awback o ha ing an exponen ial compu a ional complexi y in e ms o he numbe o g aph edi e ices. In his wo k, opological in o ma ion o in e es in each o hese g aphs is summa ized in pe si ence diag ams. Compu ing he Bo leneck dis ance be ween hese opological sig- na u es will se e as a mean o e i y simila i y be ween le e g aphs and hus be ween Ti inagh and Phoenician sc ip s. The pape is o ganized as ollows: in Sec ion 2, we gi e a b ie in oduc ion o ma h- ema ical concep s we will be using h oughou his pape ; we pu special emphasis on pe - sis en homology. In Sec ion 3, we desc ibe he me hod we used o pe o m ou analysis be o e closing wi h a discussion o esul s and u u e esea ch di ec ions. 2. Ma e ials and backg ound Homology o malizes he way opological spaces a e dis inguished by examining hei holes. One o he mos common app oaches o homology is simplicial homology. I is based on associa ing abelian g oups o modules o simplicial complexes buil on op o opological spaces. One o i s majo ad an ages is ha i lends i se o ela i ely easy compu a ions. We i s de ine wha simplices a e. A simplex o a p-simplex is he gene aliza ion o a iangle in p-dimension. De ini ion 1 (p-simplex) Le e0,e1,...,epbe a inely independen poin s in Rn. The associa ed con ex hull, deno ed σp= [e0,e1,...,ep], is called a p-simplex. Tha is he polyhed on: σp=∑p i=0 iei, i≥0,∑p i=0 i=1 Figu e 2: A 0-simplex is a poin , a 1-simplex is a line segmen , a 2-simplex is a iangle and a 3-simplex a e ahed on (Zhu 2013) 144 Bouazzaoui H., Eloma y M. A., Mamouni M.: An applica ion o pe sis en ... When σand αa e wo simplices such ha α⊂σ, we call αa ace o σand σa co- ace o α. De ini ion 2 (Simplicial complex) A simplicial complex K is a ini e collec ion o simplices sa is ying he ollowing condi ions: 1. Fo any σ∈K wi h a ace α, we ha e α∈K; 2. I σ1,σ2∈K hen σ1∩σ2=o σ1∩σ2∈K. The dimension o K is he maximal dimension o i s simplices. Figu e 3: Le : a simplicial complex. Righ : no a simplicial complex (Zhu 2013) De ini ion 3 (p-chain) A p-chain is a o mal ini e sum ∑iniσp i, whe e σp ia e o ien ed p-simplices o a simplicial- complex K and ni∈Z. The se Cp(K)o all p-chains o Kis a Z-module. The ollowing Z-linea map : ∂p:Cp(K)→Cp−1(K)(1) is called a bounda y map, i is de ined a he le el o he gene a o s as ollows: ∂p(σ):= p ∑ i=0 (−1)i[e0,e1,..., ˆei,...,ep](2) whe e σ= [e0,e1,··· ,ep]is an o ien ed p−simplex and ˆeimeans ha eiis omi ed. Thus, he bounda y o a e ahed on is he al e na i e sum o i s ou iangles, he bounda y o a iangle is he al e na i e sum o i s h ee edges and he bounda y o a line segmen is he di e ence o i s wo endpoin s. A di ec compu a ion shows ha ∂p◦∂p+1=0.(3) In o he wo ds Im∂p+1⊂ke ∂p.(4) This yields he ollowing exac sequence, called a chain complex o K: 0=Cn+1(K)i ,→Cn(K)∂n −→ Cn−1(K)∂n−1 −→ ··· ∂1 −→ C0(K)∂0 −→ C−1(K) = 0 (5) whe e ,→deno es he inclusion map. The igu e below illus a es he e olu ion o his chain complex. STATISTICS IN TRANSITION new se ies, Sep embe 2021 145 Figu e 4: Chain, cycle and bounda y g oups and hei mappings unde bounda y ope a- o s. ( Ho ak, Male i´ c and Rajko i´ c 2009) Elemen s o Zp:=ke ∂pa e called p-cycles, hose o Bp:=Im∂p+1a e called p-bounda ies. In pa icula , any p-bounda y is a cycle, bu he in e se does no always hold. The obs uc- ion o a cycle o be a bounda y is encoded in he quo ien Hp(K):=Zp Bp.(6) called he p- h homology g oup o K. I s ank, de ined as βp(K):=dimZHp(K),(7) is called he p- h Be i numbe o Kand i encodes he numbe o p−dimensional holes in he simplicial complex K. In pa icula , β0deno es he numbe o connec ed componen s o K. Fo mo e de ails, we e e he eade o hese s anda d e e ences (Ha che 2002) and (Spannie 1966). 2.1. Pe sis en homology Pe sis en homology, one o he main ools in opological da a analysis, p o ed i s use- ulness in many eal wo ld applica ions among which shape analysis, medical imaging and ne wo k sensing a e only a ew examples. In many o hese applica ions, da a is gi en as a poin cloud. Pe sis en homology keeps ack o homology classes as a nes ed sequence o simplicial complexes is buil on op o he da a. The “li e ime” o a homology class is an indica ion o he ele ance o i ele ance o homological in o ma ion. 146 Bouazzaoui H., Eloma y M. A., Mamouni M.: An applica ion o pe sis en ... Figu e 5: A noisy poin cloud da a Le Pbe a cloud o poin s embedded in Rn. One may associa e a il a ion o P, ha is a ini e inc easing sequence o sub-complexes P=K0⊂K1⊂ ··· ⊂ Kn.(8) Fo e e y i≤j, he inclusion map Ki,→Kjinduces he homology homomo phism i,j p:Hp(Ki)−→ Hp(Kj)(9) a each dimension p. This yields he homology sequence Hp(K0)−→ Hp(K1)··· −→ Hp(Kn).(10) As we go om Ki−1 o Ki, we gain new homology classes and lose o he s as hey become i ial o me ge wi h each o he . Pe sis en homology g oups a e de ined as ollows. De ini ion 4 The p- h pe sis en homology g oups, deno ed Hi,j p, a e de ined o be he im- ages Hi,j p:=Im i,j p. Thei anks βi,j p:= ank(Hi,j p), a e he co esponding p- h pe sis en Be i numbe s. We no e ha Hi,j p=Zp(Ki)/(Bp(Kj)∩Zp(Ki)).(11) A class γis bo n a ime =ii γ/∈Hi−1,i p. I dies a ime =j, when i becomes i ial o when i me ges wi h an olde class as we go om Kj−1 o Kj, ha is, i,j−1 p(γ)/∈Hi−1,j−1 p bu i,j p(γ)∈Hi−1,j p. The igu e below illus a es his scena io. STATISTICS IN TRANSITION new se ies, Sep embe 2021 147 Figu e 6: Example o a homology class wi h bi h ime =i, and dea h ime =j. (Edels- b unne and Ha e 2010) We can encode his e olu ion in a pe sis ence ba code, which is a se o in e als whose i s endpoin indica es he bi h- ime o he homology class, while he second one indica es i s dea h- ime. Sho line segmen s co espond o noise, while pe sis en line segmen s imply ele an homological in o ma ion. Figu e 7: Example o a poin cloud and i s associa ed Vie o is-Rips complex and ba code (Gh is 2008) Ba codes can be compu ed e icien ly by using a ma ix educ ion algo i hm. Su p is- ingly, we can ge all his in o ma ion wi h a single educ ion. We o de he ime appea ance (σi)o a simplex σias ollows: (σi)< (σj)whene e σiis a ace o σj. Then we se he bounda y ma ix,∂, which s o es all ha in o ma ion, ha is he bina y ma ix, ∂[i,j]:=1 i σiis a ace o σjo co-dimension one ; 0 o he wise. Le low(j)be he ow index o he lowes non-null coe icien (when i exis s) in he column j. A ma ix is called educed i low(j)=low(k)whene e j=k. In o he wo ds, no wo columns ha e lows in he same le el. One way o ge a educed ma ix R om he 148 Bouazzaoui H., Eloma y M. A., Mamouni M.: An applica ion o pe sis en ... bounda y ma ix ∂is o add columns om le o igh . (see Algo i hm 1). Algo i hm 1 : Smi h Reduc ion Algo i hm Inpu : Bounda y ma ix Ou pu : Reduced bounda y ma ix o j=1 o ndo while ∃j′<jwi h low(j′) = low(j)do add column j′ o column j end while end o Theo em 1 (Pai ing heo em, see (Edelsb unne and Ha e 2010)) Le R be he educed ma ix ob ained om he bounda y ma ix. The e is a pe sis ence pai ing (i,j)o a homology class whene e i =low(j). The il a ions buil on op o da a can also be desc ibed opologically using pe sis ence diag ams. These a e mul ise s o R2 ha encode in o ma ion abou homology g oups. A homology class ha appea s a ime iand disappea s a ime jis ep esen ed by he poin o coo dina es (i,j). The mul iplici y o ha poin ep esen s he numbe o ea u es wi h he same bi h and dea h imes. The pe sis ence o each class is he eal alue j−i. Figu e 8: Example o a pe sis ence diag am (Nanda 2017) In o de o compa e opological signa u es p esen in he esul ing pe sis ence diag ams, we compu e hei Bo leneck dis ance. De ini ion 5 Bo leneck dis ance Gi en wo pe sis ence diag ams D and E, hei Bo leneck dis ance (w∞) is de ined by: STATISTICS IN TRANSITION new se ies, Sep embe 2021 155 McMahon, A., McMahon, R., (2011). Language Classi ica ion by Numbe s. Ox o d: Ox- o d Uni e si y P ess. Sadouk, L. e al., (2020). Handw i en Phoenician Cha ac e Recogni ion and i s Use o Imp o e Recogni ion o Handw i en Alphabe s wi h Lack o Anno a ed Da a. In e - na ional Jou nal O Ad anced T ends In Compu e Science And Enginee ing. Fe nández, M., Valien e, G, (2001). A g aph dis ance me ic combining maximum com- mon subg aph and minimum common supe g aph. Pa e n Recogni ion Le e s, 22, pp. 753–758. Zhu, G., Lin, X., Zhu, K., Zhang, W., Xu Yu, J., (2012). T eeSpan: e icien ly compu ing simila i y all-ma ching. P oceedings O The 2012 ACM SIGMOD In e na ional Con- e ence On Managemen O Da aMay, pp. 529–540. Gouda, K., Hassan, M., (2016). CSI_GED: An E icien App oach o G aph Edi Simila - i y Compu a ion. P oc. O ICDE’16. Ha che , A., (2002). Algeb aic Topology, Camb idge Uni e si y P ess. Spanie , E., (1966). Algeb aic Topology, McG aw-Hill Inc. Edelsb unne , H., Ha e , J., (2010). Compu a ional Topology. An In oduc ion, Ame . Ma h. Soc., P o idence, Rhode Island. Gh is , R., (2008). Ba codes: he pe sis en opology o da a.Bulle in O The Ame ican Ma hema ical Socie y, 45, pp. 61–75. Gunna , C., De Sil a, V., Mo ozo , D., (2009). Zigzag pe sis en homology and eal- alued unc ions.P oceedings O The Twen y- i h Annual Symposium On Compu a ional Ge- ome y (SCG ’09), pp. 247–256. Milosa lje i´ c, N., Mo ozo , D., Sk aba, P., (2011). Zigzag pe sis en homology in ma ix mul iplica ion ime. P oceedings O The Twen y-se en h Annual Symposium On Com- pu a ional Geome y (SoCG ’11). Associa ion Fo Compu ing Machine y, New Yo k, NY, USA, pp. 216–225. Ca lsson, G., De Sil a, V., (2010). Zigzag pe sis ence. Found Compu Ma h 10, pp. 367– 405. 156 Bouazzaoui H., Eloma y M. A., Mamouni M.: An applica ion o pe sis en ... Floyd, R., (1962). Algo i hm 97: Sho es Pa h. Communica ions O The ACM, 5, p.345. Hagbe g, A., Swa , P., S Chul , D., (2008). Explo ing ne wo k s uc u e, dynamics, and unc ion using Ne wo kX. P oceedings O The 7 h Py hon In Science Con e ence (SciPy2008), Gäel Va oquaux, T a is Vaugh , And Ja od Millman (Eds), Pasadena, CA USA, 5, pp. 11–15. Mo ozo , D., (2012). Dionysus. h p://www.m z .o g/so wa e/dionysus/ Coulmas, F., (2008). Typology o W i ing Sys ems. Band 2, pp. 1380–1387. A ailable a : h ps://doi.o g/10.1515/9783110147445.2.9.1380 Gelb, I., (1963). A S udy o W i ing, Chicago Uni e si y P ess, 2nd edi ion. Hill, A., (1967). The ypology o w i ing sys ems. Pape s In Linguis ics, pp. 92–99. Ho ak, D., Male i´ c, S., Rajko i´ c, M., (2009). Pe sis en homology o complex ne wo ks. J. S a . Mech. Theo y And Expe imen , pp. 30–34. Pulg am, E., (1976). The ypologies o w i ing-sys ems, Mon Follick Se ies. Pichle , W., (2007). The o igin o he Libyco-Be be sc ip . Ac es Du Colloque In e na- ional, Le Libyco-be bé e Ou Le Ti inagh: De L’au hen ici é À L’usage P a ique, pp. 187–200. Sampson, G., (1985).W i ing Sys ems: A Linguis ic In oduc ion, Hu chinson & Co. L d, London. Slaou i Takli , M. (2004). L’alphabe La in se ai -il d’o igine be bé e?, Ha ma an, Pa is. Unge , J., DeF ancis, J. (1995). Logog aphic and Semasiog aphic W i ing Sys ems: A C i ique o Sampson’s Classi ica ion. Sc ip s And Li e acy. Neu opsychology And Cogni ion, 7, pp. 44–58. Nanda, V., (2017). Pe seus: The Pe sis en Homology So wa e. A ailable a : h p: //people.ma hs.ox.ac.uk/nanda/pe seus/ Zhu, X., (2013). Pe sis en homology: An in oduc ion and a new ex ep esen a ion o na u al language p ocessing. P oceedings O The Twen y-Thi d In e na ional Join Con e ence On A i icial In elligence.