Akzeptieren (Automaten- und Komplexitätstheorie)

Akzeptieren ist ein Begriff aus der Automaten- und Komplexitätstheorie, Teilgebieten der theoretischen Informatik. Die Eigenschaft, dass ein Automat eine Eingabe akzeptiert ist eng verwandt mit der Entscheidbarkeit.

• Ein Algorithmus akzeptiert eine Sprache A, genau dann wenn er für genau die Elemente aus A eine positive Antwort zurückliefert.
• Ein Algorithmus entscheidet eine Sprache A, genau dann wenn er in jedem Falle terminiert und für genau die Elemente aus A eine positive Antwort zurückliefert (Dies impliziert, dass er für alle Eingaben, die nicht in A liegen, eine negative Antwort zurückliefert).

Die Unterscheidung zwischen Akzeptieren und Entscheiden ist insbesondere dann wichtig, wenn nichtdeterministisch (siehe auch NP (Komplexitätsklasse)) gerechnet wird oder wenn es unendlich lange Berechnungen geben kann (siehe Rekursive Aufzählbarkeit).

Literatur

• Uwe Schöning: Theoretische Informatik – kurzgefasst. Spektrum Akademischer Verlag, 2001, ISBN 3-8274-1099-1. 

Weblinks

Wiktionary: akzeptieren – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen