Derick Wood - Böcker

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.

This book constitutes the strictly refereed post-workshop proceedings of the First International Workshop on Implementing Automata, WIA'96, held in London, Ontario, Canada, in August 1996.The volume presents 13 revised full papers together with an introduction and survey. The papers explore the use of software tools in formal language theory; various issues involved in the implementation of automata of all types are discussed. As the first book focusing on implementing automata, this collection of research papers defines the state of the art in the area. Generally speaking, the book advocates the practice of theory in computer science.

This book constitutes the thoroughly refereed post-workshop proceedings of the Third International Workshop on Principles of Document Processing, PODP'96, held in Palo Alto, California, USA, in September 1996. The book contains 13 revised full papers presented as chapters of a coherent, monograph-like book. The papers focus equally on the theory and the practice of document processing. Among the topics covered are theory of media, cross media publishing and multi-modal documents, SGML content models, grammar-compatible stylesheets, multimedia documents, temporal constraints in multimedia, hypertext representation, contextual knowledge, structured documents for IR, Web-publishing, virtual documents, etc.

This book constitutes the thoroughly refereed revised post-workshop proceedings of the Second International Workshop on Implementing Automata, WIA'97, held in London, Ontario, Canada, in September 1997.The book presents 21 revised full papers carefully reviewed and selected for inclusion in the book; also included is an introductory overview. The papers discuss issues involved in the implementation of automata of all types also covering aspects from areas such as natural language processing, pattern matching, speaker recognition, VLSI testing, etc. This book reflects the state-of-the-art in this emerging area of interdisciplinary research.

This book constitutes the thoroughly refereed post-workshop proceedings of the 4th International Workshop on Principles of Digital Document Processing, PODDP'98, held in Saint Malo, France, in March 1998. The 12 revised full papers presented were carefully reviewed during two rounds of selection for inclusion in the book. The book is divided into sections on document models and structures, characterization of documents and corpora, and accessing collections of documents.

Restricted-orientation convexity is the study of geometric objects whose intersections with lines from some fixed set are connected. This notion generalizes standard convexity and several types of nontraditional convexity. We explore the properties of this generalized convexity in multidimensional Euclidean space, describes restricted-orientation analogs of lines, hyperplanes, flats, and halfspaces, and identify major properties of standard convex sets that also hold for restricted-orientation convexity. We then introduce the notion of strong restricted-orientation convexity, which is an alternative generalization of convexity, and show that its properties are also similar to those of standard convexity.

Restricted-orientation convexity is the study of geometric objects whose intersections with lines from some fixed set are connected. This notion generalizes standard convexity and several types of nontraditional convexity. We explore the properties of this generalized convexity in multidimensional Euclidean space, describes restricted-orientation analogs of lines, hyperplanes, flats, and halfspaces, and identify major properties of standard convex sets that also hold for restricted-orientation convexity. We then introduce the notion of strong restricted-orientation convexity, which is an alternative generalization of convexity, and show that its properties are also similar to those of standard convexity.