Persistent arrays, path problems, and context-free languages [Elektronische Ressource] / vorgelegt von Oliver Glier

Description

Technische Universit t Darmstadt,Fachbereich Informatik.Genehmigte Dissertation zur Erlangungdes akademischen Grades Dr. rer. nat.Persistent Arrays,Path Problems,and Context-free LanguagesDissertation ? vorgelegt vonDipl.-Inform. Oliver Gliergeboren in Frankfurt am MainTag der Einreichung: 31. Januar 2005 Referenten:Tag der m ndlichen Pr fung: 21. April 2005Prof. Dr. Hermann K.-G. Walter, DarmstadtProf. Dr. J rgen Albert, W rzburgDarmst dter Dissertationen D17 Priv-Doz. Dr. Ulrike Brandt, Darmstadt0.1 Deutschsprachige ZusammenfassungDas Ziel dieser Arbeit ist es, einen Rahmen f r die Modellierung sprachbeschr nkter Wegeproblemein Graphen zu schaffen. Von konzeptioneller Seite sind da kontextfreie Grammatiken und Semiringezu nennen. Kontextfreie Grammatiken erlauben die Beschreibung rekursiver generativer Prozesse,wie sie beispielsweise in der nat rlicher Sprache auftauchen oder zur Beschreibung vonZellwachstum dienen k nnen. Sie erfassen au erdem die Struktur einiger dynamischer Programmier-schemata, so wie sie zum Beispiel im CYK Algorithmus f r kontextfreies Parsing oder in manchenpseudopolynomiellen Algorithmen f r schwere Probleme benutzt werden.Die Verbindung kontextfreier Grammatiken mit Wegeproblemen in Graphen erlauben die Modellierungzus tzlicher formalsprachlicher Einschr nkungen der m glichen Wege. Auf der anderen Seite k nnenkontextfreie Grammatiken analog zum algebraischen Wegeproblem mit Semiringwerten ausgestattetwerden.

Sujets

• Informatik
• Mathematics

Informations

• Publié par: technischen_universitat_darmstadt
• Publié le: 01 janvier 2005
• Nombre de lectures: 44
• Langue: Deutsch

Extrait