Конечные преобразователи, двухленточные автоматы и биавтоматы — взаимосвязанные вычислительные модели, ведущие свое происхождение от концепции конечного автомата. В вычислениях этих машин проявляется много общих черт, и удивительно, что методы анализа, разработанные для одной из указанных моделей, не находят подходящего применения в других моделях. Целью данной статьи является разработка единой методики построения быстрых алгоритмов проверки эквивалентности для некоторых классов автоматов (конечных преобразователей, двухленточных автоматов, биавтоматов, магазинных автоматов), которые демонстрируют определенные черты детерминированного или однозначное поведение. Этот новый метод сводит проверку эквивалентности автоматов к проверке разрешимости систем уравнений над полукольцами языков или бинарных отношений. Как оказалось, такую проверку достаточно просто провести методом исключения переменных, используя некоторые комбинаторные и алгебраические свойства регулярных префиксных языков. Основные результаты, полученные в этой статье, таковы.

1.            При помощи алгебраического метода построен новый алгоритм проверки эквивалентности детерминированных конечных автоматов, имеющий сложность по времени O(n log n).

2.            Выделен новый класс префиксных конечных трансдьюсеров и показано, что проверка эквивалентности трансдьюсеров из этого класса может быть осуществлена новым методом за время, квадратичное (для префиксных трансдьюсеров реального времени) и кубическое (для префиксных трансдьюсеров с ɛ-переходами) относительно размеров анализируемых автоматов.

3.            Показано, что проблема эквивалентности для детерминированных двухленточных конечных автоматов сводится к задаче проверки эквивалентности префиксных конечных трансдьюсеров и может быть решена за время, кубическое относительно их размеров.

4.            Аналогичным образом установлена разрешимость проблемы эквивалентности для детерминированных конечных биавтоматов за время, кубическое относительно их размеров.

5.            При помощи нового метода построен алгоритм проверки эквивалентности для простых грамматик, соответствующих детерминированным магазинным автоматам с одним состоянием.

Рафаэль Робинсон показал, что все примитивно рекурсивные функции, зависящие от одного аргумента, и только они могут быть получены из двух функций s(x) = х +1 и q(x) = x - [√x]²

с помощью операций сложения +, суперпозиции ∗ и итерации i. Джулия Робинсон доказала, что из этих же двух функций с помощью операций сложения +, суперпозиции ∗ и операции ¯¹ обращения функций можно получить все общерекурсивные (при определённом условии на операцию обращения) и все частично рекурсивные функции. На основании этих результатов А. И. Мальцев ввёл в рассмотрение алгебру Рафаэля Робинсона всех одноместных примитивно рекурсивных функций и две алгебры Джулии Робинсон: частичную алгебру всех одноместных общерекурсивных функций и алгебру всех одноместных частично рекурсивных функций, и предложил исследовать свойства этих алгебр, в том числе, выяснить, существуют ли в этих алгебрах конечные базисы тождеств. В этой статье мы показываем, что конечного базиса тождеств ни в одной из указанных алгебр не существует.

Для обеспечения безопасности движения на железнодорожном транспорте регулярно проводится неразрушающий контроль рельсов с применением различных подходов и методов, включая методы вихретоковой дефектоскопии. Актуальной задачей является автоматический анализ больших массивов данных (дефектограмм), которые поступают от соответствующего оборудования. Под анализом понимается процесс определения по дефектограммам наличия дефектных участков наряду с выявлением конструктивных элементов рельсового пути. Данная статья посвящена задаче распознавания образов длинных конструктивных элементов железнодорожных рельсов по дефектограммам многоканальных вихретоковых дефектоскопов. Рассматриваются два класса конструктивных элементов рельсового пути: 1) счётчики осей подвижного состава, 2) пересечения рельсовых путей. Длинные отметки, которые не могут быть отнесены к этим двум классам, условно считаются дефектами и выносятся в отдельный третий класс. Для распознавания образов конструктивных элементов на дефектограммах применяется свёрточная нейронная сеть, реализованная в рамках открытой библиотеки TensorFlow. С этой целью каждая выделенная для анализа область дефектограммы преобразуется в графический образ в градации серого цвета размером 30 на 140 точек.

