A Survey of Relevant Literature - The Unknown Component Problem: Theory and Applications - page 94

question whether a compositionally .U [ O/-convergent solution exists remains
open. In the latter case the authors propose to limit to l the number of internal
interactions; if, for a given l, the largest solution of the equation exists then it is
compositionally .U [ O/-convergent and also each of its reductions inherits this
property. Notice that in Sect. 3.4.3 we extended to regular languages the procedure
for determining the solution with a limited number of internal interactions.
A number of papers in process algebra [36, 55, 94, 107, 118] discuss the equation
A ˘ X C under various relations ,whereA and C are given processes.

5.2.2 Supervisory Control

In supervisory control a controller (or supervisor) restricts the behavior of a plant
by dynamically disabling some of the controllable events after the execution of each
event with the goal to match a desired behavior. An extended literature has been
developed since the seminal work by Ramadge and Wonham, studying control under
complete and partial observation, centralized and distributed control and also control
of non-terminating behaviors [76, 77, 101, 119].
Restricted solutions have been investigated too, e.g., in [78] the authors proposed
a method to derive the largest compositionally progressive solution over finite
automata. The method is based on splitting the states of the automaton of the
unrestricted solution, combining the new automaton with the context and then
deleting from the composed automaton the states that are not completely specified
(for at least an input there is no transition). The method is proposed for a general
supervisory control topology where the language of the specification C is the
restriction on the external alphabet of a subset of the language of the known
componentA. A generalization of these results for a more general topology has been
proposed in [21]. Restricted solutions to parallel equations over regular languages
are considered also in [76, 101]. In [76] the solution is called the minimally
restrictive supervisor, i.e., a supervisor that combined with the context matches
the largest specification sublanguage; in [101], a bound l is set on the number of
internal interactions. For updates on control of discrete event systems, including
fault tolerant control and Petri nets the reader may refer to [61, 64].
The computational complexity of the harder supervisory control problems
(verification and synthesis) varies from NP-hard/complete to (most often) PSPACE-
hard/complete (see [48,123,124]); some proofs use the reduction from the automata
intersection problem.

5.2.3 Simulation Relations

A procedure for deriving the largest solution for LTSs A and C of the equation
A ˘ X

bisim C was proposed in [118], where bisim denotes either a strong or