Препринты Института систем информатики СО РАН 1997 г.

В данной работе описывается простой и эффективный алгоритм, реализующий замкнутый набор булевых операций {объединение, пересечение, разность, симметрическая разность} над множествами гранично заданных многоугольников (boundary represented polygons) на плоскости. Замкнутость набора операций подразумевает корректную обработку многоугольников с самокасаниями (или кратными вершинами), т.е. результирующие многоугольники, полученные с помощью предлагаемого алгоритма, удовлетворяют предъявляемым требованиям к входным данным алгоритма. Асимптотическая оценка времени выполнения алгоритма не превышает O(n log*n + k + z log n), где n - общее число вершин многоугольников-операндов, k - число точек пересечения их рёбер, z - общее число контуров многоугольников-операндов. Таким образом, предложенный алгоритм по эффективности не уступает большинству алгоритмов, известных на сегодняшний день.

Представлен проект создания информационной системы СИМИКС для проведения гуманитарных исследований в области культуры, который выполняется при поддержке РГНФ (грант N 96-04-12030). Данная информационная система ориентирована на накопление и представление знаний в области современной музыки и киноискусства, а также в области истории развития информатики, поскольку, на взгляд авторов, информатика в современном обществе является элементом культуры. При отборе информационных данных акцент делался на отражении региональных особенностей перечисленных выше областей знаний. Предлагаются описания особенности тематики информационной системы и ее структуры. Информационная система СИМИКС предназначена для работников культуры и искусствоведов, а также для преподавателей и студентов таких профильных вузов, как консеpватоpии, Институты и колледжи культуры, а также для всех, кто интересуется вопросами современной культуры и ее истории.

Р. Глаббек и У. Гольц ввели ряд бисимуляций на структурах событий: интерливинговую, шаговую, частичного порядка, сохраняющую историю; установили их свойства и взаимосвязи. Ф. Шериф исследовал обратную бисимуляцию в интерливинговой семантике. На системах переходов Ф. Милнером было введено понятие слабой бисимуляции. В данной работе рассматриваются обратные варианты бисимуляционных эквивалентностей на структурах событий в различных семантиках, определяется ряд бисимуляций, явно отражающих параллелизм и конфликт между событиями структуры. Для перечисленных эквивалентностей вводятся их слабые варианты, которые используют понятие "невидимых" действий. Установлена полная иерархия всех рассмотренных эквивалентностных понятий. Исследовано сохранение/несохранение под действием операции уточнения для всех вновь введенных бисимуляций.

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