- Im Mittelpunkt der Betrachtung steht die Frage, wie „schwierig“ es ist, die Kommunikationskomplexitaet einer regulaeren Sprache zu bestimmen. Regulaere Sprachen sind ein grundlegender Baustein der Chomsky-Hierarchie und von grosser Bedeutung in der Praktischen und Theoretischen Informatik. Die Kommunikationskomplexitaet ist ein Mass, das die minimale Anzahl an Bits misst, die zwei Parteien A und B austauschen muessen, um eine Funktion auszuwerten, deren Eingabe auf A und B aufgeteilt ist. Der Begriff "schwierig" bezieht sich auf die Platz- und Zeitkomplexitaet einer deterministischen Turingmaschine. In der Arbeit koennen diverse Haerte- und Mitgliedschaftsresultate bzgl. der Komplexitaetsklassen PS, NP und P erzielt werden. Bei der Untersuchung spielt die Repraesentationsform der regulaeren Sprache eine grosse Rolle. Zugelassen sind endliche Automaten, regulaere Ausdruecke und Grammatiken. Die Methoden beinhalten Reduktions- und algebraische Techniken. Autor: Christian BrandlВнимание! На данный товар не распространяются ни оптовые, ни накопительные скидки. Эта книга будет изготовлена в соответствии с Вашим заказом по технологии Print-on-Demand. Print-on-Demand - это технология печати книг по Вашему заказу на цифровом типографском оборудовании.