Категорні методи в теорії мовних перетворювачів

Мовні подання - один із способів формалізації процесів, пов'язаних з використанням комп'ютерної техніки для вирішення як теоретичних, так і практичних задач, які так чи інакше охоплюють всі сторони сучасного життя. Сюди належать проблеми побудови засобів моделювання систем, формалізації процесів обробки інформації, розробки забезпечення обчислювальних машин.

Як один з напрямів загальної теорії в дисертації розроблені методи й засоби, які застосовуються до аналізу проблем моделювання систем і, зокрема, до моделювання та розробки систем автоматизованого управління й автоматизованого проектування систем управління.

У дисертації розглянуті розв'язання чотирьох груп проблем. Перша - створення загальної методології використання теоретико-категорних представлень для вирішення проблем аналізу формальних мов і перетворення мовної інформації. Це питання категорного подання синтаксису і семантики формальних мов, побудови категорних автоматів, розгляд проблем обчислювальності категорій та функторів. Сюди належить також введення перетворюючих категорій, які використовуються для аналізу скінченних перетворювачів.

Друга група проблем - це розгляд різних видів перетворювачів, які можуть задаватися як у вигляді граматик, так і у вигляді автоматів, а також змішаних кон-струкцій. Запропоновано цілий ряд нових представлень різних варіантів мовних перетворювачів. Це синхронізовані та семантично-контекстні мови, перетворювачі у вигляді магазинних автоматів з додатковими регістрами й зв'язані магазинні перетворювачі, М-системи. Побудовані алгоритми аналізу і синтезу таких перетворювачів, визначені властивості зв'язаних з ними мов.

Розроблений метод побудови категоріальних систем, який об'єднує можливо-сті алгебраїчного подання окремих кроків алгоритму порівняння двох автоматів, із загальною формою результату алгоритму у вигляді деякого мовного перетворювача, який зв'язує між собою порівнювані множини морфізмів. Цей метод використаний для вирішення конкретних проблем (третя група), які відносяться до теорії мовних перетворювачів.

Третя група проблем, розглянутих у дисертації, пов'язана з вирішенням проблем, що безпосередньо представлені або зводяться до мовних перетворювачів. Саме ця частина служить доказом ефективності запропонованої методології.

Вирішена відкрита проблема Гінзбурга-Хіббарда - розв'язуваність існування скінченних несинхронних перетворювачів, які відображають одну регулярну мову на іншу. Вирішена в загальному вигляді проблема еквівалентності детермінованих магазинних автоматів, поставлена ще в 1965 році. В обох випадках розроблені алгоритми, які вирішують ці проблеми.

Доведення еквівалентності ДМА дозволяє одержати рішення десяти відкритих проблем, поставлених у різний час Д. Кнутом, С. Гінзбургом, Е. Фрідманом, А.В. Анісімовим, А. Ахоу і Д. Ульманом та іншими видатними фахівцями в області інформатики. Ці проблеми належать до різних напрямків теоретичної інформатики - теорії мов, схем програм, теорії перетворювачів та теорії формальних граматик.

Четверта група проблем визначається застосуванням розробленої методології до проблем автоматизації проектування систем управління. Мовні подання є одним із засобів формалізації процесів, пов'язаних з використанням комп'ютерної техніки для вирішення як теоретичних, так і практичних задач, пов'язаних з проблемами моделювання систем і формалізації процесів обробки інформації.

У дисертації запропонована мова L-структур і доведена можливість її використання для опису процесів переробки інформації, пов'язаної з послідовною розробкою систем. За допомогою цієї мови запропонована схема формального опису процесу модифікуючого моделювання, який може бути використаний для послідовного перетворювання однієї моделі в іншу. Дані результати використані при розробці методів автоматизації проектування АСУ.

Подальші дослідження, визначені запропонованим в дисертації напрямком, передбачають можливість застосування побудованих схем для формалізації задач перетворення інформації, пов'язаної з побудовою комп'ютерного та програмного забезпечення систем різних класів. Вони створюють новий інструмент дослідження цих складних проблем.

Основні положення дисертації, опубліковані в таких працях

Мейтус В.Ю. Некоторые свойства синхронизируемых грамматик // Теоретическая кибернетика. - Киев: Ин-т кибернетики АН УССР, 1970. - Вып. 1. - С. 30-43.

Мейтус В.Ю. Магазинные автоматы с дополнительными регистрами // Кибернетика. - 1970. - № 5. - С. 10-19.

