Let L be a sparse context-free language over an alphabet of t letters and let f_L:N^t→N be its Parikh counting function. We prove the following two results: 1. There exists a partition of N^t into a finite family of polyhedra such that the function f_L is a quasi-polynomial on each polyhedron of the partition. 2. There exists a partition of N^t into a finite family of rational subsets such that the function f_L is a polynomial on each set of the partition.
D’Alessandro, F., Intrigila, B., Varricchio, S. (2009). The Parikh counting functions of sparse context-free languages are quasi-polynomials. THEORETICAL COMPUTER SCIENCE, 410(47-49), 5158-5191 [10.1016/j.tcs.2009.09.006].
The Parikh counting functions of sparse context-free languages are quasi-polynomials
INTRIGILA, BENEDETTO;VARRICCHIO, STEFANO
2009-01-01
Abstract
Let L be a sparse context-free language over an alphabet of t letters and let f_L:N^t→N be its Parikh counting function. We prove the following two results: 1. There exists a partition of N^t into a finite family of polyhedra such that the function f_L is a quasi-polynomial on each polyhedron of the partition. 2. There exists a partition of N^t into a finite family of rational subsets such that the function f_L is a polynomial on each set of the partition.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.