PSPACE-полнота задачи проверки частичных автоматов на бережную синхронизируемость

Abstract

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

We introduce the notion of a carefully synchronizing partial automaton as a natural generalization of the concept of a synchronizing complete automaton. We prove that the problem of checking whether or not a given partial automaton is carefully synchronizing is PSPACEcomplete even for automata with two input letters.