Мейтус В.Ю. Магазинные автоматы с дополнительными регистрами и проблема перевода // Кибернетика. - 1971. - № 5. - С. 4-5.

Мейтус В.Ю. Обобщенные преобразующие грамматики //Кибернетика. - 1972. - № 6. - С. 17-27.

Мейтус В.Ю. Абстрактное задание синтаксиса формальных языков // Докл. АН СССР. - 1974. - 216, № 2. - С. 261-263.

Мейтус В.Ю. Синтаксические структуры в формальных языках. - Киев: Ин-т кибернетики АН УССР, 1974. - 28 с.- (Препр. / АН УССР, Ин-т кибернетики; 74-49).

Мейтус В.Ю. Семантические структуры в формальных языках. Киев: Ин-т кибернетики АН УССР, 1975. - 28 с. - (Препр. / АН УССР, Ин-т кибернетики; 75-18).

Мейтус В.Ю. Семантически-контекстные грамматики и их свойства // Кибернетика. - 1977. - № 4. - С. 27-34.

Мейтус В.Ю. Преобразующие категории и конечные преобразователи, I // Кибернетика. - 1978. - № 2. - С. 26-34.

Мейтус В.Ю. Преобразующие категории и конечные преобразователи, II // Кибернетика. - 1978. - № 3. - С. 15-18.

Мейтус В.Ю. Структурно-функциональные модели в системе автоматизации проектирования // Методы проектирования АСУ. - Киев: Ин-т кибернетики АН УССР, 1982. - С. 24-30.

Мейтус В.Ю. Автоматизация проектирования АСУ: технология реализации // Индустрия построения республиканской автоматизированной системы управления (РАСУ). - Киев: Ин-т кибернетики им.В.М. Глушкова АН УССР, 1985.- С. 58-63.

Мейтус В.Ю. Функциональные методы проектирования АСУ и синхронизации проектных решений // Взаимодействие и совместимость в РАСУ УССР. - Киев: ГлавНИИВЦ Госплана УССР, 1988. - С. 72-77.

Мейтус В.Ю. Проблема эквивалентности строгих детерминированных магазин-ных автоматов, действующих в реальном времени // Кибернетика. - 1989. - № 5 - С. 14-25.

Мейтус В.Ю. Макетирование систем в технологии разработки ИАСУ // Информатизация производственных систем в современных экономических условиях.- Киев, 1992.- С. 53-57.

Мейтус В.Ю. Разрешимость проблемы эквивалентности детерминированных магазинных автоматов // Кибернетика. 1992. № 5. С. 45.

Мейтус В.Ю. К проблеме эквивалентности детерминированных магазинных автоматов // Кибернетика и системный анализ. 2007. № 2. С. 39.

Вельбицкий И.В., Мейтус В.Ю., Ющенко Е.Л. Проблема трансляции и трансля-ционно-ориентированные языки // II Всесоюз. конф. по проблемам теоретической кибернетики. - Новосибирск, 1971. - С. 43-44.

Вельбицкий И.В., Мейтус В.Ю., Ющенко Е.Л. Проблема трансляции и М-си- стемы // Математическое обеспечение ЭЦВМ. - Киев: Ин-т кибернетики АН УССР, 1971 - С. 3-21.

Вельбицкий И.В., Мейтус В.Ю., Ющенко Е.Л. М-формализмы и их применение к операционным системам // Тр. симп. "Теория языков и методы построения систем программирования". - Киев: Ин-т кибернетики им. В.М. Глушкова АН УССР,1972. - С. 22 -30.

Вельбицкий И.В., Мейтус В.Ю., Ющенко Е.Л. Теория М-систем и ее приложения // Проблемы кибернетики. - 1973. - Вып. 27. - С. 251-266.

Мейтус В.Ю., Вершинин К.П. О некоторых неразрешимых проблемах в вычислимых категориях // Докл. АН СССР. -1974. - 216, № 1. - С. 42-43.

Шкурба В.В., Мейтус В.Ю. Автоматизация проектирования АСУ и системы автоматизации проектирования // Тез. 8 Всесоюз. совещ. по проблемам управления. - Таллин, 1980. - Кн. З. - С. 581-582.

Шкурба В.В., Мейтус В.Ю., Юрков В.М. Система автоматизированного проектирования АСУ // АСУ: автоматизация проектирования и моделирования. - Киев: Ин-т кибернетики им. В.М. Глушкова АН УССР, 1981. - С. 3-15.

