Theoretische Informatik: Eine umfassende Einführung

این مقدمه تئوری زبان‌های رسمی، تئوری محاسبه‌پذیری و مروری بر نظریه پیچیدگی را پوشش می‌دهد. همه شواهد به تفصیل مورد بحث قرار گرفته است. اثبات های دشوار به اختصار خلاصه نمی شوند، اما با جزئیات بیشتری مورد بررسی قرار می گیرند. در عین حال، این کتاب مقدمه ای بر تکنیک اثبات ارائه می دهد و بنابراین هم برای مبتدیان و هم برای مدرسان مناسب است. فصل بزرگ‌تری به مدل‌های محاسباتی جایگزین، از جمله ماشین‌های ثبت دوگانه، سیستم‌های برچسب، ماشین‌های وانگ، شبکه‌های رودینگ، اتصال و محاسبات برگشت‌پذیر می‌پردازد.

Diese Einführung umfasst die Theorie der formalen Sprachen, die Theorie der Berechenbarkeit und einen Überblick über die Komplexitätstheorie. Alle Beweise werden ausführlich behandelt. Schwierige Beweise werden nicht etwa abgekürzt, sondern eingehender behandelt. Damit bietet dieses Buch zugleich eine Einführung in die Technik des Beweisens und ist somit sowohl für Anfänger als auch Dozenten geeignet. Ein größeres Kapitel behandelt alternative Rechenmodelle, unter anderem Zwei-Register-Maschinen, Tag-Systeme, Wang-Maschinen, Rödding-Netze, Splicing und reversible Rechnungen.