1,722,119 research outputs found
Program transformation for functional circuit descriptions
No full textWe model sequential synchronous circuits on the logical level by signal-processing programs in an extended lambda calculus Lpor with letrec, constructors, case and parallel or (por) employing contextual equivalence. The model describes gates as (parallel) boolean operators, memory using a delay, which in turn is modeled as a shift of the list of signals, and permits also constructive cycles due to the parallel or. It opens the possibility of a large set of program transformations that correctly transform the expressions and thus the represented circuits and provides basic tools for equivalence testing and optimizing circuits. A further application is the correct manipulation by transformations of software components combined with circuits. The main part of our work are proof methods for correct transformations of expressions in the lambda calculus Lpor, and to propose the appropriate program transformations
Ambiguity of context-free languages as a function of the word length
No full textEnglische Fassung der Diplomarbeit "Grad der Mehrdeutigkeit kontextfreier Grammatiken und Sprachen".
In dieser Arbeit definieren wir ein Maß für den Grad der Mehrdeutigkeit (degree of ambiguity da) kontextfreier Grammatiken und Sprachen als die Anzahl der Ableitungsbäume in Abhängigkeit von der Länge n eines Wortes. Wir zeigen, dass es weder Sprachen noch zyklenfreie Grammatiken gibt, deren Mehrdeutigkeitsgrad stärker als 2£(n) wächst (wie z B. £(nn)). Aus [10] ist es außerdem bekannt, dass es keine Grammatiken (und somit keine Sprachen) gibt, deren Mehrdeutigkeit stärker als polynomiell, aber schwächer als exponentiell wächst (wie z. B. £(2pn). Deshalb untersuchen wir in dieser Arbeit hauptsächlich konstant mehrdeutige, polynomiell mehrdeutige und exponentiell mehrdeutige Grammatiken und Sprachen. Für jede feste, ganze Zahl k 2 N hat Maurer [8] die Existenz einer k-deutigen kontextfreien Sprache nachgewiesen. Durch Verwendung einer einfacheren Sprache, nämlich der Sprache Lk := fambm1 1 bm2 2 : : : bmk k jm;m1;m2; : : : ;mk ¸ 1; 9 i mit m = mig, und mit Hilfe von Ogden's Lemma1 erhalten wir einen wesentlich kürzeren Beweis. Ferner zeigen wir die Existenz exponentiell mehrdeutiger Sprachen. Wir zeigen, dass die Sprache L¤ { wobei L = faibicj ji; j ¸ 1g [ faibjciji; j ¸ 1g-exponentiell mehrdeutig ist, indem wir beweisen, dass das Wort (ah+h!bh+h!ch+h!)k mindestens 2k Ableitungen in jeder Grammatik G für L¤ hat, wobei k aus N ist und h die Konstante aus Ogden's Lemma für G ist. Für beliebig kleines c aus R+ entwerfen wir eine Grammatik Gc für L¤, so dass daGc · 2cn gilt. Somit gilt, dass die Sprache L¤ zwar exponentiell mehrdeutig ist, aber es gibt kein festes c aus R+ , so dass L¤ 2cn-deutig ist. Wir geben polynomiell mehrdeutige Grammatiken an und zeigen die Existenz von polynomiell mehrdeutigen Sprachen, indem wir mit Hilfe von Ogden's Lemma beweisen, dass die Anzahl der Ableitungsbäume eines Wortes der Länge n in jeder Grammatik für die Sprache Lk in der Größenordnung von (nk) liegt, wobei k eine Konstante aus N ist, und L := fambm1cbm2c : : : bmpcjp 2 N; m;m1;m2; : : : ;mp 2 N; 9i 2 f1; 2; : : : ; pg mit m = mig gilt. Durch Angabe einer O(nk){deutigen Grammatik zeigen wir schließlich, dass Lk polynomiell vom Grad k mehrdeutig ist. Außerdem entwerfen wir für jedes feste d aus R+ eine Grammatik Gd für L, so dass daGd · dn dn für genügend großes n ist.In this paper we discus the concept of ambiguity of context{free languages and grammars. We prove the existence of constant ambigu- ous, exponential ambiguous and polynomial ambiguous languages and we give examples for these classes of ambiguity
Jahresbericht 1985. Fachbereich Informatik, Universitaet Kaiserslautern
No full textTIB: ZB 4220 (1985) / FIZ - Fachinformationszzentrum Karlsruhe / TIB - Technische InformationsbibliothekSIGLEDEGerman
Universitaet Kaiserslautern, Fachbereich Informatik. Jahresbericht 1990
No full textAvailable from TIB Hannover: ZB 4220(1990) / FIZ - Fachinformationszzentrum Karlsruhe / TIB - Technische InformationsbibliothekSIGLEDEGerman
Kaiserslautern Universitaet, Fachbereich Informatik. Jahresbericht 1989
No full textSIGLETIB Hannover: ZB 4220(1989) / FIZ - Fachinformationszzentrum Karlsruhe / TIB - Technische InformationsbibliothekDEGerman
Einfuehrung der neuen Mikroelektronik (Mead-and-Conway-Methode) in der Bundesrepublik Zwischenbericht
No full textTIB: AC 9315,2 / FIZ - Fachinformationszzentrum Karlsruhe / TIB - Technische InformationsbibliothekSIGLE2. ed.DEGerman
Mensch-Rechner-Kommunikation Herkunft und Chancen eines neuen Paradigmas
No full textTIB: RN 3437 (104) / FIZ - Fachinformationszzentrum Karlsruhe / TIB - Technische InformationsbibliothekSIGLEDEGerman
Syllables and Other String Kernel extensions
No full textRecently, the use of string kernels that compare documents as a string of letters has been shown to achieve good results on text classification problems. In this paper we introduce the application of the string kernel in conjunction with syllables. Using syllables shortens the representation of documents and as a result reduces computation time. Moreover syllables provide a more natural representation of text; rather than the traditional coarse representation given by the bag-of-words, or the too fine one resulting from considering individual letters only. We give some experimental results which show that syllables can be effectively used in text-categorisation problems. In this paper we also propose two extensions to the string kernel. The first introduces a new lambda-weighting scheme, where different symbols can be given differing decay weightings. This may be useful in text and other applications where the insertion of certain symbols may be known to be less significant. We also introduce the concept of 'soft matching', where symbols can match (possibly weighted by relevance) even if they are not identical. Again, this provides a method of incorporating prior knowledge where certain symbols can be regarded as a partial or exact match and contribute to the overall similarity measure for two data items
Integrating UML Models and OWL Ontologies
No full textDie Arbeitsberichte aus dem Fachbereich Informatik dienen der Darstellung vorläufiger Ergebnisse, die in der Regel noch für spätere Veröffentlichungen überarbeitet werden. Die Autoren sind deshalb für kritische Hinweise dankbar. Alle Rechte vorbehalten, insbesondere die der Übersetzung, des Nachdruckes, des Vortrags, der Entnahme von Abbildungen und Tabellen – auch bei nur auszugsweiser Verwertung. The “Arbeitsberichte aus dem Fachbereich Informatik “ comprise preliminary results which will usually be revised for subsequent publication. Critical comments are appreciated by the authors. All rights reserved. No part of this report may be reproduced by any means or translated
- …
