We define a class of languages (RCM) obtained by considering Regular languages, linear Constraints on the number of occurrences of symbols and Morphisms. The class RCM presents some interesting closure properties, and contains languages with holonomic generating functions. As a matter of fact, RCM is related to one-way 1-reversal bounded k-counter machines and also to Parikh automata on letters. Indeed, RCM is contained in L-NFCM but not in L-DFCM, and strictly includes L-CPA. We conjecture that L-DFCM subset of RCM
Castiglione, G., Massazza, P. (2017). On a class of languages with holonomic generating functions. THEORETICAL COMPUTER SCIENCE, 658, 74-84 [10.1016/j.tcs.2016.07.022].
On a class of languages with holonomic generating functions
Castiglione, Giuseppa
;
2017-01-01
Abstract
We define a class of languages (RCM) obtained by considering Regular languages, linear Constraints on the number of occurrences of symbols and Morphisms. The class RCM presents some interesting closure properties, and contains languages with holonomic generating functions. As a matter of fact, RCM is related to one-way 1-reversal bounded k-counter machines and also to Parikh automata on letters. Indeed, RCM is contained in L-NFCM but not in L-DFCM, and strictly includes L-CPA. We conjecture that L-DFCM subset of RCM
| File | Dimensione | Formato | |
|---|---|---|---|
|
[33]TCS_SI_Restivo.pdf
Solo gestori archvio
Tipologia:
Versione Editoriale
Dimensione
469.03 kB
Formato
Adobe PDF
|
469.03 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
