О логических и топологических классификациях регулярных языков на бесконечных ординальных словах
|
1 Введение 3
2 Предварительные сведения об (ш + а)-автоматах 5
3 Тонкая иерархия 5
4 Логические классификации регулярных (ш + а)-языков 7
5 Топологические классификации регулярных (ш + а)-языков 18
6 Связь между классификациями 21
7 Заключение 23
2 Предварительные сведения об (ш + а)-автоматах 5
3 Тонкая иерархия 5
4 Логические классификации регулярных (ш + а)-языков 7
5 Топологические классификации регулярных (ш + а)-языков 18
6 Связь между классификациями 21
7 Заключение 23
Теория автоматов на бесконечных словах - хорошо развитый раздел теоретической информатики. Он имеет фундаментальное значение для анализа бесконечного поведения систем с конечным числом состояний. С этой теорией и ее приложениями можно ознакомиться в [6, 10, 20, 21, 22]. При изучении автоматов на бесконечных словах исследователи использовали различные методы, в том числе логические и топологические.
Бюхи, Элгот, и независимо, Трахтенброт являются основателями логического подхода к теории автоматов. Они доказали, что регулярные ш-языки совпадают с множествами ш-слов, удовлетворяющих предложениям монадической логики второго порядка. Позднее, Бюхи обобщил свое определение автоматов на слова трансфинитной длины. В этих автоматах существуют переходы двух типов: предельные и непредельные. Непредельные переходы выполняются, как и в обычных детерминированных автоматах, согласно заданному отношению перехода. Предельные переходы зависят только от состояний, посещенных ра¬нее в непредельных позициях. Используя эти автоматы, Бюхи доказал обобщение выше указанного результата для всех счетных ординалов. Чойка [4] предложил свое определение автоматов на ординальных словах. Они работают на словах длины, меньшей шп+1 для некоторого наперед заданного n Е ш. Главное отличие этого определения от определения Бюхи заключается в предельных переходах в автомате.
Имеет место и аналогичная связь логики первого порядка с апериодическими регулярными ш-языками, основанная на соответствующем результате Макнотона и Пейперта для конечных слов. Эта связь приводит к интересным логическим классификациям апериодических регулярных ш-языков, аналогичным иерархиям конечных слов Страубинга-Терьена и Бжозовского-Коэна. Иерархии, индуцированные иерархиями предложений по числу перемен кванторов, хорошо изучены в литературе. Многое также известно о разностных иерархиях, однако, существуют многие другие интересные иерархии, которые ранее не изучались систематически. В разделе 4 мы приведем дополнительные сведения и новые свойства этих иерархий. Большой вклад в развитие логического подхода для шп-языков внесли статьи Бедона [2], [1].
Также хорошо развит и топологический подход к изучению автоматов на бесконечных словах. Он основан на том факте, что множество бесконечых слов над некоторым фиксированным алфавитом можно снабдить канторовской топологией. Это позволяет классифицировать регулярные ш-языки, исходя из их сложности относительно топологических иерархий, известных из дескриптивной теории множеств [5]. Борелевская иерархия и разностные иерархиии Хаусдорфа-Куратовского хорошо изучены в этом контексте. Все эти иерархии включаются в более тонкую иерархию Вэджа [23]. В теории автоматов рассматривались некоторые сужения этих иерархий на класс регулярных ш-языков. Серия работ завершилась получением наиболее тонкой топологической классификации регулярных ш- языков, известной как иерархия Вагнера [24]. Она была открыта независимо от иерархии Вэджа. В разделе 5 мы приведем дополнительные сведения о топологических иерархиях.
Мы рассматриваем множество всех a-слов над конечным алфавитом X как топологическое пространство, являющееся произведением а копий дискретного топологического пространства на X . Борелевские подмножества этого пространства можно распределить по ш1уровням иерархии Бореля {Х° }eewi. Из работы Ландвебера [7] хорошо известно, что множество ш-регулярных языков REG(w)содержится в BC(S°), т.е любой ш-регулярный язык представим в виде конечной булевой комбинации языков второго уровня борелевской иерархии. Также существует иерархия ш-регулярных языков типа шш, введенная Вагнером в [24]. В ее основе лежат инварианты автоматов Мюллера: графы переходов автоматов, распознающих один и тот же ш-язык, в некотором смысле похожи, и по определенным свойствам графа переходов некоторого автомата можно установить топологическую сложность распознаваемого им языка. Возникает естественный вопрос: могут ли автоматы на а-словах (где ш < а < шш), распознавать более сложные в смысле уровней борелевской иерархии языки?
Одним из основных результатов данной работы является теорема 1 из раздела 5, уста-навливающая положительный ответ на этот вопрос. В частности, показано, что для любого n G ш верно включение REG(oin)С Х[°гаи существуют соответствующие ш”-регулярные языки, полные в уровнях Х°гаи S^n_ 1. Таким образом, а-регулярные языки (а <шш) реализуют все конечные уровни иерархии Бореля.
Тесная связь между логическими и топологическими иерархиями в значительной степени основывается на так называемой тонкой иерархии, разработанной В. Л. Селивановым в теории вычислимости [13] с целью идентификации «естественных m-степеней». В [12] (см. также [11, 14]) тонкая иерархия была описана в терминах теоретико-множественных операций, что позволяет применять ее в различных контекстах, в том числе в логическом и топологическом. Так как тонкая иерархия является главным техническим инструментом данной работы, в разделе 3 мы приведем ее определение и необходимые свойства, а также установим новое свойство, которое потребуется нам для доказательства главного результата. Тонкие иерархии имеют длину х0и могут определяться над последовательностями подрешеток, которые мы будем называть базами. Мы будем рассматривать тонкую иерархию Saнад борелевской базой {S^+1 }гау0, тонкую иерархию Saнад базой {5^+1 }п^0, индуцированной иерархией по числу перемен кванторов предложений логики первого порядка, а также иерархию Ra= SaПК, где R = ии<„<„. REG(d).
В этой работе продолжается систематическое исследование точных отношений между логическими и топологическими классификациями регулярных языков на словах, индек-сированных счетными ординалами. Мы установим строгую синтаксическую связь между уровнями иерархий: для любого а< £0уровень логической иерархии Saсодержится в соответствующем уровне связанной топологической иерархии Sa. И наоборот, для любо¬го уровня иерархии Вагнера мы предъявим предложение логики первого порядка такое, что соответствующий а-язык лежит в точности в этом уровне. Случай а = ш подроб¬но рассматривался в работе [9]. Структура предложения близко повторяет теоретико-множественную операцию, описывающую этот уровень как класс Вэджа. Неформально, логические иерархии в некотором смысле «покрывают» топологические.
Вторым основным результатом работы является теорема 2 из раздела 6: доказано, что sa СRa и SaС R„. Также из этой теоремы следует, что логическая иерархия Saне схлопывается, т.е для любого уровня а существует язык L G SaS^, где в< а. Результаты такого рода обычно получают используя метод игр Эренфойхта-Фрессе. Его использова¬ние для доказательства таких результатов зачастую связано с серьезными техническими трудностями (в чем они заключаются, описано в разделе 6). С помощью этих игр строятся предложения логики первого порядка с заданными свойствами. В данной работе мы используем для достижения вышеописанной цели метод игр Вэджа [23]. Он используется для доказательства сводимости языков непрерывными функциями. Оказывается, что применение игр Вэджа в этом случае оправдано, и приводит к нужному результату. Также, не схлопывается и топологическая иерархия Raпри а< £0.
В разделах 4 и 5 мы приведем некоторые особые свойства тонких иерархий в логическом и топологическом контекстах. После этого, мы обсудим соотношение между ними в разделе 6, и упомянем оставшиеся открытыми вопросы. Как будет показано, установленные соотношения можно использовать для доказательства некоторых свойств логических тонких иерархий (в частности, их несхлопываемости), не содержащих в своей формулировке никаких упоминаний о топологии. Некоторые определения и доказательства, касающиеся тонких иерархий, технически довольно сложные. Главной причиной этому являются особые свойства соответствующих иерархий по числу перемен кванторов, в частности тот факт, что все уровни таких иерархий не обладают свойством редукции [18], в отличие от конечной иерархии Бореля.
Бюхи, Элгот, и независимо, Трахтенброт являются основателями логического подхода к теории автоматов. Они доказали, что регулярные ш-языки совпадают с множествами ш-слов, удовлетворяющих предложениям монадической логики второго порядка. Позднее, Бюхи обобщил свое определение автоматов на слова трансфинитной длины. В этих автоматах существуют переходы двух типов: предельные и непредельные. Непредельные переходы выполняются, как и в обычных детерминированных автоматах, согласно заданному отношению перехода. Предельные переходы зависят только от состояний, посещенных ра¬нее в непредельных позициях. Используя эти автоматы, Бюхи доказал обобщение выше указанного результата для всех счетных ординалов. Чойка [4] предложил свое определение автоматов на ординальных словах. Они работают на словах длины, меньшей шп+1 для некоторого наперед заданного n Е ш. Главное отличие этого определения от определения Бюхи заключается в предельных переходах в автомате.
Имеет место и аналогичная связь логики первого порядка с апериодическими регулярными ш-языками, основанная на соответствующем результате Макнотона и Пейперта для конечных слов. Эта связь приводит к интересным логическим классификациям апериодических регулярных ш-языков, аналогичным иерархиям конечных слов Страубинга-Терьена и Бжозовского-Коэна. Иерархии, индуцированные иерархиями предложений по числу перемен кванторов, хорошо изучены в литературе. Многое также известно о разностных иерархиях, однако, существуют многие другие интересные иерархии, которые ранее не изучались систематически. В разделе 4 мы приведем дополнительные сведения и новые свойства этих иерархий. Большой вклад в развитие логического подхода для шп-языков внесли статьи Бедона [2], [1].
Также хорошо развит и топологический подход к изучению автоматов на бесконечных словах. Он основан на том факте, что множество бесконечых слов над некоторым фиксированным алфавитом можно снабдить канторовской топологией. Это позволяет классифицировать регулярные ш-языки, исходя из их сложности относительно топологических иерархий, известных из дескриптивной теории множеств [5]. Борелевская иерархия и разностные иерархиии Хаусдорфа-Куратовского хорошо изучены в этом контексте. Все эти иерархии включаются в более тонкую иерархию Вэджа [23]. В теории автоматов рассматривались некоторые сужения этих иерархий на класс регулярных ш-языков. Серия работ завершилась получением наиболее тонкой топологической классификации регулярных ш- языков, известной как иерархия Вагнера [24]. Она была открыта независимо от иерархии Вэджа. В разделе 5 мы приведем дополнительные сведения о топологических иерархиях.
Мы рассматриваем множество всех a-слов над конечным алфавитом X как топологическое пространство, являющееся произведением а копий дискретного топологического пространства на X . Борелевские подмножества этого пространства можно распределить по ш1уровням иерархии Бореля {Х° }eewi. Из работы Ландвебера [7] хорошо известно, что множество ш-регулярных языков REG(w)содержится в BC(S°), т.е любой ш-регулярный язык представим в виде конечной булевой комбинации языков второго уровня борелевской иерархии. Также существует иерархия ш-регулярных языков типа шш, введенная Вагнером в [24]. В ее основе лежат инварианты автоматов Мюллера: графы переходов автоматов, распознающих один и тот же ш-язык, в некотором смысле похожи, и по определенным свойствам графа переходов некоторого автомата можно установить топологическую сложность распознаваемого им языка. Возникает естественный вопрос: могут ли автоматы на а-словах (где ш < а < шш), распознавать более сложные в смысле уровней борелевской иерархии языки?
Одним из основных результатов данной работы является теорема 1 из раздела 5, уста-навливающая положительный ответ на этот вопрос. В частности, показано, что для любого n G ш верно включение REG(oin)С Х[°гаи существуют соответствующие ш”-регулярные языки, полные в уровнях Х°гаи S^n_ 1. Таким образом, а-регулярные языки (а <шш) реализуют все конечные уровни иерархии Бореля.
Тесная связь между логическими и топологическими иерархиями в значительной степени основывается на так называемой тонкой иерархии, разработанной В. Л. Селивановым в теории вычислимости [13] с целью идентификации «естественных m-степеней». В [12] (см. также [11, 14]) тонкая иерархия была описана в терминах теоретико-множественных операций, что позволяет применять ее в различных контекстах, в том числе в логическом и топологическом. Так как тонкая иерархия является главным техническим инструментом данной работы, в разделе 3 мы приведем ее определение и необходимые свойства, а также установим новое свойство, которое потребуется нам для доказательства главного результата. Тонкие иерархии имеют длину х0и могут определяться над последовательностями подрешеток, которые мы будем называть базами. Мы будем рассматривать тонкую иерархию Saнад борелевской базой {S^+1 }гау0, тонкую иерархию Saнад базой {5^+1 }п^0, индуцированной иерархией по числу перемен кванторов предложений логики первого порядка, а также иерархию Ra= SaПК, где R = ии<„<„. REG(d).
В этой работе продолжается систематическое исследование точных отношений между логическими и топологическими классификациями регулярных языков на словах, индек-сированных счетными ординалами. Мы установим строгую синтаксическую связь между уровнями иерархий: для любого а< £0уровень логической иерархии Saсодержится в соответствующем уровне связанной топологической иерархии Sa. И наоборот, для любо¬го уровня иерархии Вагнера мы предъявим предложение логики первого порядка такое, что соответствующий а-язык лежит в точности в этом уровне. Случай а = ш подроб¬но рассматривался в работе [9]. Структура предложения близко повторяет теоретико-множественную операцию, описывающую этот уровень как класс Вэджа. Неформально, логические иерархии в некотором смысле «покрывают» топологические.
Вторым основным результатом работы является теорема 2 из раздела 6: доказано, что sa СRa и SaС R„. Также из этой теоремы следует, что логическая иерархия Saне схлопывается, т.е для любого уровня а существует язык L G SaS^, где в< а. Результаты такого рода обычно получают используя метод игр Эренфойхта-Фрессе. Его использова¬ние для доказательства таких результатов зачастую связано с серьезными техническими трудностями (в чем они заключаются, описано в разделе 6). С помощью этих игр строятся предложения логики первого порядка с заданными свойствами. В данной работе мы используем для достижения вышеописанной цели метод игр Вэджа [23]. Он используется для доказательства сводимости языков непрерывными функциями. Оказывается, что применение игр Вэджа в этом случае оправдано, и приводит к нужному результату. Также, не схлопывается и топологическая иерархия Raпри а< £0.
В разделах 4 и 5 мы приведем некоторые особые свойства тонких иерархий в логическом и топологическом контекстах. После этого, мы обсудим соотношение между ними в разделе 6, и упомянем оставшиеся открытыми вопросы. Как будет показано, установленные соотношения можно использовать для доказательства некоторых свойств логических тонких иерархий (в частности, их несхлопываемости), не содержащих в своей формулировке никаких упоминаний о топологии. Некоторые определения и доказательства, касающиеся тонких иерархий, технически довольно сложные. Главной причиной этому являются особые свойства соответствующих иерархий по числу перемен кванторов, в частности тот факт, что все уровни таких иерархий не обладают свойством редукции [18], в отличие от конечной иерархии Бореля.
Понятие конечного автомата на конечных словах многими авторами обобщалось на случай ш-слов. Зачастую эти обобщения эквивалентны. Наиболее интересным из них в связи с дескриптивной теорией множеств являются автоматы Мюллера, распознающие ш-регулярные языки. Важным подмножеством ш-регулярных языков являются апериодические ш-языки, т.е ш-языки, аксиоматизируемые предложениями логики первого порядка определенных сигнатур.
Важной классификацией ш-регулярных языков является иерархия Вагнера [24]. Она является важным начальным сегментом длины шш топологической тонкой иерархии типа £о. Важной классификацией ш-апериодических языков является логическая тонкая иерархия. В работе [9] мы установили точное соотношение между уровнями этих иерархий.
Для ш-регулярных языков известно ([7]) соотношение REG(w')С BC(S0J). Следуя Чойке [4], мы рассматриваем обобщение автоматов Мюллера на слова длины а, где а < шш. В данной работе показано, что для любого уровня конечной борелевской иерархии существует полный в нем язык, распознаваемый автоматом Чойки (теорема 1). Из этого следует, что топологическая иерархия языков слов длины, большей ш и меньшей шш, намного сложнее иерархии Вагнера. Также мы устанавливаем точное соотношение между уровнями логической и топологической иерархий языков, распознаваемых автоматами Чойки (теорема 2).
Однако, остаются открытыми некоторые важные вопросы, касающиеся регулярных языков на ординальных словах и требующие, по всей видимости, разработки соответствующей техники и применения новых подходов. В частности, остается неясным существование степеней Вэджа, отличных от Ra Ra, Ra Ra, (Ra+i 0 Ra+1) (Ra U Ra) и статус равенства R, = Ra.
Важной классификацией ш-регулярных языков является иерархия Вагнера [24]. Она является важным начальным сегментом длины шш топологической тонкой иерархии типа £о. Важной классификацией ш-апериодических языков является логическая тонкая иерархия. В работе [9] мы установили точное соотношение между уровнями этих иерархий.
Для ш-регулярных языков известно ([7]) соотношение REG(w')С BC(S0J). Следуя Чойке [4], мы рассматриваем обобщение автоматов Мюллера на слова длины а, где а < шш. В данной работе показано, что для любого уровня конечной борелевской иерархии существует полный в нем язык, распознаваемый автоматом Чойки (теорема 1). Из этого следует, что топологическая иерархия языков слов длины, большей ш и меньшей шш, намного сложнее иерархии Вагнера. Также мы устанавливаем точное соотношение между уровнями логической и топологической иерархий языков, распознаваемых автоматами Чойки (теорема 2).
Однако, остаются открытыми некоторые важные вопросы, касающиеся регулярных языков на ординальных словах и требующие, по всей видимости, разработки соответствующей техники и применения новых подходов. В частности, остается неясным существование степеней Вэджа, отличных от Ra Ra, Ra Ra, (Ra+i 0 Ra+1) (Ra U Ra) и статус равенства R, = Ra.
