Publication
Theoretical Computer Science
Paper

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

View publication

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.

Date

01 Jan 1982

Publication

Theoretical Computer Science

Authors

Topics

Share