Bruce Watson - Böcker

Summability methods are transformations that map sequences (or functions) to sequences (or functions). A prime requirement for a "good" summability method is that it preserves convergence. Unless it is the identity transformation, it will do more: it will transform some divergent sequences to convergent sequences.An important type of theorem is called a Tauberian theorem. Here, we know that a sequence is summable. The sequence satisfies a further property that implies convergence.Borel's methods are fundamental to a whole class of sequences to function methods. The transformation gives a function that is usually analytic in a large part of the complex plane, leading to a method for analytic continuation.These methods, dated from the beginning of the 20th century, have recently found applications in some problems in theoretical physics.

TheSixthInternationalConferenceonImplementationandApplicationof- tomata(CIAA2001)-the?rstoneheldinthesouthernhemisphere-was heldattheUniversityofPretoriainPretoria,SouthAfrica,on23-25July2001. ThisvolumeofSpringer'sLectureNotesinComputerSciencecontainsall thepapers(includingtheinvitedtalkbyGregorv. Bochmann)thatwerep- sentedatCIAA2001,aswellasanexpandedversionofoneoftheposterpapers displayedduringtheconference. Theconferenceaddressedtheissuesinautomataapplicationandimplemen- tion. Thetopicsofthepaperspresentedinthisconferencerangedfromautomata applicationsinsoftwareengineering,naturallanguageandspeechrecognition, andimageprocessing,tonewrepresentationsandalgorithmsfore?cientimp- mentationofautomataandrelatedstructures. Automatatheoryisoneoftheoldestareasincomputerscience. Researchin automatatheoryhasbeenmotivatedbyitsapplicationssinceitsearlystagesof development. Inthe1960sand1970s,automataresearchwasmotivatedheavily byproblemsarisingfromcompilerconstruction,circuitdesign,stringmatching, etc. Inrecentyears,manynewapplicationsofautomatahavebeenfoundin variousareasofcomputerscienceaswellasinotherdisciplines. Examplesofthe newapplicationsincludestatechartsinobject-orientedmodeling,?nitetra- ducersinnaturallanguageprocessing,andnondeterministic?nite-statemodels incommunicationprotocols. Manyofthenewapplicationscannotsimplyutilize theexistingmodelsandalgorithmsinautomatatheorytosolvetheirproblems. Newmodels,ormodi?cationsoftheexistingmodels,areneededtosatisfytheir requirements. Also,thesizesofthetypicalproblemsinmanyofthenewapp- cationsareastronomicallylargerthanthoseusedinthetraditionalapplications. Newalgorithmsandnewrepresentationsofautomataarerequiredtoreducethe timeandspacerequirementsofthecomputation. TheCIAAconferenceseriesprovidesaforumforthenewproblemsand challenges. Intheseconferences,boththeoreticalandpracticalresultsrelatedto theapplicationandimplementationofautomatawerepresentedanddiscussed, andsoftwarepackagesandtoolkitsweredemonstrated. Theparticipantsofthe conferenceserieswerefrombothresearchinstitutionsandindustry. Wethankalloftheprogramcommitteemembersandrefereesfortheire?orts inrefereeingandselectingpapers. Thisvolumewaseditedwithmuchhelpfrom NanetteSaesandHannekeDriever,whiletheconferenceitselfwasrunsmoothly withthehelpofElmarieWillemse,NanetteSaes,andTheoKoopman. VI Foreword WealsowishtothanktheSouthAfricanNRF(forfundingairfares)andthe DepartmentofComputerScience,UniversityofPretoria,fortheir?nancialand logisticsupportoftheconference.WealsothanktheeditorsoftheLectureNotes inComputerScienceseriesandSpringer-Verlag,inparticularAnnaKramer,for theirhelpinpublishingthisvolume. October2002 BruceW. Watson DerickWood CIAA 2001 Program Committee BernardBoigelot Universit'edeLiege,Belgium Jean-MarcChamparnaud Universit'edeRouen,France MaximeCrochemore UniversityofMarne-la-Vall'ee,France OscarIbarra UniversityofCaliforniaatSantaBarbara,USA LauriKarttunen XeroxPaloAltoResearchCenter,USA NilsKlarlund AT&TLaboratories,USA DenisMaurel Universit'edeTours,France MehryarMohri AT&TLaboratories,USA Jean-EricPin Universit'eParis7,France KaiSalomaa Queen'sUniversity,Canada HelmutSeidl TrierUniversity,Germany BruceWatson(Chair) UniversityofPretoria,SouthAfrica EindhovenUniversity,TheNetherlands DerickWood(Co-chair) HongKongUniversityofScience andTechnology,China ShengYu UniversityofWesternOntario,Canada Table of Contents UsingFiniteStateTechnologyinNaturalLanguageProcessingofBasque...1 I"nakiAlegria,MaxuxAranzabe,NereaEzeiza,AitzolEzeiza, andRubenUrizar CascadeDecompositionsareBit-VectorAlgorithms...13 AnneBergeronandSylvieHamel SubmoduleConstructionandSupervisoryControl:AGeneralization...27 Gregorv.Bochmann CountingtheSolutionsofPresburgerEquations withoutEnumeratingThem...40 BernardBoigelotandLouisLatour Brzozowski'sDerivativesExtendedtoMultiplicities...52 Jean-MarcChamparnaudandG'erardDuchamp FiniteAutomataforCompactRepresentation ofLanguageModelsinNLP...65 JanDaciukandGertjanvanNoord PastPushdownTimedAutomata...74 ZheDang,Tev?kBultan,OscarH. Ibarra,andRichardA. Kemmerer SchedulingHardSporadicTasksbyMeans ofFiniteAutomataandGeneratingFunctions...87 Jean-PhilippeDubernardandDominiqueGeniet Bounded-GraphConstruction forNoncanonicalDiscriminating-ReverseParsers...101 JacquesFarr'eandJos'eFortesGalvez ' Finite-StateTransducerCascadetoExtractProperNamesinTexts...115 NathalieFriburgerandDenisMaurel IsthisFinite-StateTransducerSequentiable?...125 Tamas ' Ga'al CompilationMethodsofMinimalAcyclicFinite-StateAutomata forLargeDictionaries...135 JorgeGran "a,Fco. MarioBarcala,andMiguelA. Alonso BitParallelism-NFASimulation...149 JanHolub ImprovingRasterImageRun-LengthEncodingUsingDataOrder...161 MarkusHolzerandMartinKutrib X Table of Contents EnhancementsofPartitioningTechniques forImageCompressionUsingWeightedFiniteAutomata ...177 FrankKatritzke,WolfgangMerzenich,andMichaelThomas Extractionof -CyclesfromFinite-StateTransducers...190 Andr'eKempe OntheSizeofDeterministicFiniteAutomata...202 Bo?rivojMelicharandJanSkryja CrystalLatticeAutomata...214 JimMorey,KamranSedig,RobertE. Mercer,andWayneWilson MinimalAdaptivePattern-MatchingAutomata forE?cientTermRewriting...221 NadiaNedjahandLuizadeMacedoMourelle AdaptiveRule-DrivenDevices-GeneralFormulationandCaseStudy...234 Joao " Jos'eNeto TypographicalNearest-NeighborSearchinaFinite-StateLexicon andItsApplicationtoSpellingCorrection...251 AgataSavary OntheSoftwareDesignofCellularAutomataSimulators forEcologicalModeling...261 YuriVelinov RandomNumberGenerationwith?-NFAs...263 LynettevanZijl SupernondeterministicFiniteAutomata...274 LynettevanZijl Author Index...289 Using Finite State Technology in Natural Language Processing of Basque Iaeaki Alegria, Maxux Aranzabe, Nerea Ezeiza, Aitzol Ezeiza, and Ruben Urizar Ixa taldea, University of the Basque Country, Spain i. alegria@si. ehu. es Abstract.