Complexity of infimal observable superlanguages
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F18%3A00484221" target="_blank" >RIV/67985840:_____/18:00484221 - isvavai.cz</a>
Výsledek na webu
<a href="http://dx.doi.org/10.1109/TAC.2017.2720424" target="_blank" >http://dx.doi.org/10.1109/TAC.2017.2720424</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1109/TAC.2017.2720424" target="_blank" >10.1109/TAC.2017.2720424</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Complexity of infimal observable superlanguages
Popis výsledku v původním jazyce
The infimal prefix-closed, controllable, and observable superlanguage plays an essential role in the relationship between controllability, observability, and co-observability -- the central notions of supervisory control. Existing algorithms are exponential and it is not known whether 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 deterministic finite automaton (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).
Název v anglickém jazyce
Complexity of infimal observable superlanguages
Popis výsledku anglicky
The infimal prefix-closed, controllable, and observable superlanguage plays an essential role in the relationship between controllability, observability, and co-observability -- the central notions of supervisory control. Existing algorithms are exponential and it is not known whether 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 deterministic finite automaton (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).
Klasifikace
Druh
J<sub>imp</sub> - Článek v periodiku v databázi Web of Science
CEP obor
—
OECD FORD obor
20205 - Automation and control systems
Návaznosti výsledku
Projekt
—
Návaznosti
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
Rok uplatnění
2018
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název periodika
IEEE Transactions on Automatic Control
ISSN
0018-9286
e-ISSN
—
Svazek periodika
63
Číslo periodika v rámci svazku
1
Stát vydavatele periodika
US - Spojené státy americké
Počet stran výsledku
6
Strana od-do
249-254
Kód UT WoS článku
000419089000022
EID výsledku v databázi Scopus
2-s2.0-85023760473