We give an exact description of the counting function of a sparse context-free language. Let L be a sparse context-free language and let f(L) be its counting function. Then there exist polynomials p(0), P-1,..., Pk-1, with rational coefficients, and an integerconstant k(0), such that for any n >= k(0) one has f(L) (it) = p(j) (n) where j is such that j equivalent to n mod k. As a consequence one can easily show the decidability of some questions concerning sparse context-free languages. Finally, we show that for any sparse context-free language L there exists a regular language L' such that for any n >= 0 one has f(L) (n) = f(L') (it) and, therefore, f(L) is rational. (c) 2006 Elsevier B.V. All rights reserved.

D'Alessandro, F., Intrigila, B., Varricchio, S. (2006). On the structure of the counting function of sparse context-free languages. THEORETICAL COMPUTER SCIENCE, 356, 104-117 [10.1016/j.tcs.2006.01.037].

On the structure of the counting function of sparse context-free languages

INTRIGILA, BENEDETTO;VARRICCHIO, STEFANO
2006-01-01

Abstract

We give an exact description of the counting function of a sparse context-free language. Let L be a sparse context-free language and let f(L) be its counting function. Then there exist polynomials p(0), P-1,..., Pk-1, with rational coefficients, and an integerconstant k(0), such that for any n >= k(0) one has f(L) (it) = p(j) (n) where j is such that j equivalent to n mod k. As a consequence one can easily show the decidability of some questions concerning sparse context-free languages. Finally, we show that for any sparse context-free language L there exists a regular language L' such that for any n >= 0 one has f(L) (n) = f(L') (it) and, therefore, f(L) is rational. (c) 2006 Elsevier B.V. All rights reserved.
2006
Pubblicato
Rilevanza internazionale
Articolo
Sì, ma tipo non specificato
Settore INF/01 - INFORMATICA
English
Contex-free language; Counting function; Sparse language
D'Alessandro, F., Intrigila, B., Varricchio, S. (2006). On the structure of the counting function of sparse context-free languages. THEORETICAL COMPUTER SCIENCE, 356, 104-117 [10.1016/j.tcs.2006.01.037].
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/39288
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 18
  • ???jsp.display-item.citation.isi??? 17
social impact