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.
The Parikh functions of sparse context-free languages are quasi-polynomials / D'Alessandro, Flavio; Intrigila, B; Varricchio, S.. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 410:(2009), pp. 5158-5181. [10.1016/j.tcs.2009.09.006]
The Parikh functions of sparse context-free languages are quasi-polynomials
D'ALESSANDRO, Flavio
;
2009
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.