Шкурба В.В., Мейтус В.Ю. Сикорская В.А., Таран Л.Ю. Структурно-функциональный проект САПР // Методы проектирования АСУ. - Киев: Ин-т кибернетики им. В.М. Глушкова АН УССР, 1982. - С. 30-45.

Шкурба В.В., Мейтус В.Ю. Модифицирующее моделирование в системе автоматизации проектирования // Тез. конф. "Проблемы проектирования и создания ВЦ КП и развития АСУ".- Душанбе, 1983.- С. 64-65.

Шкурба В.В., Мейтус В.Ю. Модифицирующее моделирование - основа системы автоматизации // Тез. конф. "Автоматизация проектирования систем управления". - Ереван, 1984. - С. 19-21.

Мейтус В.Ю., Сикорская В.А. Структурно-функциональные модели и сценарные технологии // Перспективы развития РАСУ. - Киев: Ин-т кибернетики им. В.М. Глушкова АН УССР, 1984. - С. 78-82.

Мейтус В.Ю., Сикорская В.А. Языковые модели при разработке функциональ-ных схем АСУ // Создание интегрированных систем управления в народном хозяйстве. - Киев: Ин-т кибернетики им. В.М. Глушкова АН УССР, 1986.- С. 40-45.

Меіtus V.Yu. Abstract Assignment of the Syntax of Formal Languages. // Soviet Math. Docl. - 15, N 3.- Р. 779-781.

Меіtus V.Yu., Vегsinin К.Р. On Some Unsolvable Problem in Computable Categories // Soviet Math. Docl. - 15, N 3. - Р. 752-754.

Shkurba V.V., Меіtus V.Yu. Problems of Construction of ACS Design Automation Systems //Computer-Aided Control System Desigh - M.:ІСS, 1980.- Р. 36-38.

Анотації

Мейтус В.Ю. Категорні методи в теорії мовних перетворювачів. - Рукопис.

Дисертація на здобуття наукового ступеня доктора фізико-математичних наук за спеціальністю 01.05.03 - математичне та програмне забезпечення обчислювальних машин і систем. - Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, 2008.

Дисертаційну роботу присвячено розробці, дослідженню та використанню нових методів в теорії мовних перетворювачів, які широко використовуються при вирішенні проблем, пов'язаних з різними напрямками інформатики та теорії і практики моделювання систем.

Розроблена методологія використання теоретико-категорних форм для дослідження проблем теорії формальних мов і перетворення мовної інформації. Ця методологія включає категорне подання синтаксису і семантики формальних мов, побудову категорних автоматів, аналіз проблеми обчислюваності категорій. Запропоновано декілька різних варіантів мовних перетворювачів, які використовують різні схеми пам'яті. Розроблений метод категоріальних систем, що дозволяє послідовно будувати перетворювачі з заданими ознаками та досліджувати їх особливості.

Вирішена відкрита проблема розв'язуваності існування несинхронного скінченного перетворювача, який відображає одну регулярну мову на іншу. Вирішена в загальному вигляді проблема еквівалентності детермінованих магазинних автоматів. Цей результат дав можливість розв'язати цілий ряд інших відкритих проблем, які належать до різних напрямків теоретичної інформатики - теорії мов, схем програм, теорії формальних граматик.

Розроблена методологія застосування мовних перетворювачів до проблем автоматизації проектування систем управління, пов'язаних із задачами моделювання систем і формалізацією процесів автоматизованої обробки інформації.

Ключові слова: формальні мови, синтаксис, семантика, мовні перетворювачі, категорні системи, категорні автомати, скінченні мовні перетворювачі, детерміновані магазинні автомати, М-системи, еквівалентність автоматів, моделювання систем, автоматизація проектування систем.

Мейтус В.Ю. Категорные методы в теории языковых преобразователей. - Рукопись.

Диссертация на соискание ученой степени доктора физико-математических наук по специальности 01.05.03 - математическое и программное обеспечение вычис-лительных машин и систем. - Институт кибернетики им. В.М. Глушкова НАН Украины, Киев, 2008.

Диссертация посвящена разработке, исследованию и использованию новых методов в теории языковых преобразователей, которые применяются при решении проблем, связанных с различными направлениями информатики, теории и прак-тики моделирования систем.

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

Основное направления исследования заключается в разработке и изучении различных форм языковых преобразователей, связанных с разными классами преобразуемых языков

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

