Total number
Full text
Total number
Full text
Number of local repositories
Full text
0412U003992,
к.ф.-м.н.
22-06-2012
o
Algebras of languages representable by labeled graphs
Prianychnykova Olena Oleksiivna,
popup.head Grunsky Igor Sergeevich
popup.opponent Летичевський Олександр Адольфович
popup.opponent Рисцов Ігор Костянтинович
Дисертаційну роботу присвячено проблемі розробки і дослідження алгебраїчних засобів для аналізу поведінки позначених графів і синтезу таких графів із заданою поведінкою. Введено нове поняття позначеного графа, що охоплює ряд відомих видів графів, які використовуються в комп'ютерних науках. Запропоновано матричне представлення позначених графів, алгебра успішних шляхів в графах та алгебра матриць, породжена алгеброю шляхів, що дозволяє за матрицями графів будувати матриці їх композицій. Створено алгебри, що дозволяють аналізувати поведінку таких графів. Доведено теорему, яка є узагальненням теореми Кліні-Шютценберже на випадок, коли множина поведінок графів не є півкільцем; знайдено умови за яких множина всіх можливих поведінок позначених графів співпадає з множиною всіх можливих значень термів введеної алгебри. Для окремих випадків позначених графів запропоновано спосіб побудови алгебри, яка має необхідніи властивості. Досліджено основні властивості алгебри мов, що можуть бути представлені у графах з позначеними вершинами, знайдено алгебраїчну й лінгвістичну характеризації мов, що можуть бути представлені регулярними виразами цієї алгебри. Введено поняття детермінованого графа з позначеними вершинами та показано, що класи мов, що можуть бути представлені детермінованими й недетермінованими графами, збігаються. Запропоновано спосіб детермінізації графів. Доведено критерій того, що мова може бути представлена графом з позначеними вершинами. Доведено, що для будь-якої мови, що може бути представлена графом з позначеними вершинами, існує єдиний з точністю до ізоморфізму мінімальний повний детермінований граф, та запропоновано спосіб мінімізації графів. Показано, що алгебра мов, що можуть бути представлені у графах з позначеними вершинами, є вільною алгеброю квазібагатовиду зі скінченним базисом, для цієї алгебри розроблено систему аксіом, яка складається з тотожностей і квазітотожностей, та доведено її повноту. Ключові слова: позначені графи, поведінка графа, мови в алфавіті позначок, алгебри мов.
2012-06-22
2020-04-04
Updated: 2025-12-15
Saving a scientific data set occurs in two stages:
1.) Creating a data set
Enter the name of the set, a brief description of the set (annotation), and click the “Create set” button. After that, a draft data set will be automatically created, which you can save for further work with the set. The system will redirect you to the “Data set information” page.
2.) Filling in the data
On the “Data set information” page, you need to fill in all the fields related to the data set and upload the files.
Please note! Each file is uploaded separately. This is done to ensure the stable operation of the system.
Once you have filled in the information about the scientific data set and added the necessary files, you can save the draft or send the data to the system.
Please note! Once the data has been sent, you cannot change it.
Drafts are necessary for storing the data set and editing it before sending.
All accounts on the NRA website go through a standard registration procedure and are verified. However, in order to obtain additional features, such as publishing open reviews of academic texts, verification by affiliation is required.
To obtain the status “verified”, you must change your primary email address to a corporate one, which is tied to a scientific or educational institution.
For example: user@ukrintei.ua, user@nas.gov.ua
After confirming your corporate email address, your account will be automatically verified by affiliation.
If your email address is corporate, but your account does not have a verification mark, you need to write to us at the email address NRAT@ukrintei.ua. After verification, we will add your address to the database, and your account will be verified.
After completing the verification procedure for affiliation, you can change the primary email address to a convenient one for you, without losing your status during the current verification.
You only need to verify for affiliation once.
* We use corporate addresses from the Unified State Database on Education and the State Register of Scientific Institutions Supported by the State
To search for news published on the official website of NRАT in the “News” section, you need to enter one word, several words, or an exact phrase in the search field. Different terms are separated by spaces.
The search is performed everywhere – in the title and the news text.
For a more comprehensive result, it is recommended to use word stems (parts of words without endings).
When using multiple words for the search, they are combined using one of the logical methods described below.
By default, the logical connector “and” is used. In this case, search results will include all news releases that contain the specified words, even if they are located separately from each other and are in different parts of the text.
Example: Search phrase: OECD report. Search result: all news containing the words “report” and “OECD” in the text and in the title, both together and separately.
If a phrase or phrase is enclosed in quotation marks (“), the results will include all publications where this exact phrase or phrase is found.
Example: Search phrase: “OECD report.” Search result: all news containing the exact phrase “OECD report.”
If you know the publication date of the news or are interested in a specific time frame in which they were published on the website, you can select such a date or date range in the additional field that looks like a calendar. The date is entered in the format year-month-day and confirmed by clicking on the corresponding date in the calendar dropdown. You can enter a date or choose one by browsing through the calendar by months and years. By default, the interval starts from the oldest date (2018-01-23) and ends with the current date.
You can also use one or more hashtags, which are located under the search field on the right side of the “News” page.
Please note: The search for academic texts is carried out in a separate search window at the following link https://nrat.ukrintei.ua/searchdb.
