Complexity of Infimal Observable Superlanguages

Tomáš MasopustTomáš Masopust

ISSN: 0018-9286
Download
DOI Link

Tomáš Masopust
Complexity of Infimal Observable Superlanguages
IEEE Transactions on Automatic Control, 63(1):249-254, 2018

Details
Bibtex

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: Cfaed, DIAMOND
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}
}