Скелетные автоматы | Прикладная дискретная математика. 2011. № 2(12).

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