The Finite Power Problem revisited

by Daniel Kirsten

In 1966, J.A. Brzozowski raised the finite power problem (FPP): Is it decidable whether for a given recognizable language $L$ there is an integer $n$ with $L^*=\cup_{i=0}^n L^i$. Twelve years later, I. Simon and K. Hashiguchi independently showed its decidability. There are several reasons to investigate this problem once more: In trace monoids, the FPP is equivalent to the star problem. Unfortunately, there are no generalizations of Simon's or Hashiguchi's proofs to trace monoids. This raises the question for a lucid approach to the FPP. Hashiguchi's solution of the FPP was the initial point of a successful research which led to a solution of the so-called star-height-problem. However, Hashiguchi's ideas are less understood. A lucid approach to the FPP could be the initial point to a better understanding of Hashiguchi's results. In the talk, we show a new, lucid approach to the FPP. This approach applies results from the theory of semigroups, e.g., the main proof is done by an induction on the J-classes of the syntactic monoid. A complete presentation of this approach will appear in the journal "Information Processing Letters".