Sprachen, die von DFAs mit Polynomgröße erkannt werden

Für ein festes endliches Alphabet , eine formale Sprache über ist regelmäßig , wenn es einen gibt deterministische endliche Automaten (DFA) über , die akzeptiert genau .L Σ Σ $\Sigma$$L$$\Sigma$$\Sigma$$L$

Ich interessiere mich für Sprachen, die "fast" regelmäßig sind, in dem Sinne, dass sie von Automatenfamilien erkannt werden können, deren Größe nur polynomiell mit der Wortlänge wächst.

Formal lassen Sie mich sagen , dass eine formale Sprache wird anerkannt durch eine DFA - Familie , wenn für jedes Wort , im Stich gelassen, ist in wenn akzeptiert (egal ob das andere akzeptiert oder nicht), und lassen Sie mich p-reguläre Sprachen als Sprachen definieren, die von einer PTIME-berechenbaren DFA-Familie mit polynomieller Größe erkannt werden , und zwar dort ist ein Polynom so dass für alle$L$ w ∈ & Sigma; * n = | w | w L A n w A $(A_n)$$w \in \Sigma^*$$n = |w|$$w$$L$$A_n$$w$$A_i$P | A n | ≤ P ( n ) $(A_n)$$P$$|A_n| \leq P(n)$$n$. (Diesen Namen "p-regular" habe ich mir ausgedacht. Ich möchte wissen, ob es dafür bereits einen anderen Namen gibt. Beachten Sie, dass dies nicht mit p-regular-Sprachen im Sinne von Permutationsautomaten identisch ist .)

Diese Klasse von p-regulären Sprachen umfasst natürlich reguläre Sprachen (nimm einfach für alle , wobei ein DFA ist, das die reguläre Sprache erkennt); aber es ist eine strenge Obermenge davon: Zum Beispiel ist bekannt, dass kontextfrei, aber nicht regulär ist, aber es ist p- regular ( nur Vorkommen von und Vorkommen von ). Da es sich bei den Automaten jedoch um polynomgroße DFAs handeln muss , sind dies bei einigen formalen Sprachen (tatsächlich bei einigen kontextfreien Sprachen) nicht der Falln A { a n b n ≤ n ≤ N } A n n a n $A_n = A$$n$$A$$\{a^n b^n \mid n \in \mathbb{N}\}$$A_n$$n$$a$$n$$b$p-regular: Zum Beispiel ist die Sprache der Palindrome nicht p-regular, weil Sie intuitiv, wenn Sie die erste Hälfte eines Wortes gelesen haben, so viele verschiedene Zustände haben müssen, wie es mögliche Wörter gibt, weil Sie brauchen werden genau diese erste Hälfte mit der zweiten abzustimmen.

Die Klasse der p-regulären Sprachen ist also eine strikte Obermenge regulärer Sprachen, die mit kontextfreien Sprachen nicht zu vergleichen ist. Tatsächlich scheint es, dass Sie sogar eine Hierarchie von Sprachen erhalten können, indem Sie p-reguläre Sprachen basierend auf dem kleinsten Grad des Polynoms für das sie -regulär sind, unterscheiden . Es ist nicht schwer, Beispiele zu konstruieren, um zu zeigen, dass diese Hierarchie streng ist. obwohl ich die Wechselwirkung zwischen dieser und einer alternativen Definition der Hierarchie, die auch die Komplexität der Berechnung von einschränken würde, noch nicht gut verstehe .P A $P$$P$$A_n$

Meine Frage ist: Wurde diese Klasse, die ich p-regular nenne, und die zugehörige Hierarchie zuvor untersucht? Wenn ja, wo und unter welchem ​​Namen?

(Eine mögliche Verknüpfung besteht mit dem Feld- oder Streaming-Algorithmus oder dem Online-Algorithmus. In der Terminologie des Streaming-Algorithmus für Spracherkennungsprobleme interessiert mich die Klasse (oder Hierarchie) von Sprachen, die einen deterministischen Erkennungsalgorithmus mit einem Durchgang haben können. unter Verwendung einer polynomiellen Anzahl von Zuständen (also einer logarithmischen Speichergröße), aber ich habe keine Definition dieser Klasse in dieser Abhandlung oder verwandten Abhandlungen gefunden. Beachten Sie jedoch, dass in meiner Formulierung des Problems die Länge des Wortes im Voraus bekannt ist , Was in einem Streaming-Kontext weniger natürlich ist: Im Streaming könnte man dies als einen unendlichen Automaten, ein spezielles "Wortende" -Symbol und eine Einschränkung sehen, dass die Anzahl der erreichbaren Zustände nach dem Lesen von Zeichen in polynomisch ist$n$$n$. Ich denke, dass diese Unterscheidung einen Unterschied macht, mögliches Beispiel: Sprache von binären Wörtern, deren Wert durch ihre Länge teilbar ist, die für eine feste Länge einfach ist, aber (ich nehme an) nicht durch einen unendlichen Automaten im bisherigen Sinne dargestellt werden kann, weil keine Identifikationen vorliegen kann gemacht werden, wenn die Länge nicht im Voraus bekannt ist.)

(Die Motivation für diese p-reguläre Klasse ist, dass einige Probleme, wie die Wahrscheinlichkeit einer Sprachzugehörigkeit für probabilistische Wörter, PTIME zu sein scheinen, nicht nur, wenn die Sprache regulär ist, sondern auch, wenn sie p-regulär ist, und ich versuche es genau zu charakterisieren, unter welchen Umständen diese Probleme auffindbar sind.)

die Frage scheint nicht viel untersucht worden zu sein (eine Möglichkeit ist der Versuch, eine Beziehung zu einer "nahe gelegenen" Komplexitätsklasse zu finden, z. B. P / Poly usw.); Hier ist allerdings mindestens ein Hinweis, der darauf eingeht:

• Sprachoperationen mit regulären Ausdrücken der Polynomgröße Gruber / Holzer

  Diese Arbeit beschäftigt sich mit Fragen, inwieweit reguläritätserhaltende Sprachoperationen die beschreibende Komplexität regulärer Ausdrücke beeinflussen. Es werden einige Sprachoperationen identifiziert, die für reguläre Ausdrücke in dem Sinne durchführbar sind, dass das Ergebnis der Operation als regulärer Ausdruck eines Größenpolynoms in dem der Operanden dargestellt werden kann. Wir beweisen, dass die Verwendung von Sprachquotienten, insbesondere der Präfix- und Suffix-Abschlüsse, einer regulären Menge höchstens zu einer quadratischen Vergrößerung der erforderlichen Ausdrucksgröße führen kann. Der Umlaufbetrieb kann nur eine kubische Vergrößerung bewirken und im schlimmsten Fall kann zumindest ein quadratisches Aufblähen notwendig sein.

Wie AS andeutet, kann es andere, natürlichere Möglichkeiten geben, etwas wie die gestellte Frage zu studieren. Hier ist ein anderer, etwas ähnlicher Weg, das Wachstum einer regulären Sprache basierend auf der Anzahl der Wörter der Größe zu studieren, der eine lose Beziehung zu der Frage hat, z$n$

• Ermittlung der Wachstumsrate einer regulären oder kontextfreien Sprache in polynomialer Zeit (Gawrychowski, Krieger, Rampersad, Shallit)

  Bei einer kontextfreien Sprache L können wir testen, ob es sich um ein polynomielles oder ein exponentielles Wachstum in der Polynomzeit handelt. Wenn es sich um ein Polynom handelt, können wir außerdem die genaue Reihenfolge dieses Polynoms in der Polynomzeit finden.