Zobecněný problém s výškou hvězdy - Generalized star-height problem
Lze všechny regulární jazyky vyjádřit pomocí zobecněných regulárních výrazů s omezenou hloubkou vnoření hvězd Kleene ?
Hvězda-height problém zobecnit do teorie formálních jazyků je otevřená otázka, zda všechny regulární jazyky mohou být vyjádřeny pomocí generalizované regulárních výrazů s omezenou hnízdění hloubky Kleeneho hvězd . Zde jsou zobecněné regulární výrazy definovány jako regulární výrazy , ale mají integrovaný operátor doplňku. U regulárního jazyka je jeho zobecněná výška hvězd definována jako minimální hloubka vnoření hvězd Kleene potřebná k popisu jazyka pomocí zobecněného regulárního výrazu, odtud název problému.
Konkrétněji jde o otevřenou otázku, zda je vyžadována hloubka vnoření větší než 1, a pokud ano, zda existuje algoritmus pro stanovení minimální požadované výšky hvězdy.
Pravidelné jazyky s výškou hvězdy 0 se také nazývají jazyky bez hvězd . Schützenbergerova věta poskytuje algebraickou charakterizaci jazyků bez hvězd pomocí neperiodických syntaktických monoidů . Zejména jazyky bez hvězd jsou vhodnou rozhodnutelnou podtřídou běžných jazyků.
Viz také
- Egganova věta a zobecněné části výšky hvězd v článku o výšce hvězd
- Problém s výškou hvězdy
Reference
- Janusz A. Brzozowski (1980). Msgstr "Otevřené problémy s běžnými jazyky". V knize Ronalda V. (ed.). Teorie formálního jazyka: Perspektivy a otevřené problémy . Akademický tisk. 23–47.
- Wolfgang Thomas (1981). „Poznámka k problému s výškou hvězdy“ . Teoretická informatika . 13 (2): 231–237. doi : 10.1016 / 0304-3975 (81) 90041-4 . MR 0594062 .
- Jean-Eric Pin; Howard Straubing; Denis Thérien (1992). „Některé výsledky zobecněného problému s výškou hvězd“ (PDF) . Informace a výpočet . 101 (2): 219–250. doi : 10.1016 / 0890-5401 (92) 90063-L .
- Sakarovitch, Jacques (2009). Základy teorie automatů . Z francouzštiny přeložil Reuben Thomas. Cambridge: Cambridge University Press . ISBN 978-0-521-84425-3. Zbl 1188,68177 .
- Marcel-Paul Schützenberger (1965). "Na konečných monoidech majících pouze triviální podskupiny" . Informace a kontrola . 8 (2): 190–194. doi : 10,1016 / S0019-9958 (65) 90108-7 . Zbl 0131.02001 .
externí odkazy
