On Bounded Rational Trace Languages期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

On Bounded Rational Trace Languages

Authors:	Christian Choffrut Flavio D’Alessandro Stefano Varricchio

Affiliation:	1. Laboratoire LIAFA, Université de Paris 7, 2 pl. Jussieu, 75251, Paris Cedex 05, France 2. Dipartimento di Matematica, Università di Roma “La Sapienza”, Piazzale Aldo Moro 2, 00185, Rome, Italy 3. Dipartimento di Matematica, Università di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133, Rome, Italy

Abstract:	In this paper, for a finitely generated monoid M, we tackle the following three questions: Is it possible to give a characterization of rational subsets of M which have polynomial growth? What is the structure of the counting function of rational sets which have polynomial growth? Is it true that every rational subset of M has either exponential growth or it has polynomial growth? Can one decide for a given rational set which of the two options holds? We give a positive answer to all the previous questions in the case that M is a direct product of free monoids. Some of the proved results also extend to trace monoid.

Keywords:
本文献已被 SpringerLink 等数据库收录！