hio_functions.h

Go to the documentation of this file.

/** @file hio_functions.h Algorithms for hierarchical discrete event systems with inputs and outputs */
 
/* Hierarchical IO Systems Plug-In for FAU Discrete Event Systems Library (libfaudes)
 
   Copyright (C) 2006  Sebastian Perk 
   Copyright (C) 2006  Thomas Moor 
   Copyright (C) 2006  Klaus Schmidt
 
*/
 
 
#ifndef FAUDES_HIO_FUNCTIONS_H
#define FAUDES_HIO_FUNCTIONS_H
 
#include "hio_constraint.h"
#include "hio_plant.h"
#include "hio_controller.h"
#include "hio_environment.h"
#include "corefaudes.h"
#include <vector>
#include <stack>
#include <map>
 
namespace faudes {
 
/**
 * CompleteSynth: compute supremal complete and
 * controllable (and closed)  sublanguage.
 * Computes the supremal complete and
 * controllable (and closed)  sublanguage of the
 * language generated by rSpec wrt the language
 * generated by rPlant and the controllable events
 * rCalph.
 * Method: iteration of SupCon() and erasing of dead
 * states found by IsComplete until a fix point is
 * reached.
 * Leads to maximal solution as shown in:
 * Kumar, Garg, Marcus. "On Supervisory Control of
 * sequential behaviors" IEEE Transactions On
 * Automatic Control, Vol. 37, 1992, pp. 1978-1985
 * 
 * More concise version SupConComplete() is under
 * construction, see below.
 *
 * @param rPlant
 *   plant generator
 * @param rCAlph
 *   controllable events
 * @param rSpec
 *   specification generator
 * @param rClosedLoop
 *   reference to result
 * 
 * @return
 *   success (true) for nonempty result
 *
 * @exception Exception
 *   - see exceptions of SupCon()
 *
 * @ingroup hiosysplugin 
 */
 
extern FAUDES_API bool CompleteSynth(
  const Generator& rPlant,
  const EventSet rCAlph, 
  const Generator& rSpec, 
  Generator& rClosedLoop);
 
/**
 * NormalCompleteSynth: compute normal, complete
 * and controllable (and closed)  sublanguage.
 * Computes the supremal normal, complete and
 * controllable (and closed)  sublanguage  of the
 * language generated by rSpec wrt the language
 * generated by rPlant, the controllable events
 * rCalph and the observable events rOAlph.
 * Method: iteration of CompleteSynth() and SupNorm()
 * until a fix point is reached.
 * Note: Supremality (if existent at all) has not yet been
 * considered. The proof of existence and construction
 * of both
 * -the supremal normal and complete sublanguage and
 * -the supremal normal and controllable sublanguage
 * can be found in literature, which gives reason for
 * hope.
 *
 * @param rPlant
 *   plant generator
 * @param rCAlph
 *   controllable events
 * @param rOAlph
 *   observable events
 * @param rSpec
 *   specification generator
 * @param rClosedLoop
 *   reference to result
 * 
 * @return
 *   success (true) for nonempty closed loop language
 *
 * @exception Exception
 *   - see exceptions of SupCon() and SupNorm()
 * 
 * @ingroup hiosysplugin 
 *
 */
 
extern FAUDES_API bool NormalCompleteSynth(
  Generator& rPlant, 
  const EventSet& rCAlph, 
  const EventSet& rOAlph,
  const Generator& rSpec,
  Generator& rClosedLoop);
  
/**
 * NormalCompleteSynthNB: compute normal, complete,
 * controllable and nonblocking  sublanguage.
 * Computes a normal, complete, controllable and
 * nonblocking (and closed)  sublanguage  of 
 * of the language marked by rSpec wrt the language
 * marked by rPlant, the controllable events
 * rCalph and the observable events rOAlph.
 * Method: iteration of CompleteSynth(), SupNorm()
 * and Trim() until a fix point is reached.
 * Note: Supremality (if existent at all) has not yet been
 * considered. 
 *
 * @param rPlant
 *   plant generator
 * @param rCAlph
 *   controllable events
 * @param rOAlph
 *   observable events
 * @param rSpec
 *   specification generator
 * @param rClosedLoop
 *   reference to result
 * 
 * @return
 *   success (true) for nonempty closed loop language
 *
 * @exception Exception
 *   - see exceptions of SupCon() and SupNorm()
 * 
 * @ingroup hiosysplugin 
 *
 */
extern FAUDES_API bool NormalCompleteSynthNB(
  Generator& rPlant, 
  const EventSet& rCAlph, 
  const EventSet& rOAlph,
  const Generator& rSpec,
  Generator& rClosedLoop);
 
/**
 * IoSortCL: returns IO-sorting structure  required
 * for closed loops. This structure is the prefix closure of
 * the language structure [(Yp(Up+YcUcUp))*(YeUe)*]*
 *
 * @param rYc
 *   alphabet Yc
 * @param rUc
 *   alphabet Uc
 * @param rYp
 *   alphabet Yp
 * @param rUp
 *   alphabet Up
 * @param rYe
 *   alphabet Ye
 * @param rUe
 *   alphabet Ue
 * 
 * @return
 *   IO-sorting language generator
 *
 * @exception Exception
 *   - empty parameter(s) (id 0)
 *   - non-disjoint parameters (id 0)
 * 
 * @ingroup hiosysplugin 
 *
 */
 
extern FAUDES_API Generator HioSortCL(
  const EventSet& rYc, 
  const EventSet& rUc,
  const EventSet& rYp, 
  const EventSet& rUp,
  const EventSet& rYe,
  const EventSet& rUe);
 
/**
 * HioFreeInput:  extend generator by obviously missing
 * input transitions. States of the generator in which a
 * strict but nonempty subset of the alphabet Input is active
 * are extended by transitions to an error state (ErrState1,
 * flag Err) such that now the whole Input alphabet is active in
 * that state. If the alphabet Output is nonempty, an error
 * behaviour (Output Input)* is concatenated to the error state
 * using a second error state (ErrState2, flag Err).
 * Note that this method only helps making the input free in an
 * hio system but does not guarantee a free input.
 * Method: the transition relation of all states with at least
 * one active AND at least one inactive Input-event is
 * extended by transitions such that formerly inactive Input-
 * events lead to the first error state in the result.  If the
 * parameter Output is nonempty, transitions with all
 * Output-events from first error state to the second error
 * state, and transitions with all Input-events back to the
 * first error state are inserted.
 * Note: states with NO active Input-event are ignored.
 *
 * @param rGen
 *   generator
 * @param rInput
 *   alphabet Input
 * @param rOutput
 *   alphabet Output
 * @param rResGen
 *   reference to extended generator (result)
 * @param rErrState1
 *   symbolic name of first error state; ignored if not
 *   rGen.StateNamesEnabled()
 * @param rErrState2
 *   symbolic name of second error state; ignored if not
 *   rGen.StateNamesEnabled()
 * @param rErrState1Idx
 *   index of first error state (result)
 * @param rErrState2Idx
 *   index of second error state if inserted (result)
 *
 * @exception Exception
 *   - empty Input-alphabet or non-disjoint Input and Output (id 0)
 * 
 * @ingroup hiosysplugin 
 *
 */
 
extern FAUDES_API void HioFreeInput(
  const Generator& rGen, 
  const EventSet& rInput, 
  const EventSet& rOutput,
  Generator& rResGen,
  const std::string& rErrState1, 
  const std::string& rErrState2,
  Idx& rErrState1Idx,
  Idx& rErrState2Idx);
 
/**
 * HioFreeInput:  extend generator by obviously missing
 * input transitions. States of the generator in which a
 * strict but nonempty subset of the alphabet Input is active
 * are extended by transitions to an error state (ErrState1,
 * flag Err) such that now the whole Input alphabet is active in
 * that state. If the alphabet Output is nonempty, an error
 * behaviour (Output Input)* is concatenated to the error state
 * using a second error state (ErrState2, flag Err).
 * Note that this method only helps making the input free in an
 * hio system but does not guarantee a free input.
 * Method: the transition relation of all states with at least
 * one active AND at least one inactive Input-event is
 * extended by transitions such that formerly inactive Input-
 * events lead to the first error state in the result.  If the
 * parameter Output is nonempty, transitions with all
 * Output-events from first error state to the second error
 * state, and transitions with all Input-events back to the
 * first error state are inserted.
 * Note: states with NO active Input-event are ignored.
 *
 * @param rGen
 *   generator
 * @param rInput
 *   alphabet Input
 * @param rOutput
 *   alphabet Output
 * @param rResGen
 *   reference to extended generator (result)
 * @param rErrState1
 *   symbolic name of first error state; ignored if not
 *   rGen.StateNamesEnabled()
 * @param rErrState2
 *   symbolic name of second error state; ignored if not
 *   rGen.StateNamesEnabled()
 *
 * @exception Exception
 *   - empty Input-alphabet or non-disjoint Input and Output (id 0)
 * 
 * @ingroup hiosysplugin 
 *
 */
 
extern FAUDES_API void HioFreeInput(
  const Generator& rGen, 
  const EventSet& rInput, 
  const EventSet& rOutput,
  Generator& rResGen,
  const std::string& rErrState1, 
  const std::string& rErrState2);
 
/**
 * HioFreeInput:  extend generator by obviously missing
 * input transitions. States of the generator in which a
 * strict but nonempty subset of the alphabet Input is active
 * are extended by transitions to an error state (flag Err) 
 * such that now the whole Input alphabet is active in
 * that state. If the alphabet Output is nonempty, an error
 * behaviour (Output Input)* is concatenated to the error state
 * using a second error state (flag Err).
 * Note that this method only helps making the input free in an
 * hio system but does not guarantee a free input.
 * Method: the transition relation of all states with at least
 * one active AND at least one inactive Input-event is
 * extended by transitions such that formerly inactive Input-
 * events lead to the first error state in the result.  If the
 * parameter Output is nonempty, transitions with all
 * Output-events from first error state to the second error
 * state, and transitions with all Input-events back to the
 * first error state are inserted.
 * Note: states with NO active Input-event are ignored.
 *
 * @param rGen
 *   generator
 * @param rInput
 *   alphabet Input
 * @param rOutput
 *   alphabet Output
 * @param rResGen
 *   reference to extended generator (result)
 *
 * @exception Exception
 *   - empty Input-alphabet or non-disjoint Input and Output (id 0)
 * 
 * @ingroup hiosysplugin 
 *
 */
extern FAUDES_API void HioFreeInput(
  const Generator& rGen, 
  const EventSet& rInput, 
  const EventSet& rOutput,
  Generator& rResGen);
 
/**
 * HioFreeInput:  extend HioPlant by obviously missing
 * input transitions. States of the HioPlant in which a
 * strict but nonempty subset of the Up- or Ue-alphabet is active
 * are extended by transitions to an error state such that
 * now the whole Up- or Ue-alphabet is active in that state.
 * Note that this method only helps making the input free in an
 * hio system but does not guarantee a free input.
 * Method: the transition relation of all states with at least
 * one active AND at least one inactive Up- or Ue-event is
 * extended by transitions such that formerly inactive Up- or Ue-
 * events lead to the Up- or Ue-error state in the result. 
 * Note: states with NO active Up- or Ue-event are ignored.
 *
 * @param rPlant
 *   HioPlant
 * @param rResPlant
 *   reference to extended HioPlant (result)
 * 
 * @ingroup hiosysplugin 
 *
 */  
extern FAUDES_API void HioFreeInput(
  const HioPlant& rPlant,
  HioPlant& rResPlant);
 
/**
 * HioFreeInput:  extend HioController by obviously missing
 * input transitions. States of the HioController in which a
 * strict but nonempty subset of the Uc- or Yp-alphabet is active
 * are extended by transitions to an error state such that
 * now the whole Uc- or Yp-alphabet is active in that state. To
 * avoid an additional deadlock violating completeness, an error
 * behaviour (Up Yp)* is concatenated to the error state
 * using a second error state.
 * Note that this method only helps making the input free in an
 * hio system but does not guarantee a free input.
 * Method: the transition relation of all states with at least
 * one active AND at least one inactive Uc- or Yp-event is
 * events lead to the Uc- or Yp-error state in the result.
 * For each Up-event, a transition to a second error state, and
 * for each Yp-event, a transition from the second to the first
 * error state is inserted to realise the error behaviour.
 * Note: states with NO active Uc- or Yp-event are ignored.
 *
 * @param rController
 *   HioController
 * @param rResController
 *   reference to extended HioController (result)
 * 
 * @ingroup hiosysplugin 
 *
 */    
extern FAUDES_API void HioFreeInput(
  const HioController& rController,
  HioController& rResController);
  
/**
 * HioFreeInput:  extend HioEnvironment by obviously missing
 * input transitions. States of the HioEnvironment in which a
 * strict but nonempty subset of the Ul- or Ye-alphabet is active
 * are extended by transitions to an error state such that
 * now the whole Ul- or Ye-alphabet is active in that state.To
 * avoid an additional deadlock violating completeness, an error
 * behaviour (Ue Ye)* is concatenated to the error state
 * using a second error state.
 * Note that this method only helps making the input free in an
 * hio system but does not guarantee a free input.
 * Method: the transition relation of all states with at least
 * one active AND at least one inactive Ul- or Ye-event is
 * events lead to the Ul- or Ye-error state in the result. 
 * For each Ue-event, a transition to a second error state, and
 * for each Ye-event, a transition from the second to the first
 * error state is inserted to realise the error behaviour.
 * Note: states with NO active Ul- or Ye-event are ignored.
 *
 * @param rEnvironment
 *   HioEnvironment
 * @param rResEnvironment
 *   reference to extended HioEnvironment (result)
 * 
 * @ingroup hiosysplugin 
 *
 */     
extern FAUDES_API void HioFreeInput(
  const HioEnvironment& rEnvironment,
  HioEnvironment& rResEnvironment);
 
/**
 * HioFreeInput:  extend HioConstraint by obviously missing
 * input transitions. States of the HioConstraint in which a
 * strict but nonempty subset of the U-alphabet is active
 * are extended by transitions to an error state such that
 * now the whole U-alphabet is active in that state.To
 * avoid an additional deadlock violating completeness, an error
 * behaviour (U Y)* is concatenated to the error state
 * using a second error state.
 * Note that this method only helps making the input free in an
 * hio system but does not guarantee a free input.
 * Method: the transition relation of all states with at least
 * one active AND at least one inactive U-event is
 * events lead to the U-error state in the result. 
 * For each U-event, a transition to a second error state, and
 * for each Y-event, a transition from the second to the first
 * error state is inserted to realise the error behaviour.
 * Note: states with NO active U-event are ignored.
 *
 * @param rConstraint
 *   HioConstraint
 * @param rResConstraint
 *   reference to extended HioConstraint (result)
 * 
 * @ingroup hiosysplugin 
 *
 */   
extern FAUDES_API void HioFreeInput(
  const HioConstraint& rConstraint,
  HioConstraint& rResConstraint);
 
/**
 * HioFreeInput:  convenience interface to faudes::HioFreeInput(const HioPlant&, HioPlant)
 *
 * @param rPlant
 *   HioPlant
 * @ingroup hiosysplugin 
 *
 */  
extern FAUDES_API void HioFreeInput(HioPlant& rPlant);
 
/**
 * HioFreeInput:  convenience interface to faudes::HioFreeInput(const HioController&, HioController)
 *
 * @param rController
 *   HioController
 * @ingroup hiosysplugin 
 *
 */  
extern FAUDES_API void HioFreeInput(HioController& rController);
 
/**
 * HioFreeInput:  convenience interface to faudes::HioFreeInput(const HioEnvironment&, HioEnvironment)
 *
 * @param rEnvironment
 *   HioEnvironment
 * @ingroup hiosysplugin 
 *
 */  
extern FAUDES_API void HioFreeInput(HioEnvironment& rEnvironment);
 
/**
 * HioFreeInput:  convenience interface to faudes::HioFreeInput(const HioConstraint&, HioConstraint)
 *
 * @param rConstraint
 *   HioConstraint
 * @ingroup hiosysplugin 
 *
 */  
extern FAUDES_API void HioFreeInput(HioConstraint& rConstraint);
 
 
//**********************************************************
//******************** IO-shuffle ************************
//**********************************************************
 
/**
 * MarkHioShuffle: marking rule for HioShuffle()  in case of
 * marked parameters rGen1 and rGen2 - UNDER CONSTRUCTION.
 *
 * Method:
 * Strings ending with events from rGen1 are marked according
 * to rGen1,  strings ending with  events from rGen2 are marked
 * according to rGen2.
 *
 * @param rGen1
 *   First generator
 * @param rGen2
 *   Second generator
 * @param rReverseCompositionMap
 *   map from rGen1 and rGen2 state indeces to respective
 *   state indeces of result
 * @param rShuffle
 *   Shuffle  of rGen1 and rGen2 that shall receive marking
 *
 * @ingroup hiosysplugin
 *
 */
extern FAUDES_API void MarkHioShuffle(
  const Generator& rGen1,
  const Generator& rGen2,
    const std::map< std::pair<Idx,Idx>, Idx >& rReverseCompositionMap,
  Generator& rShuffle);
 
/**
 * CheapAltAnB: returns Generator of the following
 * specification: "After a maximum of n (=depth) pairs of
 * A-transitions, a B-transition has to occur!".
 *
 * @param rAset
 *   alphabet A
 * @param rBset
 *   alphabet B
 * @param Depth
 *   depth of alternation
 * @param rAltAnB
 *   generator of AnB-specification
 *
 * @exception Exception
 *   - n less than 1 (id 0)
 *   - rAset empty (id 0)
 *   - rBset empty (id 0)
 * 
 * @ingroup hiosysplugin 
 *
 */
extern FAUDES_API void CheapAltAnB(
  const EventSet rAset, 
  const EventSet rBset,
  const int Depth,
  Generator& rAltAnB);
 
/**
 * CheapAltAB: returns Generator of the following
 * specification: "After a maximum of n (=depth) pairs of
 * A-transitions, a B-transition has to occur and vice-versa!".
 *
 * @param rAset
 *   alphabet A
 * @param rBset
 *   alphabet B
 * @param Depth
 *   depth of alternation
 * @param rAltAB
 *   generator of AB-specification
 *
 * @exception Exception
 *   - n less than 1 (id 0)
 *   - rAset empty (id 0)
 *   - rBset empty (id 0)
 * 
 * @ingroup hiosysplugin 
 *
 */
extern FAUDES_API void CheapAltAB(
  const EventSet rAset, 
  const EventSet rBset,  
  const int Depth,
  Generator& rAltAB);
  
/**
 * MarkAlternationAB: returns Generator marking the
 * alternation of Aset-transitions with Bset-transitions.
 * More docu will be provided soon.
 *
 * @param rAset
 *   alphabet A
 * @param rBset
 *   alphabet B
 * @param rAltAB
 *   recognizer of AB-alternation
 *
 * @exception Exception
 *   - rAset empty (id 0)
 *   - rBset empty (id 0)
 * 
 * @ingroup hiosysplugin 
 *
 */
extern FAUDES_API void MarkAlternationAB(
  const EventSet rAset, 
  const EventSet rBset,
  Generator& rAltAB);
 
/**
 * HioShuffleUnchecked:  IO-shuffle of rPlantA and rPlantB
 * according to definition, no parameter check. Moreover: marking
 * of alternation according to MarkAlternationAB().
 * 
 * TODO: 'checked' version
 *
 * @param rPlantA
 *   plant A generator
 * @param rPlantB
 *   plant B generator
 * @param rYp
 *   alphabet Yp
 * @param rUp
 *   alphabet Up
 * @param rYe
 *   alphabet Ye
 * @param rUe
 *   alphabet Ue
  * @param rIOShuffAB
 *   reference to I/O-shuffle generator
 * 
 * @ingroup hiosysplugin 
 *
 */
extern FAUDES_API void HioShuffleUnchecked(
  const Generator& rPlantA, 
  const Generator& rPlantB, 
  const EventSet& rYp,
  const EventSet& rUp, 
  const EventSet& rYe, 
  const EventSet& rUe,
  Generator& rIOShuffAB);
 
/**
 * HioShuffle:  IO-shuffle of rPlantA and rPlantB according
 * to definition. Moreover: marking of alternation
 * according to MarkAlternationAB().
 * 
 *
 * @param rPlantA
 *   plant A generator
 * @param rPlantB
 *   plant B generator
 * @param rYp
 *   alphabet Yp
 * @param rUp
 *   alphabet Up
 * @param rYe
 *   alphabet Ye
 * @param rUe
 *   alphabet Ue
  * @param rIOShuffAB
 *   reference to I/O-shuffle generator
 *
 * @exception Exception
 *   - empty or non-disjoint alphabets rYp, rUp, rYe, rUe (id 0). 
 *   - plant A or plant B not in HioPlantForm (id 0). 
 * 
 * @ingroup hiosysplugin 
 *
 */
extern FAUDES_API void HioShuffle(
  const Generator& rPlantA, 
  const Generator& rPlantB, 
  const EventSet& rYp,
  const EventSet& rUp, 
  const EventSet& rYe, 
  const EventSet& rUe,
  Generator& rIOShuffAB);
  
/**
 * HioShuffle:  IO-shuffle of rPlantA and rPlantB according
 * to definition. Moreover: alternation of depth
 * Depth (see CheapAltAB()) between A- and B-events (no
 * alternation for Depth=1) and marking of alternation
 * according to MarkAlternationAB().
 *
 * @param rPlantA
 *   HioPlant A
 * @param rPlantB
 *   HioPlant B
  * @param rIOShuffAB
 *   reference to composed HioPlant
 *
 * @exception Exception
 *   - todo...
 * 
 * @ingroup hiosysplugin 
 *
 */  
extern FAUDES_API void HioShuffle(
  const HioPlant& rPlantA, 
  const HioPlant& rPlantB,
  HioPlant& rIOShuffAB);
 
//******************** old version: no marking, forced alternation ************************
/**
 * HioShuffleTU:  IO-shuffle of rPlantA and rPlantB according
 * to definition with additional forced alternation of depth
 * Depth (see CheapAltAB()) between A- and B-events.
 * -> frozen version for transport unit example
 *
 * @param rPlantA
 *   plant A generator
 * @param rPlantB
 *   plant B generator
 * @param rYp
 *   alphabet Yp
 * @param rUp
 *   alphabet Up
 * @param rYe
 *   alphabet Ye
 * @param rUe
 *   alphabet Ue
 * @param Depth
 *   depth of alternation
   * @param rIOShuffAB
 *   reference to I/O-shuffle generator
 *
 * @exception Exception
 *   - todo...
 * 
 * @ingroup hiosysplugin 
 *
 */
extern FAUDES_API void HioShuffleTU(
  const Generator& rPlantA, 
  const Generator& rPlantB, 
  const EventSet& rYp,
  const EventSet& rUp, 
  const EventSet& rYe, 
  const EventSet& rUe,
  const int Depth,
  Generator& rIOShuffAB);
 
//**********************************************************
//******************** Cycles ************************
//**********************************************************
 
/**
 * SearchYclessSCC: Search for strongly connected ycless
 * components (YC-less SCC's). This function partitions the
 * stateset of a generator into equivalent classes such that
 * states x1 and x2 are equivalent iff there is a ycless
 * path from x1 to x2 and a ycless path from x2 to x1.
 * "Trivial" SCC's consisting of one state without non-Yc-
 * selfloop are omitted, SCC's consisting exclusively of
 * unmarked states are stored in rUnMarkedSccSet; all OTHER
 * SCC's are collected in rSccSet. Their roots (i.e. that
 * state of each SCC that has been visited first during depth
 * first search of the generator) are collected in rRoots.
 * This function is built on the algorithm based on a depth
 * first search presented in:
 * "Aho, Hopcroft, Ullman:
 * The Design and Analysis of Computer Algorithms"
 * Most of the comments in this function have been literally
 * taken from this book!
 * An api with generator and Yc-events as input parameters
 * and the set of YC-less SCC's as output parameters is
 * provided right below this method.
 *
 * @param state
 *   State, from which the current recursion is started.
 * @param rcount
 *   Denotes the current depth of the recursion.
 * @param rGen
 *   investigated generator
 * @param rYc
 *   alphabet Yc
 * @param UnMarkedOnly
 *   if set true, being unmarked is an additional condition for equivalence of states
 * @param rNewStates
 *   Set of states that up to now were not found by the
 *   depth first search.
 * @param rSTACK
 *   Stack of state indeces.
 * @param rStackStates
 *   Set of states whose indeces are on STACK.
 * @param rDFN
 *   Map assigning to each state idx its Depth-First Number.
 * @param rLOWLINK
 *   Map assigning to each state its LOWLINK Number.
 * @param rSccSet
 *   Set of YC-less strongly connected components (result).
 * @param rRoots
 *   Set of states that each are root of some SCC (result).
 *
 * @exception Exception
 *   - todo...
 * 
 * @ingroup hiosysplugin 
 * 
 */
extern FAUDES_API void SearchYclessScc(
  const Idx state, 
  int& rcount,      // why is this a ref?
  const Generator& rGen,
  const EventSet& rYc,
  const bool UnMarkedOnly,
  StateSet&  rNewStates,
  std::stack<Idx>& rSTACK, 
  StateSet& rStackStates,
  std::map<const Idx, int>& rDFN,
  std::map<const Idx, int>& rLOWLINK,
  std::set<StateSet>& rSccSet,
  StateSet& rRoots);
 
/**
 * YclessSCC: Search for strongly connected ycless
 * components (YC-less SCC's) - convenience api. See
 * SearchYclessSCC() for docu.
 * 
 * @param rGen
 *   investigated generator
 * @param rYc
 *   alphabet Yc
 * @param rSccSet
 *   Set of YC-less strongly connected components (result).
 * @param rRoots
 *   Set of states that each are root of some SCC (result).
 *
 * @return
 *   true if YclessSCC's have been found, false if not.
 *
 * @exception Exception
 *   - todo...
 * 
 * @ingroup hiosysplugin 
 *
 */
extern FAUDES_API bool YclessScc(
  const Generator& rGen,
  const EventSet& rYc,
  std::set<StateSet>& rSccSet,
  StateSet& rRoots);
  
 
/**
 * YclessUnmarkedSCC: Search for strongly connected ycless
 * components (YC-less SCC's) consisting of unmarked states only.
 * Uses SearchYclessSCC().
 * 
 * @param rGen
 *   investigated generator
 * @param rYc
 *   alphabet Yc
 * @param rSccSet
 *   Set of unmarked YC-less strongly connected components (result).
 * @param rRoots
 *   Set of states that each are root of some SCC (result).
 *
 * @return
 *   true if unmarked YclessSCC's have been found, false if not.
 *
 * @exception Exception
 *   - todo...
 * 
 * @ingroup hiosysplugin 
 *
 */
extern FAUDES_API bool YclessUnmarkedScc(
  const Generator& rGen,
  const EventSet& rYc,
  std::set<StateSet>& rSccSet,
  StateSet& rRoots);
 
/**
 * YclessSCC: Search for strongly connected ycless
 * components (YC-less SCC's) - convenience api. See
 * SearchYclessSCC() for docu.
 * 
 * @param rGen
 *   investigated generator
 * @param rYc
 *   alphabet Yc
 * @param rSccSet
 *   Set of YC-less strongly connected components (result).
 *
 * @return
 *   true if YclessSCC's have been found, false if not.
 *
 * @exception Exception
 *   - todo...
 * 
 * @ingroup hiosysplugin 
 *
 */
extern FAUDES_API bool YclessSCC(
  const Generator& rGen,
  const EventSet& rYc,
  std::set<StateSet>& rSccSet);
 
/**
 * IsYcLive: This function checks if generator is Yc-live.
 * Method: using YclessSCC(), the function checks if no Yc-less
 * SCC is found.
 * 
 * @param rGen
 *   investigated generator
 * @param rYc
 *   alphabet Yc
 *
 * @return
 *   true if Generator is YcLive.
 *
 * @exception Exception
 *   - todo...
 * 
 * @ingroup hiosysplugin 
 *
 */
extern FAUDES_API bool IsYcLive(
  const Generator& rGen,
  const EventSet& rYc);
  
/**
 * WriteStateSets: Write set of StateSet's to console (indeces).
 * Useful to output partitions over statesets like e.g. the
 * set of strongly connected components. Also serves as
 * template for walkthrough through each state of a set of
 * statesets.
 * 
 * @param rStateSets
 *   Reference to set of StateSets (result).
 *
 * @exception Exception
 *   - todo?
 * 
 * @ingroup hiosysplugin 
 *
 */
extern FAUDES_API void WriteStateSets(
  const std::set<StateSet>& rStateSets);
  
/**
 * WriteStateSets: Write set of StateSet's to console (symbolic
 * state names taken from rGen).
 * Useful to output partitions over statesets like e.g. the
 * set of strongly connected components. Also serves as
 * template for walkthrough through each state of a set of
 * statesets.
 *
 * @param rGen
 *   Generator holding symbolic state names.
 * @param rStateSets
 *   Reference to set of StateSets (result).
 *
 * @exception Exception
 *   - todo?
 * 
 * @ingroup hiosysplugin 
 *
 */  
extern FAUDES_API void WriteStateSets(
  const Generator& rGen,
  const std::set<StateSet>& rStateSets);
 
/**
 * SCCEntries: figure entry states and entry transitions of
 * strongly connected components rSccSet of rGen. Entry
 * states are the set of states of the SCC that are initial
 * state or direct successor of some state not belonging to
 * this SCC (i.e. belonging to a different or no SCC). Entry
 * transitions are the set of respective transitions leading
 * to an entrystate of some SCC from a state not belonging
 * to this SCC.
 * 
 * @param rGen
 *   generator holding SCC's of rSccSet
 * @param rSccSet
 *   generator holding SCC's of rSccSet
 * @param rEntryStates
 *   reference to set of entry states of all SCC's (result)
 * @param rEntryTransSet
 *   reference to set of entry transitions, sorted by X2
 *   (result)
 *
 * @exception Exception
 *   - todo: if FAUDES_CHECKED: check if elements of rSccSet
 *   are all subsets of StateSet of rGen.
 * 
 * @ingroup hiosysplugin 
 *
 */
extern FAUDES_API void SccEntries(
  const Generator& rGen,
  const std::set<StateSet>& rSccSet,
  StateSet& rEntryStates,
  TransSetX2EvX1& rEntryTransSet);
 
/**
 * cloneSCC: makes a copy (clone) of strongly connected
 * component (rSCC) of the generator and moves all
 * transitions leading to some entry state EntryState of
 * this SCC to the copy of EntryState. If this is carried
 * out for n-1 of all n entry states of the SCC, then, in
 * the generator, this one SCC is transformed into n SCC's
 * with one unique entry state each.
 * The set of SCC's is extended by the clone-SCC. The set of
 * entry states is extended by the (unique) entry state of
 * the clone-SCC.
 * Note: all added states are equivalent to some state in
 * the original generator, the behaviour is not changed.
 * The basic idea of this algorithm id taken from
 * [Jéron,Marchand,Rusu,Tschaen] "Ensuring the conformance
 * of reactive discrete-event systems using supervisory
 * control" (CDC'03)
 * todo: check const parameters
 * 
 * @param rGen
 *   generator holding SCC's of rSccSet
 * @param rScc
 *   SCC of rGen that is to be cloned // Perk: check if idx of rSccSet is better?
 * @param rSccSet
 *   set of all SCC's of rGen
 * @param EntryState
 *   one of the entry states of this SCC
 * @param rEntryStates
 *   set of entry states of this SCC
 * @param rEntryTransSet
 *   set of respective transitions to the entry states,
 *   sorted by X2
 *
 * @exception Exception
 *   - todo: exceptions, e.g. for rEntryState not subset of
 *   rEntryStates not subset of rScc not element of rSccSet,
 *   elements of rSccSet not subset of rGen.States() etc.
 * 
 * @ingroup hiosysplugin  
 *
 */
 
extern FAUDES_API void CloneScc(
  Generator& rGen,
  const StateSet& rScc,
  std::set<StateSet>& rSccSet,
  const Idx EntryState,
  StateSet& rEntryStates, 
  TransSetX2EvX1& rEntryTransSet);
 
/**
 * CloneUnMarkedSCC: makes a copy (clone) of strongly connected
 * unmarked component (rSCC)  of rGen.
 * 
 * @ingroup hiosysplugin 
*/
 
extern FAUDES_API void CloneUnMarkedScc(
  Generator& rGen,
  const StateSet& rScc,
  const Idx EntryState,
  const StateSet& rEntryStates, 
  TransSetX2EvX1& rEntryTransSet);
 
/**
 * YcAcyclic: Computes the supremal(?) Yc-acyclic
 * sublanguage of L(Gen). Procedure:
 * 1) Find Yc-less SCC's with YclessScc(...)
 * 2) transform SCC's with n entry states to n SCC's with
 * one unique entry state.
 * 3) erase transitions leading from a state of some SCC to
 * the entry state of this SCC's.
 * 4) repeat 1)-3) until no more Yc-less SCC is found, i.e.
 * rResGen generates the supremal YcAcyclic sublanguage of
 * the language generated by rGen.
 *
 * @param rGen
 *   input generator
 * @param rYc
 *   alphabet Yc
 * @param rResGen
 *   generator of supremal YcAcyclic sublanguage
 *
 * @exception Exception
 *   - todo: rYc must be subset of rGen.Alphabet()
 * 
 * @ingroup hiosysplugin 
 *
*/
extern FAUDES_API void YcAcyclic(
  const Generator& rGen,
  const EventSet& rYc,
  Generator& rResGen);
 
//**********************************************************
//******************** hio synthesis ************************
//**********************************************************
  
/**
 * ConstrSynth_Beta: compute operator constraint Sp for plant under
 * environment constraint Sl such that plant is complete & Yp-live wrt
* both constraints - Beta Version. Plant can be individual or
 * composed, ie Plant=Lpe || Le, or Plant=Lpe1 ||io Lpe2 || Lel || Ll,
 * ie composition of plant and envconstr, or composition of HioShuffle
 * of two plants with environment and envconstr.
 * Parameter rLocConstr is optional and may contain environment
 * constraints for Lpe1 and Lpe2; rOpConstraint is computed such that
 * rLocConstr is met under rOpConstraint.
 * More and better docu will follow in future version.
 * 
 * @param rPlant
 *   model of plant under environment constraint. 
 * @param rYp
 *   alphabet YP
 * @param rUp
 *   alphabet UP
 * @param rLocConstr
 *   reference to optional local constraints
 * @param rOpConstraint
 *   reference to operator constraint
 * 
 * @ingroup hiosysplugin 
 * 
*/
extern FAUDES_API void ConstrSynth_Beta(
        Generator& rPlant,
  const EventSet& rYp,
  const EventSet& rUp,
  const Generator& rLocConstr,
  Generator& rOpConstraint);
 
/**
 * HioSynthUnchecked: I/O controller synthesis procedure, no
 * parameter check. Main hio synthesis algorithm suitable for both
 * the monolithic and the hierarchical case, see also respective api's
 * HioSynth(with parameter check), HioSynthMonolithic and
 * HioSynthHierarchical. The result rController realises a solution to
 * the I/O controller synthesis problem (S_PE,S_C,S_P,S_E,S_SpecCE).
 * 
 * @param rPlant
 *   plant model generator:
 *   - monolithic case: I/O plant to be controlled;
 *   - hierarchical case: parallel composition of group
 * (I/O-shuffle) of n I/O   plants S_PEi (or their
 * abstractions) with the environment model S_EL for 
 * this group.
 * @param rSpec
 *   generator of desired behaviour of the external closed
 *   loop over alphabet SigmaCE. Must be in I/O plant form.
 * @param rConstr
 *   external constraint that may be assumed:
 *   - monolithic case: composition of constraints S_C and
 *   S_E
 *   - hierarchical case: composition of constraints S_C and
 *   S_L
 * @param rLocConstr
 *   internal constraint that has to be achieved by the I/O
 *   controller for the closed loop:
 *   - monolithic case: generator of constraint S_P
 *   - hierarchical case: parallel composition of
 *     constraints S_Pi   and S_Ei
 * @param rYc
 *   alphabet YC
 * @param rUc
 *   alphabet UC
 * @param rYp
 *   alphabet YP
 * @param rUp
 *   alphabet UP
 * @param rYel
 *   monolithic: alphabet YE, hierarchical: alphabet YL
 * @param rUel
 *   monolithic: alphabet UE, hierarchical: alphabet UL
 * @param rController
 *   reference to I/O controller(result)
 * 
 * @ingroup hiosysplugin 
 * 
*/
extern FAUDES_API void HioSynthUnchecked(
  const Generator& rPlant,
  const Generator& rSpec,
  const Generator& rConstr,
  const Generator& rLocConstr,
  const EventSet& rYc,
  const EventSet& rUc, 
  const EventSet& rYp,
  const EventSet& rUp, 
  const EventSet& rYel,
  const EventSet& rUel,
  Generator& rController);
  
/**
 * HioSynthUnchecked: I/O controller synthesis procedure.
 * Main hio synthesis algorithm suitable for both
 * the monolithic and the hierarchical case, see also respective api's
 * HioSynthMonolithic and HioSynthHierarchical.
 * The result rController realises a solution to the I/O controller
 *  synthesis problem (S_PE,S_C,S_P,S_E,S_SpecCE).
 * 
 * @param rPlant
 *   plant model generator:
 *   - monolithic case: I/O plant to be controlled;
 *   - hierarchical case: parallel composition of group
 * (I/O-shuffle) of n I/O   plants S_PEi (or their
 * abstractions) with the environment model S_EL for 
 * this group.
 * @param rSpec
 *   generator of desired behaviour of the external closed
 *   loop. Must be in I/O plant form.
 * @param rConstr
 *   external constraint that may be assumed:
 *   - monolithic case: composition of constraints S_C and
 *   S_E
 *   - hierarchical case: composition of constraints S_C and
 *   S_L
 * @param rLocConstr
 *   internal constraint that has to be achieved by the I/O
 *   controller for the closed loop:
 *   - monolithic case: generator of constraint S_P
 *   - hierarchical case: parallel composition of
 *     constraints S_Pi   and S_Ei
 * @param rYc
 *   alphabet YC
 * @param rUc
 *   alphabet UC
 * @param rYp
 *   alphabet YP
 * @param rUp
 *   alphabet UP
 * @param rYel
 *   monolithic: alphabet YE, hierarchical: alphabet YL
 * @param rUel
 *   monolithic: alphabet UE, hierarchical: alphabet UL
 * @param rController
 *   reference to I/O controller(result)
 *
 * @exception Exception
 *   - empty or non-disjoint alphabets rYc, rUc, rYp, rUp, rYel, rUel (id 0). 
 *   - rSpec not in HioPlantForm (id 0). 
 *   - alphabet mismatch between plant or constraints and spec (id 0). 
 * 
 * @ingroup hiosysplugin 
 * 
*/
extern FAUDES_API void HioSynth(
  const Generator& rPlant,
  const Generator& rSpec,
  const Generator& rConstr,
  const Generator& rLocConstr,
  const EventSet& rYc,
  const EventSet& rUc, 
  const EventSet& rYp,
  const EventSet& rUp, 
  const EventSet& rYel,
  const EventSet& rUel,
  Generator& rController);
  
/**
 * HioSynthMonolithic: I/O controller synthesis procedure for
 * monolithic plant. The result rController realises a solution to
 * the I/O controller synthesis problem (S_PE,S_C,S_P,S_E,S_SpecCE).
 * 
 * @param rPlant
 *   I/O plant to be controlled; must be in I/O plant form (tested if
 *   FAUDES_CHECKED); must be complete and Yp-live wrt. Sp and
 *   Se (not tested).
 * @param rSpec
 *   I/O plant model of desired behaviour of the external closed
 *   loop. Must be in I/O plant form (tested if FAUDES_CHECKED);
 *    must be complete and Yp-live wrt. Sc and Se (not tested).
 * @param rSc
 *   external operator constraint that may be assumed; I/O constraint form
 *   is recommended.
 * @param rSp
 *   operator constraint for rPlant; is met by admissibility of rController;
 *   I/O constraint form  is recommended.
 * @param rSe
 *   environment constraint that may be assumed; I/O constraint form
 *   is recommended.
 * @param rController
 *   I/O controller solving the I/O controller synthesis problem (result)
 * 
 * @exception Exception
 *   - plant or spec not in HioPlantForm (id 0). 
 *   - alphabet mismatch between plant or constraints and spec (id 0). 
 *
 * @ingroup hiosysplugin 
 * 
*/
extern FAUDES_API void HioSynthMonolithic(
  const HioPlant& rPlant,
  const HioPlant& rSpec,
  const HioConstraint& rSc,
  const HioConstraint& rSp,
  const HioConstraint& rSe,
  HioController& rController);
  
/**
 * HioSynthHierarchical: I/O controller synthesis procedure for
 * I/O-shuffle of i plants and their interaction via an I/O environment.
 * The result rController realises a solution to the I/O controller
 *  synthesis problem (S_PE,S_C,S_P,S_E,S_SpecCE) with the external
 *  behaviour S_PE of the I/Oshuffle-environment-composition and respects
 *  internal constraints Sp_i and Se_i preserving liveness of the
 * individual plants.
 * 
 * @param rHioShuffle
 *   I/O plant or group of I/O plants composed by I/O shuffle
 * @param rEnvironment
 *   environment model for rHioShuffle
 * @param rSpec
 *   I/O plant model of desired behaviour of the external closed
 *   loop. Must be in I/O plant form (tested if FAUDES_CHECKED);
 *    must be complete and Yp-live wrt. Sc and Se (not tested).
 * @param rIntConstr
 *   parallel composition of constraints Sp_i and Se_i of the
 *   individual plants composed to rHioShuffle
 * @param rSc
 *   external operator constraint that may be assumed; I/O constraint form
 *   is recommended.
 * @param rSl
 *   environment constraint that may be assumed; I/O constraint form
 *   is recommended.
 * @param rController
 *   I/O controller solving the I/O controller synthesis problem (result)
 * 
 * @exception Exception
 *   - HioShuffle or spec not in HioPlantForm (id 0). 
 *   - Environment not in HioEnvironmentForm (id 0). 
 *   - alphabet mismatch between plant, environment, spec and constraints (id 0). 
 *
 * @ingroup hiosysplugin 
 * 
*/
extern FAUDES_API void HioSynthHierarchical(
  const HioPlant& rHioShuffle,
  const HioEnvironment& rEnvironment,
  const HioPlant& rSpec,
  const Generator& rIntConstr,
  const HioConstraint& rSc,
  const HioConstraint& rSl,
  HioController& rController);
  
//#####################################
// #### end of hio_functions - below just archive ########
//#####################################
 
//HioShuffle_Musunoi() - special version for HioModule. Will be changed to std HioShuffle.
void HioShuffle_Musunoi(
  const HioPlant& rPlantA, 
  const HioPlant& rPlantB, 
  int depth, 
  Generator& rIOShuffAB) ;
 
//HioSynth_Musunoi() - special version for HioModule. Will be changed to std HioSynth.
void HioSynth_Musunoi(
  const Generator& rPlant,
  const HioPlant& rSpec,
  const Generator& rConstr,
  const Generator& rLocConstr,
  const EventSet& rYp,
  const EventSet& rUp, 
  Generator& rController);
}
 
 
#endif