Anzeige
Erschienen in:
2018 | OriginalPaper | Buchkapitel
The Exact Complexity of Star-Complement-Star
verfasst von : Jozef Jirásek, Galina Jirásková
Erschienen in: Implementation and Application of Automata
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
We show that the state complexity of the star-complement-star operation is given by \(\frac{3}{2}f(n\,-\,1) \,+\, 2 f(n\,-\,2) \,+\, 2n \,-\,5\), where \(f(2)=2\) and \(f(n) = \sum _{i=1}^{n-2}{n\atopwithdelims ()i} f (n\,-\,i) \,+\,2\). The function f(n) counts the number of distinct resistances possible for n arbitrary resistors each connected in series or parallel with previous ones, or the number of labeled threshold graphs on n vertices, and \(f(n)\sim n!(1-\ln 2)/(\ln 2)^{n+1} =2^{n \log n - 0.91 n + o(n)}\). Our witness language is defined over a quaternary alphabet, and we strongly conjecture that the size of the alphabet cannot be decreased.