A1 Refereed original research article in a scientific journal
Results concerning thinness of D0L languages
Authors: Honkala J
Publisher: WORLD SCIENTIFIC PUBL CO PTE LTD
Publication year: 2000
Journal: International Journal of Algebra and Computation
Journal name in source: INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION
Journal acronym: INT J ALGEBR COMPUT
Volume: 10
Issue: 2
First page : 209
Last page: 216
Number of pages: 8
ISSN: 0218-1967
DOI: https://doi.org/10.1142/S0218196700000054
Abstract
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.
UTU Research Portal