{"id":{"repo_id":"potsdam-thes","oai_identifier":"oai:kobv.de-opus4-uni-potsdam:70408"},"canonical_url":"https://search.dev.ndltd.org/etd/potsdam-thes/oai:kobv.de-opus4-uni-potsdam:70408","repository":{"repo_id":"potsdam-thes","name":"Universität Potsdam - Thes","base_url":"https://publishup.uni-potsdam.de/opus4-ubp/oai"},"display":{"title":"Transformation of leftmost derivations in cooperating distributed grammar systems","abstract":"Cooperating distributed grammar systems allow the generation of non-context-free languages by having multiple context-free grammars derive terminal words in a concurrent way. New transformations of cooperating distributed grammar systems between various leftmost restrictions under the terminal mode of derivation are developed. The results of prior works, in particular concerning the sw-mode and ss-mode of leftmostness, are reviewed and improved upon. There, a critical flaw in the transformation from the ff-mode into the sw-mode is identified and corrected. It is also shown that this transformation is not suitable for use in top-down parsing, as the resulting cooperating distributed grammar systems do not fulfill the LL(k) condition. Further is the transformation from the ss-mode into pushdown automata analyzed for use in transforming into other modes of leftmostness. A possible improvement for transforming from the ss-mode into the ws-mode that requires less additional rules is introduced. This transformation is further expanded upon to transform from the fs-mode into the ws-mode too, establishing a previously unknown relationship between these two modes. The correctness of all transformations introduced is fully proved. Additionally, it is shown that the generative power of the fs and ws-mode is strictly stronger than context-free languages, even for just two components.","abstract_html":"Cooperating distributed grammar systems allow the generation of non-context-free languages by having multiple context-free grammars derive terminal words in a concurrent way. New transformations of cooperating distributed grammar systems between various leftmost restrictions under the terminal mode of derivation are developed. The results of prior works, in particular concerning the sw-mode and ss-mode of leftmostness, are reviewed and improved upon. There, a critical flaw in the transformation from the ff-mode into the sw-mode is identified and corrected. It is also shown that this transformation is not suitable for use in top-down parsing, as the resulting cooperating distributed grammar systems do not fulfill the LL(k) condition. Further is the transformation from the ss-mode into pushdown automata analyzed for use in transforming into other modes of leftmostness. A possible improvement for transforming from the ss-mode into the ws-mode that requires less additional rules is introduced. This transformation is further expanded upon to transform from the fs-mode into the ws-mode too, establishing a previously unknown relationship between these two modes. The correctness of all transformations introduced is fully proved. Additionally, it is shown that the generative power of the fs and ws-mode is strictly stronger than context-free languages, even for just two components.","abstract_has_math":false,"creators":["Lindner, Marc Fabian"],"institution":"Universität Potsdam","degree_name":null,"degree_level":"master","degree_discipline":null,"degree_department":null,"school":null,"contributors":["Bordihn, Henning","Frank, Mario"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2026,"date_issued":"2026-06-08","date_published":"2026-06-08","updated_at":"2026-07-24T03:52:15Z","subjects":["grammar systems","leftmost derivations","transformations","terminal derivations","top-down parsing","Grammatiksysteme","Linksableitungen","Transformationen","terminale Ableitungen"],"languages":[],"rights":["CC-BY - Namensnennung 4.0 International"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://publishup.uni-potsdam.de/frontdoor/index/index/docId/70408","outbound_label":"Repository record","outbound_source":"source_url"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Bordihn, Henning","Frank, Mario"]},{"key":"dc:creator","label":"Author","values":["Lindner, Marc Fabian"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:publisher","label":"Institution","values":["Universität Potsdam"]},{"key":"dc:type","label":"Dc Type","values":["masterThesis"]},{"key":"thesis:degree_level","label":"Degree Level","values":["master"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Universität Potsdam"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["grammar systems","leftmost derivations","transformations","terminal derivations","top-down parsing","Grammatiksysteme","Linksableitungen","Transformationen","terminale Ableitungen"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["CC-BY - Namensnennung 4.0 International"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Cooperating distributed grammar systems allow the generation of non-context-free languages by having multiple context-free grammars derive terminal words in a concurrent way. New transformations of cooperating distributed grammar systems between various leftmost restrictions under the terminal mode of derivation are developed. The results of prior works, in particular concerning the sw-mode and ss-mode of leftmostness, are reviewed and improved upon. There, a critical flaw in the transformation from the ff-mode into the sw-mode is identified and corrected. It is also shown that this transformation is not suitable for use in top-down parsing, as the resulting cooperating distributed grammar systems do not fulfill the LL(k) condition. Further is the transformation from the ss-mode into pushdown automata analyzed for use in transforming into other modes of leftmostness. A possible improvement for transforming from the ss-mode into the ws-mode that requires less additional rules is introduced. This transformation is further expanded upon to transform from the fs-mode into the ws-mode too, establishing a previously unknown relationship between these two modes. The correctness of all transformations introduced is fully proved. Additionally, it is shown that the generative power of the fs and ws-mode is strictly stronger than context-free languages, even for just two components.","Kooperierende verteilte Grammatiksysteme ermöglichen die Generierung nicht-kontextfreier Sprachen, indem mehrere kontextfreie Grammatiken gleichzeitig Terminalwörter ableiten. Es werden neue Transformationen für kooperierende verteilte Grammatiksysteme zwischen verschiedenen terminalen Linksableitungen entwickelt. Die Ergebnisse bisheriger Arbeiten, insbesondere zu sw- und ss-Ableitungen, werden überprüft und verbessert. Dabei wird ein kritischer Fehler in der Transformation vom ff-Modus in den sw-Modus identifiziert und korrigiert. Es wird außerdem gezeigt, dass diese Transformation nicht für die Verwendung beim Top-Down-Parsing geeignet ist, da die resultierenden kooperierenden verteilten Grammatiksysteme die LL(k)-Bedingung nicht erfüllen. Weiterhin wird die Transformation vom ss-Modus in Kellerautomaten mit Hinblick auf ihre Anwendung zur Transformation in andere Linksableitungen analysiert. Eine mögliche Verbesserung für die Transformation vom ss-Modus in den ws-Modus, die weniger zusätzliche Regeln erfordert, wird vorgestellt. Diese Transformation wird zudem erweitert, um auch vom fs-Modus in den ws-Modus zu transformieren und so eine bisher unbekannte Beziehung zwischen diesen beiden Modi herzustellen. Die Korrektheit aller eingeführten Transformationen wird vollständig bewiesen. Außerdem wird gezeigt, dass der fs- und ws-Modus selbst bei nur zwei Komponenten deutlich stärker ist als die kontextfreien Sprachen."]},{"key":"dc:format.medium","label":"Dc Format Medium","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Transformation of leftmost derivations in cooperating distributed grammar systems","Transformationen von Linksableitungen in kooperierenden verteilten Grammatiksystemen"]}]}],"canonical_facts":{"dc:contributor":["Bordihn, Henning","Frank, Mario"],"dc:creator":["Lindner, Marc Fabian"],"dc:description.abstract":["Cooperating distributed grammar systems allow the generation of non-context-free languages by having multiple context-free grammars derive terminal words in a concurrent way. New transformations of cooperating distributed grammar systems between various leftmost restrictions under the terminal mode of derivation are developed. The results of prior works, in particular concerning the sw-mode and ss-mode of leftmostness, are reviewed and improved upon. There, a critical flaw in the transformation from the ff-mode into the sw-mode is identified and corrected. It is also shown that this transformation is not suitable for use in top-down parsing, as the resulting cooperating distributed grammar systems do not fulfill the LL(k) condition. Further is the transformation from the ss-mode into pushdown automata analyzed for use in transforming into other modes of leftmostness. A possible improvement for transforming from the ss-mode into the ws-mode that requires less additional rules is introduced. This transformation is further expanded upon to transform from the fs-mode into the ws-mode too, establishing a previously unknown relationship between these two modes. The correctness of all transformations introduced is fully proved. Additionally, it is shown that the generative power of the fs and ws-mode is strictly stronger than context-free languages, even for just two components.","Kooperierende verteilte Grammatiksysteme ermöglichen die Generierung nicht-kontextfreier Sprachen, indem mehrere kontextfreie Grammatiken gleichzeitig Terminalwörter ableiten. Es werden neue Transformationen für kooperierende verteilte Grammatiksysteme zwischen verschiedenen terminalen Linksableitungen entwickelt. Die Ergebnisse bisheriger Arbeiten, insbesondere zu sw- und ss-Ableitungen, werden überprüft und verbessert. Dabei wird ein kritischer Fehler in der Transformation vom ff-Modus in den sw-Modus identifiziert und korrigiert. Es wird außerdem gezeigt, dass diese Transformation nicht für die Verwendung beim Top-Down-Parsing geeignet ist, da die resultierenden kooperierenden verteilten Grammatiksysteme die LL(k)-Bedingung nicht erfüllen. Weiterhin wird die Transformation vom ss-Modus in Kellerautomaten mit Hinblick auf ihre Anwendung zur Transformation in andere Linksableitungen analysiert. Eine mögliche Verbesserung für die Transformation vom ss-Modus in den ws-Modus, die weniger zusätzliche Regeln erfordert, wird vorgestellt. Diese Transformation wird zudem erweitert, um auch vom fs-Modus in den ws-Modus zu transformieren und so eine bisher unbekannte Beziehung zwischen diesen beiden Modi herzustellen. Die Korrektheit aller eingeführten Transformationen wird vollständig bewiesen. Außerdem wird gezeigt, dass der fs- und ws-Modus selbst bei nur zwei Komponenten deutlich stärker ist als die kontextfreien Sprachen."],"dc:format.medium":["application/pdf"],"dc:publisher":["Universität Potsdam"],"dc:rights":["CC-BY - Namensnennung 4.0 International"],"dc:subject":["grammar systems","leftmost derivations","transformations","terminal derivations","top-down parsing","Grammatiksysteme","Linksableitungen","Transformationen","terminale Ableitungen"],"dc:title":["Transformation of leftmost derivations in cooperating distributed grammar systems","Transformationen von Linksableitungen in kooperierenden verteilten Grammatiksystemen"],"dc:type":["masterThesis"],"thesis:degree_level":["master"],"thesis:institution_name":["Universität Potsdam"]},"updated_at":"2026-07-24T03:52:15Z"}