The topological approach to the limitedness problem on distance automata

Summary

Introduction

The finite automaton [11] is a mathematical model of a computing device. It is very simple and captures the essential features of a sequential circuit. The only difference is that a finite automaton does not produce outputs. Its main objective is to decide whether to accept a given input. The study of finite automata is closely related to the study of regular languages in formal language theory.

Hashiguchi [5] and Simon [18] studied the finite power property problem of regular languages. Hashiguchi's solution is a direct application of the pigeonhole principle. Simon solved the problem by reducing it to the problem of deciding whether a given finitely generated semigroup of matrices over the tropical semiring is finite.

Hashiguchi studied the star height problem and the representation problems for regular languages in ([6], [8], [9]). His solutions relied heavily on the decidability result of the limitedness problem ([7], [10]) for distance automata. Conceptually, the distance automaton is an extension of the finite automaton such that the automaton not only decides whether an input is accepted, but also assigns a measure of cost for the effort to accept the input. In fact, the finite power property problem can be considered as a special case of the limitedness problem.

The nondeterministic behavior of finite automata in connection with their inner structure was considered in ([12], [3], [4]). One important decision problem that arose from this study is a slightly weaker version of the limitedness problem for distance automata.

Motivated by Simon's solution for the finite power property problem, Leung ([14], [15]) also solved the limitedness problem for distance automata by introducing a topological approach and by extending Simon's technique.