Structured numbers c ○ Springer-Verlag 1998 Proper

ActaInformatica35,1–15(1998)cSpringer-Verlag1998StructurednumbersPropertiesofahierarchyofoperationsonbinarytreesVincentD.Blondel?InstituteofMathematics,UniversityofLi`ege,B-4000Li`ege,Belgium(e-mail:[e-mail])Received:11December1995/30December1996Abstract.Weintroduceahierarchyofoperationson(finiteandinfinite)binarytrees.Theoperationsareobtainedbysuccessiverepetitionofoneinitialopera-tion.Thefirstthreeoperationsaregeneralizationsoftheoperationsofaddition,multiplicationandexponentiationforpositiveintegers.1IntroductionTheproductoftwopositiveintegersaandbisequaltothesumofbfactorseachequaltoa.Thebthexponentofa,denotedbyab,cansimilarlybedefinedastheproductofbfactorseachequaltoa.Theprocessofgettingnewoperationsbyrepeatingoldonesendswithexponentiationbecausethislastoperationisnotassociative.Thedefinitionab=aaa:::a|{z}bfactors(1)isambiguoussinceforexample(44)4==4(44).Forthetherighthandsideof(1)tobewelldefinedboththenumberoffactorsandtheorderinwhichtheoperationsareperformedhavetobespecified.Awayofdoingthisistoaskthesecondoperandtocarrynotonlyaquan-titativeinformation,thenumberoftimesaisrepeated,butalsoastructuredinformation,theorderinwhichtheoperationsareperformed.Binarytreesarenaturallydesignatedobjecttoconveysuchastructuredinformation.Thenumberofexternalnodes(leaves)ofabinarytreecanbeusedtospecifythenumberoffactors,andthestructureofthetreecanthenbeusedtospecifytheorderinwhichtheoperationsareperformed.?PartsofthisworkwerecompletedwhiletheauthorwasatOCIAMOxford,atKTHStockholmandatINRIAParis.2V.D.BlondelInthispaper,wedefinecountablymanyinternaloperationsonbinarytrees.Thefirstoperation,whichwedenoteby:1,isobtainedbyformingthebinarytreewhoseleftandrightsubtreesareequaltotheoperands.Thisoperationisnotassociative.Thesecondoperation:2isdefinedasfollows:Fromthebinarytreesaandbweconstructthebinarytreea:2bbyrepeatingtheoperation:1onthetreeawiththestructuredictatedbyb.Inthesameway,wedefineanoperation:3byrepeating:2,anoperation:4byrepeating:3,etc.Weeventuallyobtaincountablymanyinternaloperations(:kfork1)withthedefinitiona:kb=a:k−1a:k−1a:k−1::::k−1a|{z}bfactorsThenumberofexternalnodesofthebinarytreeresultingfromtheoperation:1,:2and:3areequaltothesum,productandexponentiationofthenumberofexternalnodesoftheoperands.Thesethreeoperationsarethoughtofasbinarytreescounterpartsoftheusualoperationsofaddition,multiplicationandexponentiation.Theoperations:kfork4havenonaturalnumbercounterpartssinceforthesecasesthestructureofthetreeshavetobetakenintoaccounttocomputethenumberofexternalnodesofa:k-product.Theobjectofthispaperistostudysomeofthepropertiesoftheoperations:kdescribedaboveandformalizedinthesecondsectionofthepaper.InSect.3theoperationsareshowntosatisfyalgebraicpropertiesthatgeneralizeelementarypropertiesforintegers.InSect.4weshowthatbinarytreescanbedecomposedinauniquewayasproductsofprimebinarytrees.InSect.5weanalysetheoperations:kfork4.InSect.6wedescribevariousintegervaluedfunctionsassociatedtotreesandshowhowthesefunctionsbehavewithrespectto:k-productsofbinarytrees.Inafinalsectionwearguethatthenotionsintroducedforfinitebinarytreescanbegeneralizedforinfinitetrees.Thisisachievedbyformalizingbinarytreesbymeansoffactoriallanguages.Differentauthorshaveproposedtocontinuethehierarchy+;;onnat-uralnumbersbyintroducingoperationsof“super-exponentiation”.D.Knuth’srecursivedefinition[18]isab=a(a(a(a:::a):::))|{z}bab=a(a(a(a:::a):::))|{z}ba:::|{z}kb=a:::|{z}k−1(a:::|{z}k−1a::::::|{z}k−1a):::))|{z}bThisdefinitioncoincide,moduloelementarynotationalmodifications,withthedefinitionoriginallygivenbyAckermannofarecursivefunctionthatisnotprimitiverecursive(see[13]).Thedefinitionhasthedisadvantageofmakinganarbitrarychoiceonhowthenon-associativeoperationsareperformedand,asaresult,theseoperationsexhibitpooralgebraicproperties(see,however,[1]).Structurednumbers3Operationsongraphs,treesandbinarytreesconstituteaclassicalobjectofstudyintheoreticalcomputerscience(see[20],[21],[19],[17,Vol.1Section2.3])butwehavefoundnoreferencethatusestheparticularstructureofbinarytreesasameanfordefiningrepeatedoperations.Thecontributionthatisprobablyclosesttooursisthe“arithmeticofshapes”developedbyI.M.Etheringtonhalfacenturyagointhecontextofgenetics.Thetransmissionofaprobabilitydistribu-tionofgenesbymatingisanoperationthatiscommutativebutnotassociative.Inordertodescribethisoperation,Etheringtonhasintroducedin[6]operationsontreesthataresimilarto:1;:2and:3andthathavegivenrisetothewidelystudiedgeneticalgebras(see[6],[15]and[5]).Theoperations:kfork4arenotdefinedinthecontextofgeneticalgebrasbecausethetreesconsideredtherearenotorderedandthereisnonaturaldefinitionof:kfork4forunorderedtrees.Motivatedbytheremarksmadeinthisintroduction,binarytreesareintro-ducedin[2],[3]and[4]asonepossiblerepresentationoftheconceptof“struc-turednumber”.Amotivationforthisterminologyisjustifiedbythefollowingobservation:Freegroupswithasimplegeneratorareisomorphicto(Z;+),freemonoidswithasinglegeneratorareisomorphicto(N;+)andfreegroupoidswithasinglegeneratorareisomorphicto(BT;:1)whereBTdenotesthesetofbinarytreesand:1isthe