Unäre stochastische Automaten
- Wir untersuchen das Verhalten von unären stochastischen endlichen Automaten mit Hilfe von Methoden der Theorie der homogenen Markovketten. Für unäre stochastische Automaten mit E-isoliertem Cutpoint lambda und n Zuständen bestimmen wir eine obere Schranke für die Größe des zyklischen Teils eines optimalen äquivalenten DFAs. Ein Ergebnis von Milani und Pighizzini zeigt bereits, dass für den zyklischen Teil des äquivalenten DFAs O(e exp(sqrt(n ln n))) Zustände ausreichen und in unendlich vielen Fällen auch Omega(eexp(sqrt(n ln n))) Zustände benötigt werden, wobei die Größe von E keine Rolle spielt. Wir zeigen die obere Schranke n exp (1/2E) für die Größe des zyklischen Teils und weisen nach, dass der optimale DFA für jedes c < 1 in unendlich vielen Fällen mehr als n exp (c/2E) viele Zustände im zyklischen Teil benötigt. Wir weisen auch nach, dass es eine unendliche Familie endlicher unärer Sprachen gibt, für die es jeweils einen PFA mit n Zuständen und 1/4-isoliertem Cutpoint gibt, während der optimale, DFA e exp(Omega x sqrt(n ln n)) Zustände im Anfangspfad benötigt.
Deutsches Urheberrecht