On a class of languages with holonomic generating functions

详细信息    查看全文

• 作者：Giusi Castiglione^a ; ^{giuseppa.castiglione@unipa.it} ; Paolo Massazza^b ; ^{paolo.massazza@uninsubria.it}
• 关键词：Holonomic functions ; Parikh vectors ; Context free languages ; k-counter machines ; Parikh automata
• 刊名：Theoretical Computer Science
• 出版年：2017
• 出版时间：7 January 2017
• 年：2017
• 卷：658
• 期：part_PA
• 页码：74-84
• 全文大小：378 K
• 卷排序：658

文摘

We define a class of languages (RCMRCM) obtained by considering Regular languages, linear Constraints on the number of occurrences of symbols and Morphisms. The class RCMRCM presents some interesting closure properties, and contains languages with holonomic generating functions. As a matter of fact, RCMRCM is related to one-way 1-reversal bounded k  -counter machines and also to Parikh automata on letters. Indeed, RCMRCM is contained in LNFCMLNFCM but not in LDFCMLDFCM, and strictly includes LLPALLPA. We conjecture that LDFCM⊂RCMLDFCM⊂RCM.