|
ИСТИНА |
Войти в систему Регистрация |
Интеллектуальная Система Тематического Исследования НАукометрических данных |
||
О проблеме эквивалентности для нисходящих детерминированных древесных автоматовстатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАКСтатья опубликована в журнале из списка Web of Science и/или Scopus
- Авторы: Захаров В.А., Чжибо Дэн
- Журнал: Вестник Московского университета. Серия 15: Вычислительная математика и кибернетика
- Номер: 4
- Год издания: 2025
- Издательство: Изд-во Моск. ун-та
- Местоположение издательства: М.
- Первая страница: 38
- Последняя страница: 45
- DOI: 10.55959/MSU/0137-0782-15-2025-49-4-38-45
- Аннотация: Мы представляем эффективный алгоритм для проверки эквивалентности состояний детерминированных конечных нисходящих (top-down) древесных автоматов (DFTAs). В отличие от строковыхавтоматов, древесные автоматы работают с иерархическими структурами, и это обстоятельствоосложняет алгоритмические задачи. Наш подход сводит проблему проверки эквивалентности кпроверке разрешимости систем уравнений, которые определяют поведение DFTA. Эта проверкаосуществляется при помощи правил равносильных преобразований, которые либо обнаруживаютнеразрешимость или несовместность уравнений, либо приводят систему к такому виду, которыйгарантирует существование решения. Доказаны корректность и завершение алгоритма и установлена верхняя оценка O(n2) времени его выполнения в модели вычислений RAM (Random AccessMachine) с указателями.
- Добавил в систему: Захаров Владимир Анатольевич