Affiliations: Institute of Mechanics, M.V. Lomonosov Moscow State University, Michurinskij av., 1, Moscow, Russian Federation, serg@msu.ru
Correspondence:
[*]
Address for correspondence: Institute of Mechanics, Michurinskij av., 1, 119192, Moscow, Russian Federation.
Abstract: In this paper we summarize known results on decision problems for finitely generated semigroups and rational sets of regular languages and prove various statements on the topic. In particular, we prove undecidability of the equivalence problem for rational set of finite languages, automaticity of finitely generated semigroups of factorial languages, and provide an algorithm for automatic presentation construction in case of regular factorial languages. We also discuss possible direction for future research and describe applications of rational sets of regular languages to computer science problems.
Keywords: Rational set of regular languages, semigroup of regular languages, membership problem, automatic structure, factorial languages
