Recognizability of Rational Sets
Deterministic and non-deterministic finite automata accept the same family of sets of finite words, namely the regular languages. However, determinism and non-determinism do not necessarily coincide for other structures such as ω-words or elements of certain monoids. This work will mainly be concerned with monoids. This work will regard rational subsets as a generalization of non-deterministic finite automata and recognizable subsets as a generalization of deterministic finite automata. These families of subsets can be regarded as deterministic and non-deterministic finite automata over monoids. Some basic results on recognizable and rational subsets will be presented in order to illustrate the difference between these families of subsets. The main statement of this work is the decidability of recognizability of rational subsets of finitely generated, commutative monoids. As an application, the result will be used to present a solution on inclusion problems between rational and recognizable subsets of finitely generated, commutative monoids.