不确定带权有限状态机的最小化问题

摘要

本文提出一个不完全确定带权有限状态机的状态最小化问题：找一个状态间权值最小的机器覆盖确定机。在详细讨论了与这一问题解决有关的概念基础上，借助于ｂｉｎａｔｅ覆盖问题，给出了它的两个分枝限界算法。