Schwere Aufgaben für Compiler (Bsp 2)

Äquivalenz von algebraischen Ausdrücken (Polynomen)

• ist unentscheidbar (Hilberts 10. Problem)
• Anwendung: Optimierung von Zählschleifen

vgl. (In-)Äquivalenz regulärer Ausdrücke, kleinster äquivalenter regulärer Ausdruck