Существует ли самый сложный DCFL?

Greibach лихо определил язык , так называемую недетерминированную версию о , таких , что любая КЛЛ является обратной морфической изображение . Существует ли подобное утверждение с DCFL, возможно, с некоторыми ограничениями на допустимые морфизмы? $H$ $D_2$ $H$

(См., Например, М. Аутеберт, Дж. Берстель и Л. Боассон. Неконтекстные языки и автоматы выталкивания. В R. Rozenberg и A. Salomaa, редакторы, Handbook of Formal Languages, том I, глава 3. Springer Verlag , 1997.)

fl.formal-languages open-problem context-free nondeterminism hard-instances Михаэль Кадилхак
источник

Ответы:

Идентичная характеристика гомоморфизма DCFL не представляется возможной. Следующее извлечено из оригинальной статьи Грайбаха .

Мы показываем, что любой контекстный язык может быть выражен как или для гомоморфизма . Алгебраическое утверждение таково: семейство контекстно-свободных языков является основным AFDL; ... В отличие от этого, семейство детерминированных контекстно-свободных языков не является основным AFDL [7]. $h^{-1}(L_0)$ $h^{-1}(L_0-\{e\})$ $h$

Документ 7 является версия конференции бумаги. В версии конференции теорема 4.2 гласит, что «семейство детерминированных контекстно-свободных языков не является главной АФДЛ».

Однако некоторые аналоговые характеристики все еще могут быть возможны. Охотин предоставил гомоморфные характеристики конъюнктивной и булевой грамматик. Для DCFL проблема кажется открытой. Ниже приводится заключение статьи Охотина (из 2013).

Любое семейство языков, замкнутых относительно обратных гомоморфизмов, потенциально может иметь аналог обратной гомоморфной характеристики Грейбаха. Вопрос в том, какие семьи есть? Может ли оно существовать для линейных, детерминированных или однозначных вариантов обычных (не зависящих от контекста) грамматик? Может ли быть такая характеристика для линейных конъюнктивных грамматик, однозначных конъюнктивных грамматик и т. Д.?

Матеус де Оливейра Оливейра
источник

Благодарность! Тем не менее, я знаю, что DCFL не являются основными; Вот почему я позволяю при необходимости ограничивать морфизмы - я могу более точно сформулировать свой вопрос следующим образом: каков наименьший класс функций F, для которого существует язык H, где F (H) - множество всех DCFL - дать или принять некоторые дополнительные закрытия

Микаэль Кадилхак

Ok. Я отредактировал свой ответ. Похоже, что для DCFL это открытая проблема.

Матеус де Оливейра Оливейра

Как ни странно, я очень хорошо знаю статью Охотина, но не заметил, что он явно имел в виду проблему! Ну, тогда я не уверен, что делать здесь; Конечно, это действительный ответ на данный момент , но она должна быть оставлена открытой , пока не решены?

Микаэль Кадилхак

Я не знаю, что полиция сайта спрашивает о решениях трудных открытых проблем. Лично, если бы кто-то указал мне, что интересующая меня проблема открыта в течение многих лет, я бы принял ответ. Мое мнение таково, что в этом случае более уместно рассматривать вопрос в качестве справочного запроса. Но могут быть разные точки зрения в отношении этого. Я думаю, что это обсуждение в meta.cstheory может быть полезным meta.cstheory.stackexchange.com/questions/1058/…

Матеус де Оливейра Оливейра

Конечно, я не против, чтобы вы приняли ваш ответ. Действительно, это очень интересный ответ. Однако, хотя вид ответа соответствует названию, он очень отличается от самого вопроса, поскольку сокращения пространства журналов намного более эффективны, чем гомоморфизмы.

Матеус де Оливейра Оливейра

Там на самом деле является труднее DCFL, которая является детерминированной версией Greibach - х; он был представлен Садборо в 78 году в статье « О детерминированных контекстно-свободных языках, многоголовочных автоматах и мощностях вспомогательного хранилища пуш- апов» - однако это самое сложное сокращение пространства журналов. Упомянутый там язык - это набор слов над где: $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,$

с словами над , такими, что существует слово с слово. $\gamma_0, \gamma_a^{(i)}, \gamma_b^{(i)}$ $\{a, \bar{a}, b, \bar{b}\}$ $w_1w_2\cdots w_k \in \{a, b\}^k$ $\gamma_0 \; \bar{w_1}\gamma_{w_1}^{(1)} \cdots \bar{w_k}\gamma_{w_k}^{(k)}$

Затем утверждается, что является DCFL, а любое пространство журнала DCFL сокращается до . В этом смысле - самая сложная лента DCFL. $L_0^{(2)}$ $L_0^{(2)}$ $L_0^{(2)}$

Как упомянул участник Mateus de Oliveira Oliveira, DCFL не является основным AFL, и неизвестно , существует ли точная характеристика, включающая закрытие одного языка при некоторых операциях.

Михаэль Кадилхак
источник

Бумага

Ж.-М. Autebert, Une note sur le le цилиндрических детерминистов, Теоретическая информатика 8 (1979), 395-399

дает краткое доказательство следующего результата (приписано Грайбаху), который, кажется, отвечает на ваш вопрос:

нет детерминированного контекстно-свободного языка такое , что для каждого детерминированного контекстно-свободного языка , существует гомоморфизм и регулярный язык такое , что . $L$ $C$ $h$ $R$ $C = h^{-1}(L)\cap R$

J.-E. Штырь
источник