Decidability of "Skolem matrix emptiness problem" entails constructability of exact regular expression

Abstract

The famous result of T. Skolem of 1933 assures the regularity of JA-sets of arbitrary integer valued matrices A. It prompts also a problem of deciding the emptiness of JA (Skolem Problem), and a more important problem of describing JA in terms of finite-state machine or Kleene's Regular Expression. We show (by elementary method) that recursiveness of Skolem Problem entails constructability of exact regular expression (machine). Under the same assumption, this provides an algorithm for the full matrix equivalence problem JA = JB. Moreover, we prove the equivalence problem 'modulo a finite set' JA = FJB to be recursively solvable. © 1982.