Postęp w ogólnym problemie z wysokością gwiazdy?

15

(Uogólniona) wysokość gwiazdy w języku jest minimalnym zagnieżdżeniem gwiazd Kleene wymaganym do przedstawienia języka za pomocą rozszerzonego wyrażenia regularnego. Przypomnijmy, że rozszerzonym wyrażeniem regularnym ponad skończonych alfabet spełnia następujące: $A$

(1) i są rozszerzone wyrażenia regularne dla wszystkich $\emptyset, 1$ $a$ $a\in A$

(2) Dla wszystkich rozszerzonych wyrażeń regularnych ; , , i są rozszerzonymi wyrażeniami regularnymi $E,F$
$E\cup F$ $EF$ $E^*$ $E^c$

Jednym z fraz uogólnionego problemu wysokości gwiazdy jest to, czy istnieje algorytm obliczający minimalną uogólnioną wysokość gwiazdy. W związku z tym problemem mam kilka pytań.

Czy nastąpił jakiś postęp (lub zainteresowanie badaniami) dotyczący tego problemu? Wiem wiele lat temu, że Pin Straubing i Thérien opublikowali kilka artykułów w tej dziedzinie.
Problem ograniczonej wysokości gwiazdy został rozwiązany w 1988 roku przez Hashiguchi, ale uogólniona wersja (o ile mi wiadomo) jest nadal otwarta. Czy ktoś ma jakąkolwiek intuicję, dlaczego tak się dzieje?

Link, który może być pomocny, to: wysokość gwiazdy

fl.formal-languages lower-bounds regular-expressions

— zmieszana matematyka
źródło

Pomocna byłaby jasna definicja „rozszerzonego wyrażenia regularnego” lub linku. Również linki do cytowanych dokumentów pomogłyby wyjaśnić pytanie

— Suresh Venkat,

2

\emptyset, 1, a

$\emptyset, 1, a$

a \in A

$a\in A$

2

AFAIK, Pin aktualizuje swoją stronę internetową ( liafa.jussieu.fr/~jep/Problemes/starheight.html ), co oznaczałoby brak postępu.

— Michaël Cadilhac

dzięki: jeszcze lepiej byłoby włączyć to do pytania.

— Suresh Venkat

1

W poprzednich komentarzach „liafa.jussieu.fr” należy zastąpić „www.liafa.univ-paris-diderot.fr”. Zredagowałem link w pytaniu, ale nie mogłem edytować linków w komentarzach.

— J.-E.

9

$k$ $k\ge 0$

Natomiast po około pięćdziesięciu latach nie wiemy, czy istnieje jakiś regularny język wysokości co najmniej dwóch gwiazd. Nie wiemy nawet, czy w końcu istnieje potrzeba procedury decyzyjnej. Ten „całkowity brak przykładów” wskazuje, że niezwykle trudno jest poradzić sobie z tym problemem.

— Hermann Gruber
źródło

Czy znasz jakieś aplikacje / obszary, na które odkrycie rzeczywistego algorytmu miałoby bezpośredni wpływ? (inne niż z czysto intelektualnego punktu widzenia)

— zmieszana

1

0

$0$

1

$1$

1

Ograniczona wysokość gwiazdy prawdopodobnie zostanie wkrótce zastosowana w pracach nad przybliżeniem kosztów komponentów w systemach komunikacyjnych. (jeszcze nie ma odwołania)

— Denis,

7

Ta odpowiedź jest poświęcona pamięci Janusza (Jana) Antoniego Brzozowskiego, który zmarł 24 października 2019 r.

John jest z pewnością osobą, która sprawiła, że problemy z wysokością gwiazdy stały się tak znane. Rzeczywiście, na konferencji w Santa Barbara w grudniu 1979 r. Przedstawił wybór sześciu otwartych problemów dotyczących zwykłych języków i wspomniał o dwóch innych tematach na zakończenie swojego artykułu [1]. Tymi sześcioma otwartymi problemami były kolejno: wysokość gwiazdy, ograniczona wysokość gwiazdy, złożoność grupy, usuwanie gwiazd, regularność niezliczonych klas i optymalizacja kodów prefiksów. Dwa pozostałe tematy to problem ograniczania i hierarchia kropek.

W czerwcu 2015 r., Podczas jednodniowej konferencji z okazji jego 80. urodzin , przedstawiłem dwa artykuły ankietowe podsumowujące aktualny stan wiedzy na te pytania [2, 3]. W szczególności znajdziesz [2] szczegółowe informacje na temat problemów z wysokością gwiazdy.

[1] JA Brzozowski, Otwarte problemy dotyczące języków regularnych w formalnej teorii języków. Perspektywy i otwarte problemy, Materiały z sympozjum, które odbyło się w Santa Barbara, Kalifornia, 10-14 grudnia 1979 r. [, RV Book (red.), S. 23–47, New York Etc .: Academic Press, filia Harcourt Brace Jovanovich, wydawcy. XIII, 454 s., 1980.

[2] J.-É. Przypnij, Otwarte problemy dotyczące zwykłych języków, 35 lat później , Stavros Konstantinidis; Nelma Moreira; Rogério Reis; Jeffrey Shallit. Rola teorii w informatyce - eseje dedykowane Januszowi Brzozowskiemu, World Scientific, 2017,

[3] J.-É. Pin, Hierarchia głębokości kropek, 45 lat później . Stavros Konstantinidis; Nelma Moreira; Rogério Reis; Jeffrey Shallit. Rola teorii w informatyce - eseje dedykowane Januszowi Brzozowskiemu, World Scientific, 2017.

— J.-E. Kołek
źródło

Dzięki za podzielenie się tym - właśnie dowiedziałem się z twojej odpowiedzi, że zmarł.

— Hermann Gruber,

2

Rozwiązanie problemu ograniczonej wysokości gwiazdy zainspirowało bogatą teorię funkcji kosztów regularnych (autorstwa Colcombet), która z kolei pomogła rozwiązać inne problemy rozstrzygalności i oferuje nowe narzędzia do atakowania otwartych problemów. Teoria ta wciąż się rozwija i została rozszerzona na nieskończone słowa, skończone drzewa, nieskończone drzewa, z własnym zestawem głębokich wyników i otwartych problemów. Oto przełomowy artykuł z teorii i bibliografia ze strony Colcombet.

Chociaż więc nie jest to bezpośrednio zastosowanie uogólnionej wysokości gwiazdy, pokazuje, że postępy w pozornie bezużytecznych problemach, takich jak wysokość gwiazdy, prawdopodobnie będą oznaczały lepsze zrozumienie zwykłych języków i przyniosą nowe wyniki dla różnych problemów.

Referencje: Thomas Colcombet. „Teoria monoidów stabilizacyjnych i funkcji kosztów regularnych”. W: ICALP 2009

— Denis
źródło