Сверхслова, меры на них и их полупрямые произведения (1104768), страница 15
Текст из файла (страница 15)
Первым аргументом отображения будут являться последовательности в алфавите из пар букв, в которых верхняя буква больше или равна нижней, а одиночные буквы теперь берутсяиз {⊕, ⊙, ⊖} . Вторым аргументом будет дополнительная последовательность(которая опять будет предполагаться распределённой по ).
Принимаемые значения — последовательности в том же алфавите пар букв.Лемма 3.23. Пусть для и выполняются следующие условия:1) Для любых мер > на словах над алфавитом {⊕, ⊙, ⊖} и для любойинвариантной меры Ω на словах над алфавитом из пар символов {⊕, ⊙, ⊖}с первой проекцией, равной и второй проекцией, равной , образы проекций Ω при Clean равны Clean и Clean , соответственно.
Здесь и понимаются как операторы, и распределение дополнительногослучайного аргумента (из определения как оператора на мерах).2) Для любого сверхслова над алфавитом пар символов, такого что перваякомпонента больше либо равна второй, это же неравенство выполнено дляего образа при .Тогда монотонен относительно D .Доказательство. Если мера Ω является мерой, существование которойподтверждает отношение D между двумя мерами, то Ω подтверждаетD между их образами. Лемма 3.23 доказана.Нам достаточно построить оператор , обладающий свойствами,описанными в предыдущей лемме.94Пусть задана последовательность в алфавите пар символов и дополнительная случайная последовательность из нулей и единиц (на каждомместе выбор делается независимо, и вероятность единицы равна ). Теперьопишем, как вычисляются компоненты пары, стоящей на заданном месте вобразе.Каждый символ из верхней и нижней компоненты будет либо оставаться неизменным, либо заменяться на ⊙ по следующему правилу.
Рассмотрим по отдельности верхнюю и нижнюю компоненту . Назовём “связанными” те символы, которые входят в подслова вида ⊕ ⊙ ⊖ , > 0 . Остальныесимволы будем считать “свободными”. Будем считать, что блок — это либо⊕⊙ ⊖ , либосвободный символ. Заметим, что возможна ситуация,(︁ отдельный)︁например,⊕⊕⊕⊖⊕⊖⊖⊖, когда свободный символ стоит над связанным, и наоборот. Свободные символы всегда переносятся в образ без изменений. Теперьопределим, что происходит с блоками. К некоторым из них будет примененаоперация обнуления, то есть замены каждого символа блока на ⊙ .
Для того,чтобы образы блоков были независимы внутри верхней и нижней компоненты, будем требовать, чтобы образ блока зависел только то символов, стоящихв и в на позициях, занимаемых рассматриваемым блоком. Для того,чтобы одновременно сохранить неравенство между верхней и нижней компонентой и при этом получить правильные вероятности превращений, будемпривязывать обнуление нижнего блока к обнулению верхнего блока, которыймог бы обнулиться и испортить неравенство.Если рассматривается блок в верхней компоненте, то просто заменим егона блок из одних нулей, если над его первым символом ( ⊕ ) стоит единица.Ясно, что каждый блок сохраняется с вероятностью 1 − и обнуляется свероятностью , что не отличается от происходящего при .Теперь рассмотрим блок в нижней компоненте.
Во-первых, возможно,что над последним символом блока ( ⊖ ) стоит тоже ⊖ . Тогда рассмотримслово, стоящее над всем блоком. Оно начинается с ⊕ , так только он разрешён над ⊕ . Оно не содержит ⊖ , кроме последнего символа,потомучто ⊖(︁)︁* * *⊖разрешён только над ⊖ .
Таким образом,мы получаем ⊕⊕ ⊙ ⊙ ⊙ ⊖ . В любом95случае, ⊖ в верхней компоненте является связанным, и соответствующий ему⊕ лежит в пределах рассматриваемого блока. Кроме того, если левый ⊕ вверхней компоненте связан, то он связан с правым ⊖ в верхней компоненте.Поэтому в этом случае будем рассматривать ⊖ в крайней правой позициифрагмента над блоком в верхней компоненте, находить парный ему ⊕ и обнулять блок тогда и только тогда, когда на (︁позиции, )︁соответствующей этому⊙⊙⊙⊖плюсу, в стоит 1 . Например, для случая ⊕нам надо рассмотреть⊕⊙⊙⊙⊖(︁)︁⊙⊕⊙⊖символ в на первой позиции, а для ⊕— на третьей.⊕⊙⊙⊙⊖Пусть теперь у нас есть блок в нижней компоненте, над последним символом которого стоит не ⊖ .
В этом случае над первым символом (которымявляется ⊕ ) стоит ⊕ , и мы обнулим блок, если на этой позиции в стоит 1 .Заметим, что мы сначала, не обращаясь к , определяем одну позициювнутри блока, проверяем символ в на этой позиции, и потом в соответствиис ним обнуляем или нет блок. Распределение вероятностей образов в любомслучае соответствует считыванию одного символа из .Теперь проверим неравенство между последовательностями. Если обасимвола перенесены или оба обнулены, то проверять ничего не надо — попредположению, что вначале неравенство верно или потому, что ⊙ 6 ⊙ . Если при обнулении одного символа в паре верхний не уменьшился, а нижнийне увеличился, то опять неравенство сохранится.Более того, если один из(︁ )︁символов был уже ⊙ , или если была пара ⊕⊖ , то неравенство будет выпол(︁ )︁нено.
Итак, нам надо доказать, что если в ⊕обнулился верхний символ⊕(︁ )︁или в ⊖обнулился нижний, то и второй тоже обнулился.⊖(︁ )︁Рассмотрим сначала случай ⊖⊖ . Если нижний ⊖ обнулился, то он связанный, но верхний, как мы уже знаем, тоже связан. Более того, их обнулениезависит от одного и того же символа(︁ )︁ в , что и требовалось доказать.Теперь рассмотрим случай ⊕⊕ . Верхний ⊕ обнулился, значит, он связанный. Рассмотрим слово вида ⊕ ⊙ ⊖ , в которое он входит. Мы знаем,что под его первым символом стоит ⊕ . Под его последним символом стоит,разумеется, ⊖ .
В середине — под ⊙ — могут быть ⊙ и ⊖ . Поэтому ⊕ ,96стоящий под первым ⊕ , связанный. Докажем, что его обнуление зависит оттого, что стоит в на той самой позиции, где он сам находится. Действительно, чтобы это было не так, соответствующий ему ⊖ должен стоять под ⊖ .Но соответствующий ему ⊖ стоит не правее конца рассматриваемого словасверху (как и при анализе распределения вероятностейдля(︁ вычёркивания)︁⊙⊙⊙⊖каждого блока, у нас есть два случая: устроенные как ⊕⊕ ⊙ ⊙ ⊙ ⊖ , то есть с(︁)︁⊕⊙⊙⊙⊖одинаковыми блоками сверху и снизу, и устроенные как ⊕ ⊙ ⊖ ⊙ ⊖ , то естьс более коротким блоком снизу). Более того, если соответствующий ⊖ стоитпод ⊖ , то тогда мы имеем два одинаковых блока друг над другом, так чтоиз обнуления верхнего символа в любом случае следует обнуление нижнего,что и требовалось.Теорема 3.4 доказана.97Список литературы1.
M.Lothaire. Algebraic Combinatorics on Words. Cambridge University Press,2002.2. Притыкин Ю. Л. Конечно-автоматные преобразования строго почти периодических последовательностей // Математические заметки.2006.Т. 80, № 5. С. 751–756.3. Muchnik A., Semenov A., Ushakov M. Almost periodic sequences // Theoretical Computer Science. 2003. Vol.
304. P. 1–33.4. Притыкин Ю. Почти периодичность, конечно-автоматные преобразования и вопросы эффективности // Известия вузов. Математика. 2010.Т. 1. С. 74–87.5. Притыкин Ю. Действие конечных автоматов на почти периодическиепоследовательности. доклад на Колмогоровском семинаре. 2005.6. Шень А. Редкие множества. доклад на Колмогоровском семинаре. 2009.7. Н.К. Верещагин, В.А. Успенский, Шень А.
Колмогоровская сложность иалгоритмтическая случайность. М.: МЦНМО, 2012.8. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.:МЦНМО, 2001.9. Bienvenu L., Romashchenko A., Shen A. Sparse sets // Proceedings of Symposium on Cellular Automata, Journées Automates Cellulaires (JAC 2008).2008. P. 18–28.10. Makarychev K., Makarychev Y., Romashchenko A., Vereshchagin N. A newclass of non Shannon type inequalities for entropies // Communications inInformation and Systems. 2002. Vol. 2, no. 2.
P. 147–166.9811. Тоом А. Устойчивые и притягивающие траектории в многокомпонентныхсистемах // Многокомпонентные системы / Ed. by Р. Л. Добрушин.Москва: Наука, 1978.12. Gács P. Reliable Cellular Automata with Self-Organization // Journal ofStatistical Physics. 2001. Vol. 103, no. 1/2. P. 45–267.13. Toom A. Non-ergodicity in a 1-D particle process with variable length //Journal of Stat. Physics. 2004.
Vol. 115. P. 895–924.14. Тоом А. Клеточные автоматы. НМУ, спецкурс. 2004.15. Н.К. Верещагин, Шень А. Вычислимые функции. 2-е изд. М.: МЦНМО,2008.Список публикаций автора по теме диссертации16. Pаскин М. А. О нижней оценке регулятора прямого произведения почтипериодической и периодической последовательностей // Вестник Московского Университета. Серия 1. Математика и механика.
2011. № 6. С. 7–11.17. Pаскин М. А. Согласованная с отношением порядка копроекция вычислимых мер не всегда вычислима // Вестник Московского Университета.Серия 1. Математика и механика. 2012. № 2. С. 17–19.18. Pаскин М. А. Частичный порядок Тоома транзитивен // Проблемы передачи информации. 2012. Т. 48, № 2. С. 79–99..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
