Halbringe : Algebraische Theorie und Anwendungen in der Informatik

Der Begriff des Halbringes entsteht aus dem des Ringes, indem man auf die Gruppeneigenschaft (und seltener auch auf die Kommutativitiit) der Addition verzichtet. So bilden die natiirlichen Zahlen einen Halbring, die sicherlich iilteste algebraische Struktur, in der Menschen gerechnet haben. Zahlreiche Arbeiten tiber Halbril1ge sind seit etwa 50 Jahren erschienel1. AniaB dazu war, jedenfalls teilweise, das Auftretel1 von Halbringen als Positivbereiche partiell geordneter Ringe und Korper, bei topologischen Fragestellungen, und nicht zuletzt beim Aufbau der Arithmetik im Zusammenhang mit entsprechenden Fragen des Schulunterrichts. Besonderes Interesse verdienen Halbringe da­ durch, daB sie unterdessen in wachsendem MaBe, oft ohne Bezug auf die bereits vorhandene Literatur, als Hilfsmittel in verschiedenen Gebieten der Informatik verwendet werden. In dieser Situation mochten wir eine Einfiihrung in die algebraische Theorie der Halbringe vorlegen, in der auch einige Anwendungen in der Theoretischen Informatik ausfiihrlich behandelt werden. Dabei haben wir uns inhaltlich weitgehend auf die allgemeinen Grundlagen einer algebraisehen Halbringtheo­ rie und auf solche Teilgebiete dieser Theorie besehriinkt, die ftir die eben genannten Anwendungen benotigt werden. Weiterhin legen wir hier, wie ja aueh bei der Behandlung von Ringen iiblieh, einen Halbringbegriff zugrunde, der die Kommutativitiit der Addition einsehlieBt (vgl. Definition 2. 1 im ersten Kapitel). Damit haben wir die gelegentlich in der Literatur auch auftreten­ den Halbril1ge mit nichtkollllllutativer Addition ausgeklammert, deren Unter­ suchung zwar fiir sieh reizvoll, dartiber hinaus jedoch von weit geringerem Interesse ist und oft erheblich mehr Aufwand erfordert.