A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Results concerning thinness of D0L languages
Tekijät: Honkala J
Kustantaja: WORLD SCIENTIFIC PUBL CO PTE LTD
Julkaisuvuosi: 2000
Journal: International Journal of Algebra and Computation
Tietokannassa oleva lehden nimi: INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION
Lehden akronyymi: INT J ALGEBR COMPUT
Vuosikerta: 10
Numero: 2
Aloitussivu: 209
Lopetussivu: 216
Sivujen määrä: 8
ISSN: 0218-1967
DOI: https://doi.org/10.1142/S0218196700000054
Tiivistelmä
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.
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.
Turun yliopiston Tutkimustietojärjestelmän portaali