Проблема - эквивалентность
Cтраница 3
Если над некоторой информационной областью 0 проблема эквивалентности для конечных детерминированных преобразователей неразрешима, то неразрешима и проблема проверки выполнимости свойства Черча-Россера. В самом деле, по двум детерминированным преобразователям Аг и Л2 легко построить недетерминированный преобразователь Л, который на первом шаге недетерминированно передает управление преобразователю Лх или Л2, а затем функционирует согласно правилам выбранного преобразователя. Преобразователь А - преобразователь Черча - Россера тогда и только тогда, когда Аг и А2 эквивалентны. Таким образом, для преобразователей над стандартной памятью или над целочисленной решеткой Z X Z проверка свойства Черча - Россера неразрешима, так как известно, что для детерминированных читающих преобразователей над этими структурами проблема эквивалентности неразрешима. [31]
В этом разделе доказывается алгоритмическая неразрешимость проблемы эквивалентности для конечных схем. Эта проблема неразрешима и для устойчивых и для последовательных конечных схем. Поскольку класс счетчиковых схем содержит класс конечных схем, то для счетчиковых схем проблема эквивалентности также неразрешима. Разрешимость проблемы эквивалентности доказана лишь для схем без логических разветвлений, которые содержатся в классе счетчиковых схем. Этот результат обсуждается в разд. [32]
Из теоремы 7.14 также нетрудно вывести разрешимость проблемы эквивалентности для линейных LA ( / - распознавателей. [33]
Для конечных детерминированных читающих преобразователей над свободными группами проблема эквивалентности по данным разрешима. [34]
В классе LL ( fe) - rpaMMaTHK разрешима проблема эквивалентности. [35]
Установив, что для некоторого подкласса класса рекурсивных схем проблема эквивалентности разрешима, мы покажем то же самое для класса стандартных схем с одной переменной и засылками констант. Проблема эквивалентности для стандартных схем с одной переменной без засылок констант разрешима, как было показано в разд. Следовательно, следующая теорема является оптимальной. [36]
При фиксированных сигнатурах Q и П и алфавите R проблема функциональной эквивалентности конечных X-Y - автоматов неразрешима тогда и только тогда, когда R содержит по крайней мере два символа переменных, Q - по крайней мере один функциональный символ арности больше нуля, П - по крайней мере один символ предиката арности больше нуля. [37]
С получением более тонкой классификации разрешимых случаев интересно рассмотреть проблему функциональной эквивалентности для случая, когда элементарные условия таковы, что множество L допустимых функций выходов совпадает с множеством всех функций выходов. Это возможно, например, когда каждое из условий зависит от всех переменных. [38]
Следствие 7.7. Проблема эквивалентности для унарных рекурсивных схем равносильна проблеме эквивалентности для LA ( 1) - распозна-вателей. [39]
Метод сведения проблемы парасочетаний над алфавитом 61 62 к проблеме эквивалентности схем мы проиллюстрируем на примерах, поскольку формальное доказательство легко восстанавливается. [40]
Теорема 7.14. Для LA ( / - распознавателей ограниченного диаметра проблема эквивалентности разрешима. [41]
Однако и в языкеСи, и в языке Паскаль игнорируется проблема эквивалентности типов. [42]
 |
Схема Патерсона всегда останавливается. [43] |
Ясно, что проблемы остановки и расходимости - частный случай проблемы эквивалентности. [44]
Следствие 7.4. В классе линейных LA ( / - распознавателей разрешима проблема эквивалентности. [45]
Страницы: 1 2 3 4