Skip to main content
Passa alla visualizzazione normale.

GIUSEPPA CASTIGLIONE

On a class of languages with holonomic generating functions

  • Authors: Castiglione, G.; Massazza, P.
  • Publication year: 2017
  • Type: Articolo in rivista (Articolo in rivista)
  • Key words: Context free languages; Holonomic functions; k-counter machines; Parikh automata; Parikh vectors; Theoretical Computer Science; Computer Science (all)
  • OA Link: http://hdl.handle.net/10447/254435

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