- AutorIn
- Steffen Märcker
- Titel
- Charakterisierung erkennbarer Baumreihen über starken Bimonoiden durch gewichtete MSO-Logik
- Zitierfähige Url:
- https://nbn-resolving.org/urn:nbn:de:bsz:15-qucosa2-164894
- Schriftenreihe
- Abschluss- und Qualifikationsarbeiten aus der Fakultät für Mathematik und Informatik
- Datum der Einreichung
- 03.12.2010
- Abstract (DE)
- Endliche Wortautomaten ermöglichen es, reguläre Wortsprachen sowohl zu erkennen als auch zu erzeugen. Julius Richard Büchi gelang es, diese erkennbaren Wortsprachen mithilfe der monadischen Logik zweiter Stufe, kurz MSO, zu charakterisieren [7, 19]. Dieses Ergebnis wurde dann auf erkennbare Baumsprachen, das heißt Mengen von geordneten Bäumen, die durch einenAufwärtsbaumautomaten erkannt werden, erweitert [11, 28]. Anstelle der <-Relation auf den Positionen eines Wortes tritt dabei die Kindrelation edgei(x; y) für die Positionen eines Baumes. Die erkennbaren Wort- und Baumsprachen haben breite Anwendung in der Informatik gefunden. Zu den bekanntesten gehören beispielsweise reguläre Ausdrücke und Syntaxbäume vieler Programmiersprachen. Im Zusammenspiel mit XML ist die Schemasprache RelaxNG zur Dokumentvalidierung [9, 29], im Gegensatz zu XML-Schema, durch die reiche Theorie erkennbarer Baumsprachen fundiert.
- Freie Schlagwörter (EN)
- bimonoid, tree series, weighted MSO logic, weighted tree automata
- Klassifikation (DDC)
- 000
- BetreuerIn Hochschule / Universität
- Prof. Dr. Manfred Droste
- Dr. Ingmar Meinecke
- Den akademischen Grad verleihende / prüfende Institution
- Universität Leipzig, Leipzig
- Version / Begutachtungsstatus
- angenommene Version / Postprint / Autorenversion
- URN Qucosa
- urn:nbn:de:bsz:15-qucosa2-164894
- Veröffentlichungsdatum Qucosa
- 20.10.2017
- Dokumenttyp
- Diplomarbeit
- Sprache des Dokumentes
- Deutsch