Диссертации и авторефераты Украины
Перейти на каталог
Каталог диссертаций

Я ищу:
Диссертация / Автореферат

Диссертационная работа:

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

Скачать диссертацию *

* Ссылка размещена на правах рекламы



Аннотация к работе:

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

Рукопис.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


Меню
Реклама



2006-2009 © Диссертации и авторефераты Украины