Riassunto
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´e
Contenuti
Using Finite State Technology in Natural Language Processing of Basque.- Cascade Decompositions are Bit-Vector Algorithms.- Submodule Construction and Supervisory Control: A Generalization.- Counting the Solutions of Presburger Equations without Enumerating Them.- Brzozowski’s Derivatives Extended to Multiplicities.- Finite Automata for Compact Representation of Language Models in NLP.- Past Pushdown Timed Automata.- Scheduling Hard Sporadic Tasks by Means of Finite Automata and Generating Functions.- Bounded-Graph Construction for Noncanonical Discriminating-Reverse Parsers.- Finite-State Transducer Cascade to Extract Proper Names in Texts.- Is this Finite-State Transducer Sequentiable?.- Compilation Methods of Minimal Acyclic Finite-State Automata for Large Dictionaries.- Bit Parallelism - NFA Simulation.- Improving Raster Image Run-Length Encoding Using Data Order.- Enhancements of Partitioning Techniques for Image Compression Using Weighted Finite Automata.- Extraction of ?-Cycles from Finite-State Transducers.- On the Size of Deterministic Finite Automata.- Crystal Lattice Automata.- Minimal Adaptive Pattern-Matching Automata for Efficient Term Rewriting.- Adaptive Rule-Driven Devices - General Formulation and Case Study.- Typographical Nearest-Neighbor Search in a Finite-State Lexicon and Its Application to Spelling Correction.- On the Software Design of Cellular Automata Simulators for Ecological Modeling.- Random Number Generation with ?-NFAs.- Supernondeterministic Finite Automata.
Le informazioni nella sezione "Su questo libro" possono far riferimento a edizioni diverse di questo titolo.
