|
Showing 1 - 8 of
8 matches in All Departments
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. The authors explore the properties of
this generalized convexity in multidimensional Euclidean space, and
describ restricted-orientation analogs of lines, hyperplanes,
flats, halfspaces, and identify major properties of standard convex
sets that also hold for restricted-orientation convexity. They 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 that 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. The authors explore the
properties of this generalized convexity in multidimensional
Euclidean space, and describ restricted-orientation analogs of
lines, hyperplanes, flats, halfspaces, and identify major
properties of standard convex sets that also hold for
restricted-orientation convexity. They 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 that of standard convexity.
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 ...1 77
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 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.
|
Automata Implementation - Second International Workshop on Implementing Automata, WIA'97, London, Ontario, Canada, September 18-20, 1997, Revised Papers (Paperback, 1998 ed.)
Derick Wood, Sheng Yu
|
R1,639
Discovery Miles 16 390
|
Ships in 10 - 15 working days
|
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 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.
|
Automata Implementation - First International Workshop on Implementing Automata, WIA '96, London, Ontario, Canada, August 29 - 31, 1996, Revised Papers (Paperback, 1997 ed.)
Darrell Raymond, Derick Wood, Sheng Yu
|
R1,598
Discovery Miles 15 980
|
Ships in 10 - 15 working days
|
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.
|
You may like...
Loot
Nadine Gordimer
Paperback
(2)
R398
R330
Discovery Miles 3 300
Loot
Nadine Gordimer
Paperback
(2)
R398
R330
Discovery Miles 3 300
|