Computation of the Supremal Controllable Sublanguage Using an Augmented Language

This paper introduces a concept of an augmented language of a control specification in discrete-event systems. This language is at least legal in the sense that a plant can not generate illegal strings. We investigate its properties related to controllability of a control specification, and propose an algorithm for computation of the supremal controllable sublanguage, which is based upon an augmented language and a mapping over a family of languages. We show criteria of its finite convergence, which does not require that both a plant and a control specification are described by regular languages, but that the augmented language is regular and “enough large”. We also propose an algorithm based upon an automaton which generates an augmented language in the case that a control specification is closed, and show that its complexity is polynomial.