(nach Mojżesz Presburger, 1904-1943)
- Prädikatenlogik
(d. h. alle Quantoren
∀,∃,
alle Booleschen Verknüpfungen)
- Signatur: Fun.-Symbole 0, 1, +,
Rel.-Symbole = , < ,≤
- 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)
(untere Schranke! selten!)
2014-07-06
