Theoretischen_informatik
- Negation der Pumpingeigenschaft
- Skolem Normalform
- Skolemisierung
- Erfüllbarkeitsreduktion
- Erfüllbarkeitsäquivalenz prädikatenlogische Formeln
- Existenzquantor
- Allquantor
- Quantor
- Universelle Formel
- Existenzielle Formel
- Satz prädikatenlogische Formel äquivalent zu PNF
- Pränexe Normalform
- Äquivalenz prädikatenlogische Formeln
- Formelspiel
- Turingreduktion
- Satz Turingreduktion ist transitiv
- Satz Turingreduktion ist reflexiv
- Folgerungsbeziehungsproblem der Prädikatenlogik
- Erfüllbarkeitsproblem der Prädikatenlogik
- Erfüllbarkeit (Aussagenlogik)
- Erfüllbarkeitsproblem der Aussagenlogik
- Satz Unerfüllbar gdw bot herleitbar
- Satz Formel aus Menge herleitbar gdw Menge und Negation der Formel unerfüllbar
- Prädikatenlogische Folgerungsbeziehung
- Folgerungsbeziehung
- Aussagenlogische Folgerungsbeziehung
- Satz Halteproblem für Turingmaschinen ist unentscheidbar
- Beispiel KFG aus if-else Kellerautomat
- Substitution
- Grund-atomare prädikatenlogische Formel
- Atomare prädikatenlogische Formel
- Interpretation von prädikatenlogische Formeln
- Variablenbelegungsveränderung
- Zusammenfassung Syntax Prädikatenlogik
- Term
- Prädikatenlogische Formel
- Interpretation von Termen
- Struktur
- Grundterm
- Signatur
- Relationale Signatur
- Algebraische Signatur
- Universale Sprache
- Satz Vollständigkeit der aussagenlogischen Resolution
- Resolutionsbeweis
- Resolvente
- Aussagenlogischen Formel
- nicht-triviale semantische Eigenschaft
- Satz von Friedberg und Muchnik
- Erkannte Sprache einer TM
- Polynomialzeitreduktion
- Log-Raum-Reduktion
- Satz Auf entscheidbare Sprache Turing-reduzierbare Sprache ist entscheidbar
- Reduktion
- Komplement einer Sprache
- Satz Jede Sprache ist Turing-reduzierbar zu ihrem Komplement
- Satz Jede Sprache ist einseitig Turing-reduzierbar zu ihrem Jump
- Jump
- Satz Allgemeine Wortproblem für Turingmaschinen ist unentscheidbar
- Allgemeines Wortproblem für Turingmaschinen
- Satz epsilon-Halteproblem für Turingmaschinen ist unentscheidbar
- epsilon-Halteproblem für Turingmaschinen
- Halteproblem für Turingmaschinen
- Halteproblem
- Satz von Rice
- Satz von Kleene und Post
- Einseitige Turingreduktion
- Leere Sprache
- Anwendung Pumpinglemma für Kontextfreie Sprachen
- Pumpinglemma für Kontextfreie Sprachen
- Satz Größe eines Syntaxbaum
- Pumpingeigenschaft für Kontextfreie Sprachen
- Pumpinglemma für reguläre Sprachen
- Satz Jede reguläre Sprache wird von DKA erkannt
- Erweiterte Folgekonfiguration eines Kellerautomaten
- Durch leeren Keller erkannte Sprache eines NDKA
- Durch Endzustand erkannte Sprache eines NDKA
- Deterministischer Kellerautomat
- Satz Umwandlung NDKA in äquivalenter KFG
- Sprache IfElse
- Satz Umwandlung KFG in äquivalenter NDKA
- Nichtdeterministischer Kellerautomat
- Ableitung in Satzform
- Satz durch Endzustand und durch leeren Keller erkannt ist äquivalent
- Kontextfreie Sprache
- Automatentheorie
- Satz NDKA von Endzustand zu äquivalenten leeren Kelller
- Satz NDKA von leeren Keller zu äquivalenten Endzustand
- Satz NDKA erkennt w-w-reversed
- Berechnung eines NDKA
- Erkannte Sprache eines NDKA
- Satz ungelese Eingabe und unbenutzer Speicher beeinflusst Erweiterte Folgekonfiguration nicht
- Folgekonfiguration eines Kellerautomaten
- Konfiguration eines Kellerautomaten
- Sprache Palindrom
- Datenstruktur
- Kontextfreie Grammatik
- Ableitung mit Produktionsregeln
- Mehrdeutige Kontextfreie Grammatik
- Eindeutige Kontextfreie Grammatik
- Satz Syntaxbaum, erweiterte Ableitung und rekursive Inferenz sind äquivalent
- erweiterte Ableitung
- Syntaxbaum
- Ertrag eines Syntaxbaums
- Rekursive Inferenz
- Satz Jede reguläre Sprache ist auch kontextfrei
- WortKFG-Algorithmus
- Produzierte Sprache einer kontextfreien Grammatik
- Produkt einer kontextfreien Grammatik
- Minimaler DEA
- Satz NEA zu regulärer Ausdruck
- Zustand aus einem GNEA entfernen
- Urbilder regulärer Sprachen
- Berechnung eines GNEA
- Berechnung eines NEA
- Generalisierter nichtdeterministischer endlicher Automat
- Regulärer Ausdruck
- Satz Kleene Hülle eines NEAs
- Satz Konkatenation zweier NEAs
- Satz Vereinigung zweier NEAs
- Universelle Turingmaschine
- Satz Komplement von Allgemeine Wortproblem ist nicht erkennbar
- Satz Allgemeine Wortproblem ist erkennbar
- Satz SUBSET-SUM is NP-vollständig
- Entscheidungsproblem
- Kodierung einer TM
- Abschlusseigenschaften der regulären Sprachen
- Satz Regulärer Ausdruck zu NEA
- Satz DEA zu NEA
- Satz Korrektheit Potenzmengenkonstruktion ohne epsilon-Kanten
- epsilon-Eliminierung
- epsilon-Pfad
- Epsilon-Kante
- Potenzmengenkonstruktion
- w-Pfad
- epsilon-Hülle
- Satz reverse ist nicht sequentiell
- Funktion reverse
- Lemma des linear beschränkten Abstandswachstum
- Lemma des linear beschränkten Längenwachstum
- Abstand
- Sequenzielle Funktion
- Satz raise ist nicht sequentiell
- Funktion raise
- Berechenbare Funktion
- Pumpingeigenschaft
- Sprache
- Reguläre Sprache
- Erkannte Sprache eines DEA
- Berechnung eines DEA
- Endlicher Automat
- Berechnung
- Berechnung einer TM
- Deterministischer endlicher Automat
- Kommutativität der Disjunktion
- Äquivalenzumformung
- Aussagenlogische Gesetze
- Satz TQBF ist PSPACE-vollständig
- Ersetzungslemma
- Äquivalente Substitution
- Kommutativität der Konjunktion
- Äquivalenz aussagenlogischer Formeln
- Aussagenlogische Variable
- Boolescher Wert
- Erfüllbarkeitsproblem für quantifizierte boolesche Formeln
- Junktor
- Variablen einer aussagenlogischen Formel
- Lemma Tautologie gdw neg unerfüllbar
- Unerfüllbarkeit (Aussagenlogik)
- Tautologie
- 1-Belegung
- 0-Belegung
- Knappe Variablenbelegung
- Auswertung einer aussagenlogischen Formel unter einer Belegung
- Variablenbelegung
- Passende Variablenbelegung
- Wahrheitswerte
- Satz Variablen und Junktoren
- Satz Anzahl der Konfigurationen eines LBTM
- Satz EQ-ROBP in BPP
- Satz NL teil von P
- Komplexitätsklasse
- Satz FORMULA-GAME ist PSPACE-vollständig
- Problem E gewinnt Formelspiel
- Gewinnstrategie
- Spiele
- Satz 3SAT ist NP-vollständig
- Satz 3SAT is poly reduzierbar auf CLIQUE
- nichtdeterministisch polynomielle Zeit
- Satz Redundanz zusätzlicher Bänder
- LSPACE
- deterministisch polynomielle Zeit mit Orakel-TM
- Orakel-Turingmaschine
- Orakel
- Problem der Äquivalenz zweier Regulärer Ausdrücke mit Potenzierung
- Reguläre Sprache mit Potenzierung
- Problem der Äquivalenz zweier Regulärer Ausdrücke
- EXPSPACE-Vollständigkeit
- PSPACE-Vollständigkeit
- PSPACE
- deterministisch polynomielle Zeit
- EXPTIME
- EXPSPACE
- Satz PSPACE Teilmenge von EXPTIME
- Raumhierarchiesatz
- Zeitkonstruierbare Funktion
- Hierarchiesätze
- Satz TQBF ist nicht NL
- Satz NL ist eine echte Teilmenge von PSPACE
- Raumkonstruierbare Funktion
- Satz coPATH is in NL
- Satz PATH is NL-vollständig
- Satz PATH ist in P
- NLSPACE
- coNL
- coNP
- Nur-Lesen Eingabeband Turingmaschine
- Satz Falls B in L und A log-raum reduzierbar auf B dann A in L
- Satz NP-vollständig durch Reduktion von NP-vollständig
- NL-Vollständigkeit
- NP-Schwer
- NL-Schwere
- Logarithmische Platzkomplexität berechenbare Funktion
- log space transducer
- Satz Anzahl der Konfiguration einer ROITM
- Satz von Savitch
- Satz Anzahl der Konfiguration einer TM
- Satz 0^k1^k ist L
- Sprache 0^k1^k
- Satz von Cook und Levin
- Graphentheorie
- Problem der Äquivalenz zweier ROBP
- Problem der exakten Überdeckung
- Satz RELPRIME ist in P
- Hamiltonkreisproblem
- Verifizierer
- Strukturelle Induktion
- Sortierverfahren
- Quicksort
- Algorithmus Topo-Sortierung
- Selectionsort
- Radixsort
- Bucketsort
- Mergesort
- Insertionsort
- Bubblesort
- Algorithmus von Dijkstra
- Algorithmus von Bellman und Ford
- Binäre Suche
- Verstärkungslemma
- Traveling Salesman Problem
- Quantencomputer
- Median-Algorithmus
- Güte von Approximationsalgorithm
- Boolesche Funktion
- Big O
- Simons-Problem
- Simons-Algorithmus
- Optimalitätsprinzip von Bellman
- Teilsummenproblem
- SPACE
- small o
- Satz PSPACE gleich NPSPACE
- Satz P Teilmenge von PSPACE
- Satz NP gdw. NDTM
- Satz Laufzeit zusätzlicher Bänder
- Satz Hamiltonwegproblem ist in NP
- Satz Laufzeit Determinisierung von Nichtdeterminismus
- Satz Hamiltonwegproblem ist in EXPTIME
- Satz Falls B NP-vollständig und B in P dann P gleich NP
- Satz Falls SAT in P dann P gleich NP
- Satz CLIQUE is NP-vollständig
- RELPRIME
- Rekursionsgleichung
- Randomisierte polynomielle Zeit
- Probabilistische Entscheidbarkeit
- Polynomieller Verifizierer
- Primzahltest
- Polynomialzeit berechenbare Funktion
- Polynomialzeit
- Platzkomplexität
- Null-Fehler probabilistische polynomielle Zeit
- P versus NP
- NTIME
- NSPACE
- NPSPACE
- NP-Vollständigkeit
- nichtdeterministische Polynomialzeit
- Landau-Symbole
- Färbungsproblem
- Faktorisierungsproblem
- coRP
- beschränkte Fehlerwahrscheinlichkeit probabilistische polynomielle Zeit
- Vervollständigte Entfernungsmatrix
- TIME
- Multigraph
- k-Färbung
- Hamiltonwegproblem
- Eulerkreis
- Vereinigung von regulären Sprachen
- Buchstaben
- Äquivalenz DEA, NEA und Reg
- Alphabet
- Turingmaschine
- Reguläre Urbildmengen
- Mehrband-Turingmaschine
- Nichtdeterministische Turingmaschine
- Deterministische Turingmaschine
- Satz Redundanz von Nichtdeterminismus
- Probabilistische Turingmaschine
- Linear beschränkte Turingmaschine
- Äquivalente Automaten
- Dynamische Programmierung
- Baum