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.
2010
bounded languages; rational relations; trace languages
01 Pubblicazione su rivista::01a Articolo in rivista
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]
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/122660
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 3
social impact