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.
2009
Pubblicato
Rilevanza internazionale
Articolo
Sì, ma tipo non specificato
Settore INF/01 - INFORMATICA
English
Sparse language; Context-free language; Semi-linear set; Parikh counting function
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].
D’Alessandro, F; Intrigila, B; Varricchio, S
Articolo su rivista
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/33158
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 10
  • ???jsp.display-item.citation.isi??? 10
social impact