Digraph Complexity Measures and Applications in Formal Language Theory
Hermann Gruber
Abstract
We investigate structural complexity measures on digraphs, in
particular the cycle rank. This concept is intimately related to a
classical topic in formal language theory, namely the star height of
regular languages. We explore this connection, and obtain several new
algorithmic insights regarding both cycle rank and star height. Among
other results, we show that computing the cycle rank is
NP-complete, even for sparse digraphs of maximum
outdegree 2. Notwithstanding, we provide both a
polynomial-time approximation algorithm and an exponential-time exact
algorithm for this problem. The former algorithm yields an
O((log n)3/2)-approximation in polynomial
time, whereas the latter yields the optimum solution, and runs in time
and space O*(1.9129n) on digraphs
of maximum outdegree at most 2.
Regarding the star height problem, we identify a subclass of the regular languages for which we can precisely determine the computational complexity of the star height problem. Namely, the star height problem for bideterministic languages is NP-complete, and this holds already for binary alphabets. Then we translate the algorithmic results concerning cycle rank to the bideterministic star height problem. We thus obtain a polynomial-time approximation algorithm, as well as a reasonably fast exact exponential algorithm for the bideterministic star height problem.
Regarding the star height problem, we identify a subclass of the regular languages for which we can precisely determine the computational complexity of the star height problem. Namely, the star height problem for bideterministic languages is NP-complete, and this holds already for binary alphabets. Then we translate the algorithmic results concerning cycle rank to the bideterministic star height problem. We thus obtain a polynomial-time approximation algorithm, as well as a reasonably fast exact exponential algorithm for the bideterministic star height problem.
Full Text: PDF PostScript