Supremal Controllable Sublanguage Computation

摘要

The aim of this paper is to review some algorithms to compute the supremal controllable sublanguage of a language K w.r.t. a language L. We focus on the case of a closed language. It is known that in this case the algorithm of Kumar et al. has an O(mn) time complexity, where n (resp. m) is the number of states of an automaton recognizing L (resp. K). A variant of Ramadge and Wonham algorithm with the same complexity is presented. Moreover, the direct method due to Brandt et al. has an O(m~2n) time complexity. An automata-theoretic approach yielding an O(mn) time complexity is described.