Decision Problems and Applications of Rational Sets of Regular Languagesстатья
Информация о цитировании статьи получена из
Web of Science,
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 2 октября 2018 г.
Аннотация: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.