; TeX output 2006.12.30:1710 header=pstricks.proheader=pst-dots.proheader=pst-node.proKE&:9color push Blackhtml:color push gray 0 color pop html:G color pop3ڍ:9|&html: html:.MTvkcolor push Black color popZVg5PSfile=logo129.eps llx=0 lly=0 urx=99 ury=16 rwi=28807~color push Black color popN q cmbx12Anely
Self-GeneratingSetsandMorphisms.s獒 XQ ff cmr12David/GarthandAdamGouge WDivision/ofMathematicsandComputerScience ;T4ruman/StateUniversity =pKirksville,/MO63501 dUSA (html:color push cmyk 0 1 0 0߆T ff cmtt12dgarth@truman.edu html: color pop (html:color push cmyk 0 1 0 0acg938@truman.edu html: color pop^1 vcolor push Black color pop r"V
3
cmbx10Abstract]lcolor push Black color pop-̻K`y
3
cmr10Kim!bMerlingdenedaself-generatingsetb>
3
cmmi10Sfofintegersasfollows.9Assume1isa
_mem!bMeroofS ,andifxisinS,then2xand4x !",
3
cmsy10 1oarealsoinS.9:Weestudysimilar_self-generatingasetsofin!tegerswhosegeneratingfunctionscomefromaclassofane_functionsforwhic!hthecoMecientsonxarepMowersofaxedbase.lWeeprovethat_foran!ypMositiveintegerm,Ktheresultingsequence,reducedmoMdulom,istheimageof_aninnitew!ordthatisthexedpMointofamorphismoveranitealphabMet.W5Weealso_pro!vethattheresultingc!haracteristicsequenceofS<#istheimageofthexedpMoint_oframorphismofconstan!tlength,andisthereforeautomatic.CZWeethengiveseveral_examples&ofself-generatingsetswhoseexpansionsinacertainbasearec!haracterized_b!yt5sequencesofintegerswithmissingbloMcksofdigits."ThisexpandsupMonearlierwork_b!yAllouche,Shallit,andSk!ordev.ݍFinallye,wegiveanotherpMossiblegeneralizationof_theforiginalsetofKim!bMerling..html: html:*N G cmbx121(Inutro =ductionb#XQ cmr12KimrbSerling[!html:color push cmyk 0 1 0 04 html: color pop]denedaself-generatingset+g cmmi12Sasfollows.html: html:xcolor push Black\h1. color pop_1bSelongstoS ;Mhtml: html:#?color push Black\h2. color pop_ifxbSelongstoS ,then2xand4x,!",
cmsy10 1belongtoS ;andhtml: html:color push Black\h3. color pop_nothingelsebSelongstoS .SqWVritingtheinrtegersinSinincreasingordergivesthesequenceL&11;ꦹ2;3;4;6;7;8;11;12;14;15;16;22;23;24;27;28;30;31;32;:::ʜ; :9color push Black 1G color pop *KE&:9color push Blackhtml:color push gray 0 color pop html:G color pop3ڍ&:9whicrhisSloane's1߆T cmtt12A052499["html:color push cmyk 0 1 0 07 html: color pop].8ReducingthesequencemoSdulo2,weobtain V1;ꦹ0;1;0;0;1;0;1;0;0;1;0;0;1;0;1;0;0;1;0;::::9KimrbSerlinghfoundthatthislastsequence,fXstartingatthesecondterm,isthewrell-known :9FibSonacciw%wrord.VRecallthattheFibonacciwrordcanbeobtainedasthexedpoinrtofthe:9morphismM0!01,f<1!0.avThepapSerbryKimbSerlingalsonotedthatthesequenceRJ(n)of:9rankspast1oftheevrentermsofSis r!RJ(n)UR=1;ꦹ3;4;6;8;9;11;:::B;:9whicrhissequenceA000201["html:color push cmyk 0 1 0 07 html: color pop]. -Alloucrhe,Shallit,andmSkordev[html:color push cmyk 0 1 0 02 html: color pop]madesomeadditionalinterestingobservXationsabSout:9S .In$particular,Ktheyshorwed$thatthesetT:=URS 1,thesetobtainedfromSbrysubtracting:91fromalltheelemenrtsofS ,isalsoself-generatingasfollows::9UThtml: html:*color push Black\h1. color pop_0bSelongstoThtml: html:color push Black\h2. color pop_IfxbSelongstoTnthen2x+1and4x+2belongtoThtml: html:color push Black\h3. color pop_NothingelsebSelongstoTƹ. Inaddition,[theyshorwedthatTdisthesetofinrtegerswhosebase2representationdoSesnot conrtain`thebloSck00.0sThesebinaryexpansionscorrespSondtothelazyFibonacciexpansionsofthesetofnaturalnrumbSers.KimrbSerlingkO[!html:color push cmyk 0 1 0 05 html: color pop]generalizedthenotionofself-generatingsetsofintegersinthefollowingwrayV."{LetxFI>bSeacounrtablesetofanefunctionswithintegercoSecients."{LetS2 cmmi8F
ǹbSethesetofTnrumbSerssatisfyingtheconditionsthat1UR2SFO,andifx2SF
andfQ2Fƹ,thenfG(x)2SFO.KimrbSerling'sepaperconrtainedseveralexamples. ThepapSerbyAllouche,TShallit,andSkrordevư[html:color push cmyk 0 1 0 02 html: color pop]citedsomeoftheseexamplesinconnectionwithsequencesofintegerswithmissingbloScrks.YFVormostoftheseexamplestheyshowedthatthecharacteristicsequenceofSFis2-automatic.MTheythenaskred,\HowfarcanthesequencepropSosedbryKimbSerlingbSe generalized?"tInparticulartheyaskred,Q;\UnderwhichconditionsisthecorrespSondingcrharacteristicysequenceautomatic?"SRWVeaddressthesequestionsforageneralclassofanefunctions.FVortheremainderofthispapSer,letFbethefamilyoffunctionsdenedasfollorws.r0LetvXandabSepositivreintegers,let`iObSeintegerssatisfying 1UR=`|{Y cmr80V`1`2`vandletbiObSeinrtegerssatisfyingvb0V=UR0; Nand$0bi,a`8:; cmmi6i 1Pforz1ivn9:FVor0URiv8letfidڹ(x)=a2`8:i%XxJ bi,TanddeneF=URffi,:0ivn9g. LetSUֹdenotethesetSF describSedearlier.8WVeprorvethefollorwingtworesults.UThtml: html: :9color push Black 2G color pop
KE&:9color push Blackhtml:color push gray 0 color pop html:G color pop3ڍ&:9color push Black3N cmbx12Theorem1.I color pop2@ cmti12Lffet1mbeapositiveinteger.aYThenthesequenceS\reducedmodulomisthe :9image,bundertacffoding,oftaninniteworffdthatisaxedpointofamorphismoveranite:9alphabffet.:9UThtml: html:*color push BlackTheorem 2. color popThe35charffacteristicsequenceofSisa-automatic. TheyfamilyFmconsideredhereisslighrtlymoregeneralthanasimilarfamilystudiedbyKimrbSerling[!html:color push cmyk 0 1 0 05 html: color pop].(Inparticular,TheaddedseveralrestrictionstothefunctionsinF3EthatensurethatYthesetsfjf
(S )arepairwisedisjoinrt. RInthiscasethenumbSersinSarematchedinone-to-onecorrespSondencewiththewrordsoverthealphabSetf0;:::ʜ;vn9g.X/FVorsuchsetshealsoRstudied,0forxedj ӹ,thedistributionofthenrumbSersRffjf
(x)UR:x2S ginS.&AsaresultofTheoremlhtml:color push cmyk 0 1 0 01 html: color popthesefrequencies,Jwhentheyexist,arecoSordinatesofanormalizedeigenrvectoroftheincidencematrixofthemorphismcorrespSondingtoitsPrerron-FVrobeniuseigenrvXalue([html:color push cmyk 0 1 0 01 html: color pop],Theorem8.4.6).WVeprorveTheoremshtml:color push cmyk 0 1 0 01 html: color popandhtml:color push cmyk 0 1 0 02 html: color popinSectionshtml:color push cmyk 0 1 0 03 html: color popandhtml:color push cmyk 0 1 0 04 html: color pop,respSectivelyV.~TheproSofsgiverisetosimpleGalgorithmsforconstructingthemorphisms.jThealgorithmsalsorevrealthatTheoremshtml:color push cmyk 0 1 0 01 html: color popɼandhtml:color push cmyk 0 1 0 02 html: color popholdwhenthefunctionsinFkareoftheformfidڹ(x)=a2`8:i%XxB+bi.InɼSectionhtml:color push cmyk 0 1 0 05 html: color popwremenrtion someexamplesofself-generatingsetsthathavefurtherconnectionswithsequencesof inrtegerswithmissingbloScks.InSectionhtml:color push cmyk 0 1 0 06 html: color popwesuggestanotherpSossiblegeneralizationoftheKimrbSerlingsetinwhichtheseresultsapplyV.6IWebSegin,phowever,byprovingsomenecessarylemmas.Vhtml: html: 2(PreliminaryzLemmasforTheoremhtml:color push cmyk 0 1 0 01 html: color popb#InthissectionwreshowhowtoputatreestructureonSthatgivesrisetothemorphisms.6LetLUR=max3|f`0;:::ʜ;`v
g,/andjletBX=URmaxfb0;:::ʜ;bv
g.-LetS)=URfsnPg2K cmsy81RAn=1=fs1V