Жұлдыз биіктігі проблемасы - Википедия - Star height problem

The жұлдыз биіктігі проблемасы жылы ресми тіл теориясы барлығы ма деген сұрақ қойылады қарапайым тілдер пайдаланып білдіруге болады тұрақты тіркестер шектеулі жұлдыз биіктігі, яғни ұясының тереңдігі шектеулі Kleene жұлдыздары. Нақтырақ айтқанда, ұя салу тереңдігі әрқашан жеткілікті ме? Егер жоқ болса, онда бар ма алгоритм қанша қажет екенін анықтау үшін? Мәселе көтерілді Эгган (1963).

Жұлдыз биіктігі тұрақты кәдімгі тілдердің отбасылары

Бірінші сұраққа теріс жауап берілді, 1963 жылы Эгган тұрақты тілдердің мысалдарын келтірді жұлдыз биіктігі n әрқайсысы үшін n. Мұнда жұлдыз биіктігі сағ(L) қарапайым тіл L барлық тұрақты өрнектер арасындағы жұлдыздардың минималды биіктігі ретінде анықталады L. Табылған алғашқы бірнеше тіл Эгган (1963) әр тіл үшін тұрақты сөйлем беру арқылы келесіде сипатталады:

Бұл өрнектерді құру принципі - осы өрнек екі данасын біріктіру арқылы алынады , жаңа алфавиттік белгілерді қолдана отырып, екінші дананың әріптерін тиісті түрде өзгерту, нәтижені басқа жаңа алфавиттік белгімен байланыстыру, содан кейін алынған өрнекті Клейн жұлдызымен қоршау. Қалған, одан да қиын бөлігі - мұны дәлелдеу жұлдыз биіктігінен кем баламалы тұрақты өрнек жоқ n; дәлелі келтірілген (Eggan 1963 ).

Алайда, Эгганның мысалдары үлкенді қолданады алфавит, өлшемі 2n-1 жұлдызша биіктігі бар тіл үшін n. Сонымен, ол екілік алфавиттерден мысалдар таба аламыз ба деп сұрады. Көп ұзамай бұл шындыққа айналды Дежан және Шютценбергер (1966). Олардың мысалдарын индуктивті түрде анықталған екілік алфавит үстіндегі тұрақты тіркестер отбасы келесідей - cf. Саломаа (1981):

Бұған тағы да дәлелдеу керек төменгі жұлдыз биіктігінің эквивалентті тұрақты өрнегін қабылдамайды. Дәлелдер келтірілген (Дежан және Шютценбергер 1966 ж ) және (Саломаа 1981 ж ).

Кәдімгі тілдердің жұлдыздық биіктігін есептеу

Керісінше, екінші сұрақ әлдеқайда күрделі болып шықты және бұл сұрақ ресми тіл теориясында жиырма жыл бойына танымал ашық мәселеге айналды (Бжозовский 1980 ж ). Бірнеше жыл бойы аз ғана прогресс болды. The таза топтық тілдер жұлдыздардың биіктігі проблемасы дәлелденген қарапайым тілдердің алғашқы қызықты отбасы болды шешімді (McNaughton 1967 ). Бірақ жалпы проблема шешілгенге дейін 25 жылдан астам уақыт бойы ашық болды Хашигучи, кім 1988 жылы алгоритмін жариялады жұлдыз биіктігі кез-келген тұрақты тіл. Алгоритм мүлдем практикалық болған жоқ, өйткенібастауыш күрделілік. Ломбардия мен Сакарович (2002) осы алгоритмнің ресурстарды тұтынуын көрсету үшін бірнеше нақты сандарды келтіреді:

[Хашигучи сипаттаған рәсім] тіпті өте кішкентай мысалдар үшін мүмкін емес есептеулерге әкеледі. Мысалы, егер L цикл күрделілігінің 3 күйлі автоматы 3 арқылы қабылданады (және кішігірім 10 элементтің ауысу моноидымен), содан кейін а өте төмен кәмелетке толмаған тексерілетін тілдер санының L теңдік үшін:

— Ломбардия және Дж. Сакарович, қайтымды тілдердің жұлдыздық биіктігі және әмбебап автоматтар, ЛАТИН 2002

Бір ғана нөмірге назар аударыңыз жазылғанда 10 миллиард нөлге ие ондық санау, және қазірдің өзінде алыс қарағанда үлкен бақыланатын әлемдегі атомдар саны.

Хашигучидің процедурасына қарағанда әлдеқайда тиімді алгоритмді Кирстен 2005 жылы ойлап тапқан. Бұл алгоритм белгілі бір мерзімге сәйкес келеді шектелмеген автоматты кіріс ретінде, екі еселік шегіндеэкспоненциалды кеңістік. Бұл алгоритмнің ресурстарға деген қажеттілігі іс жүзінде мүмкін деп саналатын деңгейден айтарлықтай асып түседі.

Бұл алгоритмді 2008 жылы Колкомбет пен Лёдинг ағаштарға оңтайландырған және жалпылаған (Colcombet & Löding 2008 ж ), тұрақты шығындар функциялары теориясының бөлігі ретінде. Ол 2017 жылы Stamina инструментальды жиынтығында іске асырылды.[1]

Сондай-ақ қараңыз

Әдебиеттер тізімі

  1. ^ Натанаэль Фийалков, Уго Гимберт, Эдон Келменди, Денис Куперберг: «Төзімділік: Автоматтық теориядағы тұрақтылық моноидтары «. CIAA 2017: 101-112 құралы мекен-жайы бойынша қол жетімді https://github.com/nathanael-fijalkow/stamina/

Келтірілген жұмыстар

Әрі қарай оқу