Тест двух деревьев выражения LTL для эквивалентности

Question

Есть ли алгоритм о том, как проверить, если два выражения LTL (представлены как двоичные деревья) семантически эквивалентны?Поскольку есть много меньших эквивалентных эквивалентных $ a \ prightarrow b \ equiv \ neg a \ vee b $ или $ f (a) \ equiv true u a $ а также коммутативность, распространение и т. Д., которые необходимо учитывать.
Моя первоначальная идея состояла в том, чтобы создать таблицу правды для обоих выражений и их сравнения.Но тогда временные операторы не будут приняты во внимание.Создание и сравнение автомата для каждого выражения звучит как это было бы довольно неэффективным.

Есть лучший способ сделать это?

Answer 1

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

Проблема проверки того, действует ли формула LTL, то есть, удовлетворена ли она в каждом вычислении, является полным вычислением PSPACE (это простое упражнение, учитывая, что удовлетворение LTL является PSPace Complete). Таким образом, проверка, проверяя ли два формула LTL эквивалентными, также, по меньшей мере, Pspace Hard, поскольку вы можете уменьшить от первого путем тестирования эквивалентности с формулой «True».

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