Results concerning thinness of D0L languages

: Honkala J

Publisher: WORLD SCIENTIFIC PUBL CO PTE LTD

: 2000

: International Journal of Algebra and Computation

: INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION

: INT J ALGEBR COMPUT

: 10

: 2

: 209

: 216

: 8

: 0218-1967

DOI: https://doi.org/10.1142/S0218196700000054

A language L is called thin if there exists an integer no such that for all n greater than or equal to n(0) L contains at most one word of length n. We show that thinness is decidable for exponential D0L languages. We show also that Siegel's result concerning integral points on algebraic curves of positive genus can often be used to prove that a polynomially bounded HD0L language is thin.