Gibt es eine härteste DCFL?

Bekanntermaßen definierte Greibach eine Sprache , die sogenannte nichtdeterministische Version von , so dass jede CFL ein inverses morphes Bild von $H$ $D_2$ $H$ . Gibt es eine ähnliche Aussage zu DCFL, möglicherweise mit einer gewissen Einschränkung der zulässigen Morphismen?

(Siehe z. B. M. Autebert, J. Berstel und L. Boasson. Kontextfreie Sprachen und Pushdown-Automaten. In R. Rozenberg und A. Salomaa, Herausgeber, Handbuch der formalen Sprachen, Band I, Kapitel 3. Springer Verlag 1997.)

fl.formal-languages open-problem context-free nondeterminism hard-instances Michaël Cadilhac
quelle

Antworten:

Eine identische Homomorphismus-Charakterisierung von DCFL scheint nicht möglich zu sein. Im Folgenden wird aus Greibach ursprünglichen extrahiert Papier .

Wir zeigen, dass jede kontextfreie Sprache für einen Homomorphismus als oder ausgedrückt werden kann . Die algebraische Aussage lautet: Die Familie der kontextfreien Sprachen ist eine Haupt-AFDL; ... Im Gegensatz dazu ist die Familie der deterministischen kontextfreien Sprachen keine Haupt-AFDL [7]. $h^{-1}(L_0)$ $h^{-1}(L_0-\{e\})$ $h$

Das Papier 7 ist die Konferenzversion des Papiers. In der Konferenzversion besagt Satz 4.2, dass "die Familie der deterministischen kontextfreien Sprachen keine Haupt-AFDL ist".

Möglicherweise ist jedoch noch eine analoge Charakterisierung möglich. Okhotin lieferte homomorphe Charakterisierungen von konjunktiven und booleschen Grammatiken. Für DCFLs scheint das Problem offen zu sein. Das Folgende ist das Fazit von Okhotins Artikel (von 2013).

Jede unter inversen Homomorphismen geschlossene Sprachfamilie kann möglicherweise ein Analogon zu Greibachs inverser homomorpher Charakterisierung aufweisen. Die Frage ist, welche Familien haben es? Könnte es für lineare, deterministische oder eindeutige Varianten gewöhnlicher (kontextfreier) Grammatiken existieren? Könnte es eine solche Charakterisierung für lineare Konjunktivgrammatiken, eindeutige Konjunktivgrammatiken usw. geben?

Mateus de Oliveira Oliveira
quelle

Vielen Dank! Ich weiß jedoch, dass die DCFL keine Principal sind. Deshalb lasse ich die Morphismen bei Bedarf einschränken - ich kann meine Frage genauer formulieren als: Was ist die kleinste Klasse von Funktionen F, für die es eine Sprache H gibt, in der F (H) die Menge aller DCFL ist - zusätzliche Verschlüsse geben oder nehmen.

Michaël Cadilhac

In Ordnung. Ich habe meine Antwort bearbeitet. Es scheint, dass dies für DCFL ein offenes Problem ist.

Mateus de Oliveira Oliveira

Komischerweise kenne ich Okhotins Artikel sehr gut, habe aber nicht bemerkt, dass er sich ausdrücklich auf das Problem bezog! Nun, ich bin mir nicht sicher, was ich hier tun soll. Sicher, es ist eine gültige Antwort für den Moment , aber sollte sie offen bleiben, bis sie gelöst ist?

Michaël Cadilhac

Ich weiß nicht, wie die Polizei der Website nach Lösungen für offene Probleme fragt. Wenn mich jemand darauf hinweist, dass ein Problem, an dem ich interessiert bin, für viele Jahre offen ist, dann würde ich die Antwort akzeptieren. Meiner Meinung nach ist es in diesem Fall sinnvoller, die Frage als Referenzanfrage zu betrachten. Diesbezüglich kann es jedoch unterschiedliche Standpunkte geben. Ich denke, diese Diskussion in meta.cstheory könnte hilfreich sein meta.cstheory.stackexchange.com/questions/1058/…

Mateus de Oliveira Oliveira

Natürlich macht es mir nichts aus, wenn Sie die Antwort akzeptieren. In der Tat ist es eine sehr interessante Antwort. Obwohl die Art der Antwort zum Titel passt, unterscheidet sie sich stark von der eigentlichen Frage, da die Reduzierung des logarithmischen Speicherplatzes viel stärker ist als die von Homomorphismen.

Mateus de Oliveira Oliveira

Es tatsächlich ist ein härteste DCFL-, die eine deterministische Version von Greibach der ist; Es wurde von Sudborough im Jahr 78 in Über deterministische kontextfreie Sprachen, Mehrkopfautomaten und die Leistung eines zusätzlichen Pushdown-Speichers eingeführt . Die darin erwähnte Sprache ist die Menge von Wörtern über wobei: $L_0^{(2)}$ $\{a, \bar{a}, b, \bar{b}, \#, [, ]\}$

γ_{0} [\bar{a} γ_{a}^{(1)} # \bar{b} γ_{b}^{(1)}] \dots [\bar{a} γ_{a}^{(k)} # \bar{b} γ_{b}^{(k)}],

$\gamma_0\;[\bar{a}\gamma_a^{(1)}\#\bar{b}\gamma_b^{(1)}]\;\cdots\; [\bar{a}\gamma_a^{(k)}\#\bar{b}\gamma_b^{(k)}]\enspace,$

with $\gamma_0, \gamma_a^{(i)}, \gamma_b^{(i)}$ words over $\{a, \bar{a}, b, \bar{b}\}$ , such that there exists a word $w_1w_2\cdots w_k \in \{a, b\}^k$ with $\gamma_0 \; \bar{w_1}\gamma_{w_1}^{(1)} \cdots \bar{w_k}\gamma_{w_k}^{(k)}$ a Dyck word.

It then holds that $L_0^{(2)}$ is a DCFL and any DCFL log-space-reduces to $L_0^{(2)}$ . In that sense, $L_0^{(2)}$ is the hardest tape DCFL.

As mentioned by contributor Mateus de Oliveira Oliveira, DCFL is not a principal AFL, and it is unknown whether there exists an exact characterization involving the closure of a single language under some operations.

Michaël Cadilhac
quelle

The paper

J.-M. Autebert, Une note sur le cylindre des langages déterministes, Theoretical Computer Science 8 (1979), 395-399

gives a short proof of the following result (credited to Greibach) which seems to answer your question:

there is no deterministic context-free language $L$ such that, for every deterministic context-free language $C$ , there is an homomorphism $h$ and a regular language $R$ such that $C = h^{-1}(L)\cap R$ .

J.-E. Pin
quelle