Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
437969 | Theoretical Computer Science | 2009 | 24 Pages |
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