Предложен целый ряд новых представлений различных вариантов языковых преобразователей. Это синхронизируемые и семантически-контекстные языки, магазинные автоматы с дополнительными регистрами и обобщенные магазинные автоматы с дополнительными регистрами, М-системы. Разработаны алгоритмы анализа и синтеза таких преобразователей, исследованы свойства преобразуемых ими языков.

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

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

Разработанный в диссертации метод сравнения категориальных систем использован для решения в общем виде проблемы эквивалентности детерминированных магазинных автоматов (ДМА), сформулированной еще в 1965 году. Сначала последовательно строится категориальная система, использующая для своего построения процедуру, состоящую из специальных операций над множествами морфизмов. Затем разработан алгоритм сравнения, который решает эту проблему эквивалентности за конечное число шагов, на основании построенных оценок.

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

Языковые представления являются одним из способов формализации процессов, связанных с использованием компьютерной техники для решения как теоретических, так и практических задач, которые, так или иначе, охватывают все стороны современной жизни. Сюда относятся и проблемы построения систем, моделирования, формализации процессов обработки информации, создание математического и программного обеспечения вычислительных машин.

В диссертации предложен язык L-структур и доказана возможность его использования для описания процессов переработки информации, связанной с последовательной разработкой систем. Этот язык был использован при разработке формального описания метода модифицирующего моделирования, который заключается в последовательной коррекции существующей системы к ее необходимому представлению. Эти результаты, в частности, были использованы при разработке методов автоматизации проектирования АСУ, на основе последовательного перехода от общих описаний разрабатываемой системы к более детальным и конкретным описаниям.

Ключевые слова: формальные языки, синтаксис, семантика, языковые преобразователи, категорные системы, категорные автоматы, конечные языковые преобразователи, детерминированные магазинные автоматы, М-системы, эквивалентность автоматов, моделирование систем, автоматизация проектирования систем.

Мeytus V.Ju. Сategory methods in the theory of language converters. - Manuscript.

The thesis on competition of a scientific degree of the doctor of physical and mathematical sciences, speciality 01.05.03 - mathematical and program maintenance of computers and systems. Institute of Cybernetics, Ukrainian National Academy of Sciences, Kyiv, 2008.

Doctoral thesis is devoted to construction of new methods of representation and solution of problems theory of language converters which are used in various sections of theoretical computer science and tasks of simulation of systems. Algebraic category approach with reference to problems of the analysis of language converters is developed in the thesis. The constructed mathematical theory contains the algebraic analysis of syntax and semantics of formal languages, and also automata, used as a resource of representation of languages.

To construction or researching of language converters many theoretical problems are reduced. Therefore the special device of research is developed to the broad audience of language problems. The main attention is accented on tasks of synthesis of various sorts of the language converters presented as M-systems, and on tasks of decidability of problems of existence of mappings, linked to some classes of automata.

A lot of new representations of various variants of language converters is offered. These are synchronizable and semantic-contextual languages, pushdown automata with additional registers and the generalized pushdown automata with additional registers, and also M-systems. Analysis and synthesis algorithms of such automata are developed, researched properties of languages transform these automata.

The methods developed in the thesis, including method of construction categorical systems, are used for solution of problems, presentable or reduced to to language converters. This part is for the proof of efficiency offered methodology. In particular, Ginsburg-Hibbard open problem for finite converters is solved. The problem of equivalence the determined pushdown automata (DPDA) is solved in a general view. In both cases the algorithms are developed, which solve each problem.

The proof of equivalence DPDA has allowed to receive solution of ten open problems put at various times by specialists of computer science. These problems concern to different areas theoretical computer science - theories of formal languages and converters, schemes of programs, the theory formal grammars.

Language representations are one of ways formalizing of the processes linked to usage computer equipment for solution as theoretical, so practical tasks which anyhow cover all the sides modern life. Problems of construction of systems here concern, simulations, formalizing of processes of information processing, creation mathematical and software maintenance of computers.

In the thesis language of L-structures is offered and its possibility is proved usages for the description of processes of processing of the information linked with sequential system engineering. These results have been used by development of methods of automation of designing of the management information system.

Key words: formal languages, syntax, semantic, language converters, categorical systems, categorical automata, finite language converters, deterministic pushdown automata, M-systems, equivalence of automata, simulation of systems, automation of system design.

Размещено на Allbest.ru