Expressionsstärke

Expressionsstärke bezeichnet in der Logik, formalen Sprachen und der Informatik die Fähigkeit eines Systems, Eigenschaften, Relationen oder Berechnungen auszudrücken oder zu definieren. Sie beschreibt, welche Modelle oder Strukturen durch Sätze, Ausdrücke oder Programme charakterisiert werden können. In der Regel gilt: Je größer die Expressionsstärke, desto mehr lässt sich ausdrücken, oft aber auf Kosten von Entscheidungsfähigkeit oder Effizienz.

Man vergleicht Sprachen oder Logiken durch eine Inklusionsbeziehung: Eine Sprache L1 hat weniger Expressionsstärke als L2, wenn jeder Ausdruck in L1 auch in L2 darstellbar ist, aber nicht umgekehrt. Typische Stufen reichen von der Aussagenlogik (Aussagenkombinationen) über die Prädikatenlogik erster Ordnung (Quantoren über Objekte) bis hin zu höherdimensionalen Logiken wie der monadischen oder vollen zweiter Ordnung. Erweiterungen wie Fixed-Point-Operatoren erhöhen die Ausdrucksstärke und ermöglichen rekursive Eigenschaften (z. B. Erreichbarkeit in Graphen), oft verbunden mit Änderungen in der Entscheidbarkeit. Höherstufige Logiken können nahezu jede berechenbare Eigenschaft beschreiben, gehen damit aber häufig Verluste bei Entscheidbarkeit oder höhere Komplexität ein.

In der Praxis beeinflusst die Expressionsstärke Anwendungen in Theoretischer Informatik, Programmiersprachen, formaler Verifikation und Abfragesprachen. Stärkere Sprachen bieten mehr Ausdrucksmöglichkeiten, machen aber Analyse, Modellprüfung oder Abfrageoptimierung oft anspruchsvoller. Die Konzepte der Expressionsstärke helfen, Fähigkeiten und Grenzen eines Sprachsystems zu verstehen und zu vergleichen.