A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Decision problems concerning thinness and slenderness of formal languages
Tekijät: Honkala J
Kustantaja: SPRINGER VERLAG
Julkaisuvuosi: 1998
Journal: Acta Informatica
Tietokannassa oleva lehden nimi: ACTA INFORMATICA
Lehden akronyymi: ACTA INFORM
Vuosikerta: 35
Numero: 7
Aloitussivu: 625
Lopetussivu: 636
Sivujen määrä: 12
ISSN: 0001-5903
DOI: https://doi.org/10.1007/s002360050134
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali