In this paper, for a finitely generated monoid M, we tackle the following three questions: center dot Is it possible to give a characterization of rational subsets of M which have polynomial growth? center dot What is the structure of the counting function of rational sets which have polynomial growth? center dot 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.
On Bounded Rational Trace Languages / Christian, Choffrut; D'Alessandro, Flavio; Stefano, Varricchio. - In: THEORY OF COMPUTING SYSTEMS. - ISSN 1432-4350. - 46:2(2010), pp. 351-369. [10.1007/s00224-008-9143-9]
On Bounded Rational Trace Languages
D'ALESSANDRO, Flavio;
2010
Abstract
In this paper, for a finitely generated monoid M, we tackle the following three questions: center dot Is it possible to give a characterization of rational subsets of M which have polynomial growth? center dot What is the structure of the counting function of rational sets which have polynomial growth? center dot 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.