Please use this identifier to cite or link to this item: http://dx.doi.org/10.25673/32915
Title: Regel- und Symbolkomplexität kontextfreier Sprachen unter ausgewählten Operationen
Author(s): Harbich, Ronny
Referee(s): Dassow, JürgenLook up in the Integrated Authority File of the German National Library
Granting Institution: Otto-von-Guericke-Universität Magdeburg, Fakultät für Informatik
Issue Date: 2020
Extent: vii, 142 Seiten
Type: HochschulschriftLook up in the Integrated Authority File of the German National Library
Type: Doctoral Thesis
Exam Date: 2019
Language: German
Publisher: Prosodia, Verlag für Musik und Literatur, Tangermünde
URN: urn:nbn:de:gbv:ma9:1-1981185920-331116
Subjects: Theoretische Informatik
Abstract: Wir untersuchen kontextfreie Sprachen in Bezug auf die Beschreibungskomplexitäten Regel- und Symbolkomplexität nach Anwendung ausgewählter Sprachoperationen (z. B. Vereinigung). Kontextfreie Sprachen werden durch kontextfreie Grammatiken allein durch Platzhalter/ Variablen, Buchstaben, Ersetzungsregeln und eine für kontextfreie Grammatiken festgelegte Vorgabe der Regelanwendung erzeugt. Eine regel-minimale (kontextfreie) Grammatik ist eine kontextfreie Grammatik, die die geringste Regelanzahl für die kontextfreie Sprache L, die sie erzeugt, hat, bezogen auf alle kontextfreien Grammatiken, die L erzeugen. Bei Konstruktion einer regel-minimalen Grammatik G, die eine Sprache L erzeugt, gibt es die Möglichkeit, L in andere Sprachen zu zerlegen, die unter Anwendung gewisser Operationen wieder L ergeben. So könnte L derart in Sprachen L1 und L2 zerlegt werden, dass mithilfe der Operation Vereinigung gerade L = L1 [ L2 gelte. Anschließend werden für L1 und L2 regel-minimale Grammatiken G1 bzw. G2 konstruiert. Die Regelkomplexitäten von G, G1 und G2 können nun verglichen werden: So könnte die addierte Anzahl der Regeln von G1 und G2 größer sein als die von G – oder umgekehrt oder gleich. Wir zeigen in dieser Arbeit, welche Komplexitätsänderungen für regel-minimale Grammatiken bei der Sprachzerlegung prinzipiell möglich sind: Es sei Prod(L) die Anzahl an Regeln, die eine regel-minimale Grammatik benötigt, um eine kontextfreie Sprache L zu erzeugen. Für zwei natürliche Zahlen n und m ist dann CProd[ (n,m) = {Prod(L1 [ L2) | Prod(L1) = n, Prod(L2) = m, L1 und L2 sind kontextfreie Sprachen} die Menge möglicher Regelkomplexitäten, die zwei beliebige kontextfreie Sprachen mit der minimalen Regelanzahl n bzw. m unter Vereinigung [ haben können. Dies lässt sich analog für weitere Operationen definieren. Für m n sind die folgenden Aussagen ein Teil der wesentlichen Ergebnisse dieser Arbeit: • Unter der Operation Spiegelbild gilt CProd()R (n) = {n} . • Unter der Operation Vereinigung gilt 6, . . . , n + m + 2 2 CProd [ (n,m) = CProd[ (m, n) /3 n + m + 3, . . . für n 2,m 2. • Unter der Operation Konkatenation gilt n + 2, . . . , n + m + 1 2 CProd · (n,m) = CProd· (m, n) /3 n + m + 2, . . . für n 5,m 5. • Unter der Operation Kleene-Abschluss gilt CProd() (n) = 8>>< >>: {1} für n = 0 {1, 2} für n = 1 {2, . . . , n + 2} sonst. • Unter der Operation Homomorphismus (Menge aller Homomorphismen Hom) gilt CProdHom (n) =({0} für n = 0 {1, . . . , n} sonst. • Unter der Operation Inverser Homomorphismus (Menge aller inversen Homomorphismen Hom-1) gelten {0} = CProdHom-1 (0), N = CProdHom-1 (n) für n 1. • Unter der Operation Schnitt mit regulärer Sprache (Menge aller Schnitte mit regulärer Sprache Reg) gelten {0} = CProdReg (0), {0, 1} = CProdReg (1), N0 = CProdReg (n) für n 2. Zuvor Genanntes untersuchen wir zudem analog für symbol-minimale Grammatiken – hier werden die Anzahl der Platzhalter/Variablen und Buchstaben in den Regeln als Maß verwendet. Wir erhalten für die Mengen möglicher Symbolkomplexitäten unter Sprachoperationen im Wesentlichen – bezogen auf die Mengen möglicher Regelkomplexitäten unter Sprachoperationen – ähnliche Ergebnisse.
URI: https://opendata.uni-halle.de//handle/1981185920/33111
http://dx.doi.org/10.25673/32915
Open Access: Open access publication
License: (CC BY-SA 4.0) Creative Commons Attribution ShareAlike 4.0
Appears in Collections:Fakultät für Informatik

Files in This Item:
File Description SizeFormat 
Harbich_Ronny_Dissertation_2019.pdfDissertation1.18 MBAdobe PDFThumbnail
View/Open


This item is licensed under a Creative Commons License Creative Commons