Recognizable and Rational Subsets of Algebras

Article type: Research Article

Authors: Steinby, Magnus

Affiliations: University of Turku, Department of Mathematics, SF-20500 Turku, Finland

Abstract: In this paper recognizable and rational subsets of general algebras of finite type are studied. These are natural generalizations of the familiar notions originally defined for monoids, but they also include as special cases recognizable and rational tree languages, for example. Some closure properties of the families of recognizable and rational subsets are studied. The operations considered seem to be intimately connected with the recognizability and rationality properties of subsets, and they can also be defined for subsets of abstract algebras, regardless of the nature of the elements. The last part of the paper is devoted to generalized forms of Kleene’s theorem and related results.

DOI: 10.3233/FI-1993-182-412

Journal: Fundamenta Informaticae, vol. 18, no. 2-4, pp. 249-266, 1993