Статья посвящена сравнению стилометрических характеристик нескольких уровней, являющихся маркерами стиля прозаического текста, и анализу стилистических изменений русской и британской прозы 19-21 веков. Стилометрические характеристики включают в себя низкоуровневые характеристики, основанные на словах и символах, и высокоуровневые — ритмические. Подобные характеристики моделируют стиль текста и являются индикаторами времени его создания.

Вычисление всех характеристик происходит полностью автоматически, что позволяет проводить крупные эксперименты с художественными произведениями большого объёма и ускоряет работу эксперта-лингвиста. Для подсчёта стилометрических характеристик, в том числе основанных на результатах поиска ритмических средств, используется программа ProseRhythmDetector. В результате её работы каждый текст представляется в виде набора одних и тех же характеристик трёх уровней: символов, слов, ритма. Тексты объединяются по десятилетиям, для каждого десятилетия находятся средние значения стилометрических характеристик. Полученные модели десятилетий сравниваются при помощи стандартных метрик близости, результаты сравнения визуализируются в виде тепловых карт и дендрограмм. Эксперименты с двумя корпусами русских и британских текстов показывают, что в течение 19-21 веков появляются как общие тенденции изменения стиля для обоих корпусов, например, уменьшение количества ритмических средств в расчёте на одно предложение, так и собственные для каждого языка, например, динамика изменения длин слов и предложений. Стилометрические характеристики всех уровней выявляют схожесть стиля текстов, опубликованных в одном веке. Также характеристики трёх уровней в комплексе лучше демонстрируют уникальность каждого десятилетия, чем характеристики конкретного уровня. Это исследование показывает значимость стилометрических характеристик как маркеров стиля различных эпох и позволяет выявить тенденции изменения стиля на протяжении нескольких веков.

Логистическое уравнение с запаздыванием или уравнение Хатчинсона представляет собой одно из фундаментальных уравнений популяционной динамики и находит широкое применение в задачах математической экологии. В работе рассматривается семейство отображений, построеннное для этого уравнения на основе центральных разделенных разностей. Такие разностные схемы обычно используются при численном моделировании данной задачи. Представленные отображения сами по себе могут служить моделями динамики популяций, поэтому их изучение представляет значительный интерес. В работе сопоставляются свойства траекторий данных отображений и исходного уравнения с запаздыванием. Показано, что поведение решений отображений, построенных на основе центральных разделенных разностей, не сохраняет, даже при достаточно малой величине шага по времени, основных динамических свойств логистического уравнения с запаздыванием. В частности, у этого отображения при колебательной потере устойчивости ненулевого состояния равновесия не бифурцирует устойчивая инвариантная кривая. Эта кривая соответствует в таких отображениях устойчивому предельному циклу исходного непрерывного уравнения. Тем самым показано, что такая разностная схема не может быть использована для численного моделирования логистического уравнения с запаздыванием.

В работе рассматривается обобщение правил вывода зависимостей соединения, которые используются при проектировании схемы базы данных, удовлетворяющей требованиям пятой нормальной формы. В предшествующих работах, посвященных данной проблематике, делаются попытки построить системы аксиом таких зависимостей, основанных на правилах вывода. Однако, если обоснование непротиворечивости (надежности) полученных аксиом не вызывает затруднений, то доказательство полноты в общем случае не получило удовлетворительного решения. Прежде всего, это связано с ограниченностью самих правил вывода. В данной работе акцентировано внимание на двух оригинальных системах аксиом, представленных в работах Sciore и Malvestuto. Для зависимостей включения получена система правил, которая обобщает существующие системы и при этом имеет меньше ограничений. В работе представлено доказательство выводимости известных систем аксиом из представленных правил вывода. Кроме того, приводится доказательство непротиворечивости (надежности) этих правил. Вопрос о полноте формальной системы, основанной на представленных правилах, не нашел положительного решения. В заключение отмечена теоретическая и практическая значимость правил вывода для зависимостей соединения.