(nach Mojżesz Presburger, 1904-1943)
- Prädikatenlogik
(d. h. alle Quantoren
∀,∃
mathend000#,
alle Booleschen Verknüpfungen)
- Signatur: Fun.-Symbole 0, 1, +
mathend000#,
Rel.-Symbole = , < ,≤
mathend000#
- interpretiert in der Struktur
der natürlichen Zahlen
Resultate:
- Presburger 1929:
Allgemeingültigkeit und Erfüllbarkeit
solcher Formeln sind entscheidbar
- Fischer und Rabin 1974:
Entscheidungsproblem hat Komplexität
∈Ω(22n)
mathend000#
(untere Schranke! selten!)
2014-03-31
