Article ID Journal Published Year Pages File Type
437969 Theoretical Computer Science 2009 24 Pages PDF
Abstract

Let L be a sparse context-free language over an alphabet of t letters and let fL:Nt→N be its Parikh counting function. We prove the following two results: 1.There exists a partition of Nt into a finite family of polyhedra such that the function fL is a quasi-polynomial on each polyhedron of the partition.2.There exists a partition of Nt into a finite family of rational subsets such that the function fL is a polynomial on each set of the partition.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics