Kemajuan pada masalah ketinggian bintang umum?

Ketinggian bintang (yang digeneralisasikan) dari suatu bahasa adalah bersarang minimum dari bintang-bintang Kleene yang diperlukan untuk mewakili bahasa dengan suatu ekspresi reguler yang diperluas. Ingatlah bahwa ekspresi reguler yang diperluas menggunakan alfabet terbatas memenuhi yang berikut:$A$

(1) dan sebuah diperpanjang ekspresi reguler untuk semua a ∈ $\emptyset, 1$$a$$a\in A$

(2) Untuk semua persamaan reguler yang diperluas ; E ∪ F , E F , E ∗ dan E c adalah ekspresi reguler yang diperluas$E,F$
$E\cup F$$EF$$E^*$$E^c$

Salah satu ungkapan masalah ketinggian bintang umum adalah apakah ada algoritma untuk menghitung tinggi minimum bintang umum. Berkenaan dengan masalah ini saya punya beberapa pertanyaan.

1. Apakah ada kemajuan terbaru (atau minat penelitian) tentang masalah ini? Saya tahu beberapa tahun yang lalu bahwa Pin Straubing dan Thrien menerbitkan beberapa makalah di bidang ini.

2. Masalah ketinggian bintang terbatas diselesaikan pada tahun 1988 oleh Hashiguchi tetapi versi umum (sejauh yang saya tahu) masih terbuka. Adakah yang punya intuisi mengapa ini bisa terjadi?

Tautan yang mungkin bermanfaat adalah sebagai berikut: starheight

Mengenai pertanyaan kedua Anda, penjelasan mengapa masalah tinggi bintang umum kurang dapat diakses daripada masalah tinggi bintang adalah sebagai berikut: Sudah kertas mani Eggan pada tahun 1963 berisi bahasa tinggi bintang biasa ( , untuk setiap k ≥ 0 . Hanya beberapa tahun kemudian, McNaughton, dan, secara independen, Déjean dan Schützenberger, menemukan contoh di atas huruf biner. Ini memperjelas apa masalahnya "tentang". Selama tahun-tahun berikutnya, ada aliran hasil publikasi yang kurang lebih mantap di bidang masalah ketinggian bintang biasa. Ini memberi semakin banyak contoh yang diterbitkan, contoh tandingan dan fenomena seputar masalah ini.$k$$k\ge 0$

Sebaliknya, setelah sekitar lima puluh tahun sekarang, kita tidak tahu apakah ada bahasa reguler tinggi bintang setidaknya dua. Jadi kita bahkan tidak tahu apakah perlu ada prosedur keputusan. Ini "sama sekali tidak ada contoh" menunjukkan bahwa sangat sulit untuk memahami masalah ini.

Jawaban ini didedikasikan untuk mengenang Janusz (John) Antoni Brzozowski, yang meninggal pada 24 Oktober 2019.

John tentu adalah orang yang membuat masalah ketinggian bintang begitu terkenal. Memang, pada sebuah konferensi di Santa Barbara pada bulan Desember 1979, ia menyajikan enam pilihan masalah terbuka tentang bahasa reguler dan menyebutkan dua topik lain di akhir artikelnya [1]. Keenam masalah terbuka ini adalah, secara berurutan, tinggi bintang, tinggi bintang terbatas, kompleksitas kelompok, penghapusan bintang, keteraturan kelas yang tidak terhitung dan optimalitas kode awalan. Dua topik lainnya adalah masalah keterbatasan dan hierarki dot-depth.

Pada Juni 2015, selama a konferensi satu hari untuk menghormati ulang tahunnya yang ke-80 , saya mempresentasikan dua artikel survei yang merangkum keadaan seni pada pertanyaan-pertanyaan ini [2, 3]. Khususnya, Anda akan menemukan [2] informasi terperinci tentang masalah ketinggian bintang.

[1] JA Brzozowski, Buka masalah tentang bahasa biasa , dalam teori bahasa formal. Perspektif dan masalah terbuka, Prosiding simposium yang diadakan di Santa Barbara, California, 10-14 Desember 1979 [, RV Book (ed.), Hlm. 23–47, New York Etc .: Academic Press, Anak Perusahaan Harcourt Brace Jovanovich, Penerbit. XIII, 454 hal., 1980.

[2] J.-É. Sematkan, Buka masalah tentang bahasa biasa, 35 tahun kemudian , Stavros Konstantinidis; Nelma Moreira; Rogério Reis; Jeffrey Shallit. Peran Teori dalam Ilmu Komputer - Esai Didedikasikan untuk Janusz Brzozowski, World Scientific, 2017,

[3] J.-É. Pin, Hirarki titik-kedalaman, 45 tahun kemudian . Stavros Konstantinidis; Nelma Moreira; Rogério Reis; Jeffrey Shallit. Peran Teori dalam Ilmu Komputer - Esai Didedikasikan untuk Janusz Brzozowski, World Scientific, 2017.

Solusi dari masalah ketinggian bintang yang terbatas mengilhami teori kaya fungsi biaya reguler (oleh Colcombet), yang pada gilirannya membantu menyelesaikan masalah decidability lainnya dan menawarkan alat baru untuk menyerang masalah terbuka. Teori ini masih berkembang dan diperluas ke kata-kata tanpa batas, pohon terbatas, pohon tak terbatas, dengan serangkaian hasil mendalam dan masalah terbuka. Berikut ini adalah makalah seminal teori, dan bibliografi , dari situs web Colcombet.

Jadi, meskipun tidak secara langsung aplikasi ketinggian bintang yang digeneralisasikan, ini menunjukkan bahwa kemajuan pada masalah yang tampaknya tidak berguna seperti ketinggian bintang kemungkinan berarti pemahaman yang lebih baik tentang bahasa reguler, dan menghasilkan hasil baru pada masalah yang berbeda.

Referensi: Thomas Colcombet. "Teori stabilisasi monoids dan fungsi biaya reguler". Dalam: ICALP 2009