6533b7d8fe1ef96bd126ae57
RESEARCH PRODUCT
On a class of languages with holonomic generating functions
Paolo MassazzaGiusi Castiglionesubject
Class (set theory)Holonomic functionsGeneral Computer Science0102 computer and information sciences02 engineering and technologyContext free language01 natural sciencesTheoretical Computer ScienceMorphismRegular language0202 electrical engineering electronic engineering information engineeringParikh vectorMathematicsDiscrete mathematicsk-counter machineHolonomic functionConjecturek-counter machinesSettore INF/01 - InformaticaHolonomicParikh automataComputer Science (all)Context-free languageParikh vectorsAlgebraContext free languagesClosure (mathematics)010201 computation theory & mathematicsBounded function020201 artificial intelligence & image processingHolonomic functions; Parikh vectors; Context free languages; k-counter machines; Parikh automatadescription
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
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2017-01-01 |