On slender 0L languages over the binary alphabet

: Honkala J

Publisher: SPRINGER VERLAG

: 2000

: Acta Informatica

: ACTA INFORMATICA

: ACTA INFORM

: 36

: 9-10

: 805

: 815

: 11

: 0001-5903

DOI: https://doi.org/10.1007/s002360050175

A language L is called slender if there exists a constant k such that L contains no k words of equal length. In this paper we continue the study of relationships between slender languages and bounded languages. We show that if a 0L language L over a two-letter alphabet is slender then L is a D0L language or L is a bounded language. As an application we prove the decidability of the slenderness problem in many cases.