Complexity of Infimal Observable Superlanguages

From International Center for Computational Logic

Toggle side column

Complexity of Infimal Observable Superlanguages

Tomáš MasopustTomáš Masopust
Complexity of Infimal Observable Superlanguages


Tomáš Masopust
Complexity of Infimal Observable Superlanguages
IEEE Transactions on Automatic Control, 63(1):249-254, 2018
  • KurzfassungAbstract
    The infimal prefix-closed, controllable and observable superlanguage plays an essential role in the relationshis between controllability, observability and co-observability -- the central notions of supervisory control. Existing algorithms for its computation are exponential and it is not known if a polynomial algorithm exists. We answer the question by studying the state complexity of this language. State complexity of a language is the number of states of its minimal DFA. For a language with state complexity n, we show that the upper-bound state complexity on the infimal prefix-closed and observable superlanguage is 2^n + 1 and that this bound is asymptotically tight. Hence there is no algorithm computing a DFA of the infimal prefix-closed and observable superlanguage in polynomial time. Our construction shows that such a DFA can be computed in time O(2^n). The construction involves NFAs and a computation of the supremal prefix-closed sublanguage. We study the computation of supremal prefix-closed sublanguages and show that there is no polynomial-time algorithm computing an NFA of the supremal prefix-closed sublanguage of a language given as an NFA even if the language is unary.
  • Weitere Informationen unter:Further Information: Link
  • Projekt:Project: CfaedDIAMOND
  • Forschungsgruppe:Research Group: Wissensbasierte SystemeKnowledge-Based Systems
@article{M2018,
  author    = {Tom{\'{a}}{\v{s}} Masopust},
  title     = {Complexity of Infimal Observable Superlanguages},
  journal   = {IEEE Transactions on Automatic Control},
  volume    = {63},
  number    = {1},
  publisher = {IEEE},
  year      = {2018},
  pages     = {249-254},
  doi       = {10.1109/TAC.2017.2720424}
}