A1 Refereed original research article in a scientific journal
Decision problems concerning thinness and slenderness of formal languages
Authors: Honkala J
Publisher: SPRINGER VERLAG
Publication year: 1998
Journal: Acta Informatica
Journal name in source: ACTA INFORMATICA
Journal acronym: ACTA INFORM
Volume: 35
Issue: 7
First page : 625
Last page: 636
Number of pages: 12
ISSN: 0001-5903
DOI: https://doi.org/10.1007/s002360050134
Abstract
A language L is called thin if for almost all n there is at most one word of length n in L. A language L is called slender if there is a positive integer k such that for any n there are at most k words of length n in L. The notions of Parikh thin and Parikh slender languages are defined similarly by counting the words with the same Parikh vectors instead of the words of the same length. In this paper we discuss decision problems concerning these four properties. It is shown that all four properties are decidable for bounded semilinear languages but undecidable for DTOL languages. As a consequence all these problems are decidable for context-free languages.
A language L is called thin if for almost all n there is at most one word of length n in L. A language L is called slender if there is a positive integer k such that for any n there are at most k words of length n in L. The notions of Parikh thin and Parikh slender languages are defined similarly by counting the words with the same Parikh vectors instead of the words of the same length. In this paper we discuss decision problems concerning these four properties. It is shown that all four properties are decidable for bounded semilinear languages but undecidable for DTOL languages. As a consequence all these problems are decidable for context-free languages.
UTU Research Portal