A1 Journal article – refereed
On slender 0L languages over the binary alphabet

List of Authors: Honkala J
Publication year: 2000
Journal: Acta Informatica
Journal name in source: ACTA INFORMATICA
Journal acronym: ACTA INFORM
Volume number: 36
Issue number: 9-10
Number of pages: 11
ISSN: 0001-5903

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.

Internal Authors/Editors

Last updated on 2019-20-07 at 14:44