Implementation and Application of Automata: 6th International Conference, CIAA 2001, Pretoria, South Africa, July 23-25, 2001. Revised Papers

Front Cover
Bruce Watson, Derick Wood
Springer Science & Business Media, Jan 16, 2003 - Computers - 294 pages
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 IŠaki Alegria, Maxux Aranzabe, Nerea Ezeiza, Aitzol Ezeiza, and Ruben Urizar Ixa taldea, University of the Basque Country, Spain i. alegria@si. ehu. es Abstract.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Using Finite State Technology in Natural Language Processing of Basque
1
Cascade Decompositions are BitVector Algorithms
13
A Generalization
27
Counting the Solutions of Presburger Equations without Enumerating Them
40
Brzozowskis Derivatives Extended to Multiplicities
52
Finite Automata for Compact Representation of Language Models in NLP
65
Past Pushdown Timed Automata
74
Scheduling Hard Sporadic Tasks by Means of Finite Automata and Generating Functions
87
Improving Raster Image RunLength Encoding Using Data Order
161
Enhancements of Partitioning Techniques for Image Compression Using Weighted Finite Automata
177
Extraction of varepsilonCyclesfrom FiniteState Transducers
190
On the Size of Deterministic Finite Automata
202
Crystal Lattice Automata
214
Minimal Adaptive PatternMatching Automata for Efficient Term Rewriting
221
Adaptive RuleDriven Devices General Formulation and Case Study
234
Typographical NearestNeighbor Search in a FiniteState Lexicon and Its Application to Spelling Correction
251

BoundedGraph Construction for Noncanonical DiscriminatingReverse Parsers
101
FiniteState Transducer Cascade to Extract Proper Names in Texts
115
Is this FiniteState Transducer Sequentiable?
125
Compilation Methods of Minimal Acyclic FiniteState Automata for Large Dictionaries
135
Bit Parallelism NFA Simulation
149
On the Software Design of Cellular Automata Simulators for Ecological Modeling
261
Random Number Generation with oplusNFAs
263
Supernondeterministic Finite Automata
274
Author Index
289
Copyright

Other editions - View all

Common terms and phrases

Bibliographic information