Quadratisches Verhältnis zwischen nichtdeterministischem und deterministischem Raum?

Der Satz von Savitch zeigt, dass für alle ausreichend großen Funktionen f und der Beweis, dass dies eng ist, seit Jahrzehnten ein offenes Problem ist .$\mathrm{NSPACE}(f(n)) \subseteq \mathrm{DSPACE}(f(n)^2)$$f$

Nehmen wir an, wir nähern uns dem Problem vom anderen Ende. Nehmen Sie der Einfachheit halber das boolesche Alphabet an. Der von einem TM zur Entscheidung einer berechenbaren Sprache verwendete Speicherplatz hängt häufig eng mit dem Logarithmus der Anzahl der vom Automaten, der das TM für jeden regulären Teil einer Sprache simuliert, verwendeten Zustände zusammen. Dies motiviert die folgende Frage.

Sei die Anzahl syntaktisch unterschiedlicher DFAs mit n Zuständen und sei N n die Anzahl unterschiedlicher NFAs mit n Zuständen. Es ist einfach zu zeigen, dass lg N n in der Nähe von ( lg D n ) 2 liegt .$D_n$$n$$N_n$$n$$\lg N_n$$(\lg D_n)^2$

Ferner sei die Anzahl der unterschiedlichen regulären Sprachen sein , die von einem DFA mit erkannt werden können n Zuständen und lassen N ' n die Anzahl von einem NFA anerkannt sein.$D_n'$$n$$N_n'$

Ist bekannt, ob nahe an ( lg D ' n ) 2 liegt ?$\lg N_n'$$(\lg D_n')^2$

Mir ist nicht klar, wie und D ' n oder N n und N ' n zueinander in Beziehung stehen oder wie eng sie sind. Wenn sich all dies auf eine bekannte Frage in der Automatentheorie bezieht, wäre ein Hinweis oder ein Zeiger wünschenswert. Dieselbe Frage ist aufgrund derselben Überlegung auch für Zweiwege-Automaten relevant, und ich interessiere mich besonders für diese Version.$D_n$$D_n'$$N_n$$N_n'$

In meiner Arbeit mit Domaratzki und Kisman, "Über die Anzahl der von endlichen Automaten mit n Zuständen akzeptierten unterschiedlichen Sprachen", die in J. Automata, Languages ​​and Combinatorics 7 (2002) veröffentlicht wurde, haben wir bewiesen, dass wenn die Anzahl von ist verschiedene Sprachen, die von NFAs mit n Zuständen über einem k- Buchstaben-Alphabet akzeptiert werden , und g k ( n ) ist in ähnlicher Weise die Anzahl von verschiedenen Sprachen, die von DFAs akzeptiert werden, dann für festes k ≥ $G_k (n)$$n$$k$$g_k (n)$$k \geq 2$

(i) ist bis zu Ausdrücken kleinerer Ordnung asymptotisch k n log $\log g_k (n)$$kn\log n$

(ii) ist bis zu Ausdrücken kleinerer Ordnung asymptotisch zwischen ( k - 1 ) n 2 und k n 2 .$\log G_k (n)$$(k-1)n^2$$kn^2$