Complexity of Infimal Observable Superlanguages

DOI10.1109/TAC.2017.2720424MaRDI QIDQ4567064zbMATH OpenOpenAlexFDO

Authors Tomáš Masopust

Publication date 27 June 2018

Published in IEEE Transactions on Automatic Control (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1703.05016

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Discrete event control/observation systems (93C65)

Abstract: 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 theory. Existing algorithms for its computation are exponential and it is not known whether a polynomial algorithm exists. In this paper, we study the state complexity of this language. State complexity of a language is the number of states of the minimal DFA for the language. For a language of 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. It proves that there is no algorithm computing a DFA of the infimal prefix-closed and observable superlanguage in polynomial time. Our construction further 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 the supremal prefix-closed sublanguage and show that there is no polynomial-time algorithm that computes an NFA of the supremal prefix-closed sublanguage of a language given as an NFA even if the language is unary.

Cited in

(5)

• scientific article; zbMATH DE number 1528682 (Why is no real title available?)
• New Algorithms for Verification of Relative Observability and Computation of Supremal Relatively Observable Sublanguage
• The infimal controllable and N-observable superpredicate of a given predicate
• Characterization of co-observable languages and formulas for their super/sublanguages
• Approximation of sets of superwords by L-language formulas

This page was built for publication: Complexity of Infimal Observable Superlanguages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4567064)