Komplexität endlicher selbst-verifizierender Automaten

Selbst-verifizierende endliche Automaten sind eine natürliche Erweiterung nichtdeterministischer endlicher Automaten, die in symmetrischer Weise für jedes Eingabewort entweder mindestens eine akzeptierende oder mindestens eine verwerfende Berechnung liefern. Dies hat den Vorteil, dass sie niemals eine falsche Antwort geben. Mittels Definition einer Erweiterung der Potenzmengenkonstruktion sowie eines Mengenabzählarguments wird gezeigt, dass die Komplexität der Transformation selbst-verifizierender endlicher Automaten in äquivalente deterministische endliche Automaten substantiell geringer ist als die Transformation allgemeiner nichtdeterministischer endlicher Automaten.

Authors: Assent I.
Published in: Tagungsband Informatiktage 2003
Sprache: DE
Jahr: 2003
ISBN: 3-920560-21-3
Konferenz: Informatiktage
Typ: Tagungsbeiträge
Forschungsgebiet: