Использование конечных автоматов в качестве ключей от контейнера

Question

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

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

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

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

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

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

Может кто-нибудь предложить хорошую газету для чтения? - или, по крайней мере, дайте мне знать, если я скачал красную сельдь или нет?

Answer 1

вот тезис 1992 года, где они производят минимизированные канонические автоматы: Минимизация недетерминированных конечных автоматов

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

<from_state, symbol, to_state, is_accepting_final_state>

Это должно решить проблему.

Answer 2

Я считаю, что вы можете получить каноническую форму из свернутых автоматов. Для любых двух эквивалентных автоматов их минимизированные формы изоморфны (я полагаю, это следует из теоремы Майхилла-Нерода). Этот изоморфизм учитывает метки ребер и, конечно, классы узлов (начало, принятие, непринятие). Это делает это проще, чем изоморфизм немаркированных графов.

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

Редактировать: Следует учитывать и не относящиеся к дереву ребра, но их можно также канонически упорядочить по их меткам.

Answer 3

Если все, что вы можете сделать, это == или! =, То я думаю, что вы должны проверить каждого участника набора, прежде чем добавлять другого. Это медленно. (Изменить: я думаю, вы уже знаете это, учитывая название вашего вопроса, даже если вы продолжаете о функциях сравнения для прямого сравнения двух конечных автоматов.)

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

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

Answer 4

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

Как предложено в вопросе, чтобы лексически упорядочить два автомата, мне нужно рассмотреть две вещи. Два набора возможных первых токенов и два набора возможных хвостов. Хвосты могут быть представлены как конечные автоматы и могут быть получены из оригинальных автоматов.

Так что алгоритм сравнения рекурсивный - сравните голову, если у вас другой результат, если тот же самый, то рекурсивно сравните хвост.

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

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

Также оказалось, что эта статья актуальна, но, вероятно, только уводит меня так далеко. Обычные языки могут формировать группу с помощью оператора конкатенации, и левый смежный класс связан с заголовком: все, что я рассматривал.

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

Мне не нужно останавливаться на первом повторении пары автоматов. Я могу продолжать, пока не найду более легко обнаруживаемое повторение - такое, которое имеет некоторую структурную эквивалентность, а также логическую эквивалентность. До тех пор, пока мой алгоритм «извлекать хвост из автомата» вменяемый (и особенно если я минимизирую и выполняю другие очистки на каждом этапе), я не буду генерировать бесконечную последовательность эквивалентных, но отличающихся друг от друга пар автоматов во время сравнения. Единственными источниками вариаций в структуре являются исходные два автомата и алгоритм хвостовых автоматов, оба из которых конечны.

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

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

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

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