Christian Brandl

Berechnungskomplexität: Kommunikationskomplexität und reguläre Sprachen

Algebraische Methoden im Gebiet der Kommunikationskomplexität

• Broschiertes Buch

Produktbeschreibung

Im Mittelpunkt der Betrachtung steht die Frage, wie schwierig es ist, die Kommunikationskomplexität einer regulären Sprache zu bestimmen. Reguläre Sprachen sind ein grundlegender Baustein der Chomsky-Hierarchie und von großer Bedeutung in der Praktischen und Theoretischen Informatik. Die Kommunikationskomplexität ist ein Maß, das die minimale Anzahl an Bits misst, die zwei Parteien A und B austauschen müssen, um eine Funktion auszuwerten, deren Eingabe auf A und B aufgeteilt ist. Der Begriff "schwierig" bezieht sich auf die Platz- und Zeitkomplexität einer deterministischen Turingmaschine. In der Arbeit können diverse Härte- und Mitgliedschaftsresultate bzgl. der Komplexitätsklassen PS, NP und P erzielt werden. Bei der Untersuchung spielt die Repräsentationsform der regulären Sprache eine große Rolle. Zugelassen sind endliche Automaten, reguläre Ausdrücke und Grammatiken. Die Methoden beinhalten Reduktions- und algebraische Techniken. Autor: Christian Brandl

Produktdetails

• Verlag: Südwestdeutscher Verlag für Hochschulschriften
• Seitenzahl: 156
• Deutsch
• ISBN-13: 9783838122229
• ISBN-10: 3838122224
• Artikelnr.: 32552398

Autorenporträt

Name: Christian Brandl Akademischer Grad: Dr. rer. nat. Geburtsdatum: 24.12.1977 Geburtsort: Hermannstadt Schulausbildung: 1997, Abitur Hochschulstudium: 1998-2004, Mathematik und BWL Promotion: 2010 zum Dr. rer. nat. Berufstätigkeit: Assistent an der Ruhr-Universität Bochum