Bounded D0L languages
type: Item
instance of: scholarly article
title: Bounded D0L languages
zbMATH Open document ID: 0636.68097
DOI: 10.1016/0304-3975(87)90035-1
author: Tom Head
author: Barbara Lando
published in: Theoretical Computer Science
publication date: 1987-01-01T00:00:00Z
review text: The authors show that for a given alphabet A and a morphism h the set of words w such that the D0L language L(A,h,w) is bounded (i.e. is a subset of \(x\) \(*_ 1x\) \(*_ 2...x\) \(*_ n\) for some words \(x_ 1,x_ 2,...,x_ n\) over A) is B *, where B is an effectively computable subset of A. This implies that it is decidable whether a given D0L system \(S=(A,h,w)\) generates a bounded set. Moreover, if \(S=(A,h,w)\) is a polynomially bounded D0L system (i.e. the growth function of S is bounded by some polynomial) then L(S) is bounded if and only if S is linearly bounded.
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q42
zbMATH DE Number: 4037250
zbMATH Keywords: bounded D0L languages
zbMATH Keywords: periodic D0L languages
zbMATH Keywords: D0L system
reviewed by: Matti Linna
MaRDI profile type: Publication
full work available at URL: 0304-3975(87)90035-1
OpenAlex ID: W123646645
cites work: Q5576254
cites work: Q3899529
cites work: Q4045671
cites work: On the periodicity of morphisms on free monoids
cites work: Periodic D0L languages
cites work: Regularity of sets of initial strings of periodic D0L-systems
cites work: Code properties and homomorphisms of DOL systems
cites work: Decidability of periodicity for infinite words
cites work: Q4140407
cites work: Q3948608
Recommended article: Bounded Counter Languages
Recommended article: Q3345795
Recommended article: Bounds for the D0L language equivalence problem
Recommended article: Scope-Bounded Pushdown Languages
Recommended article: Scope-bounded pushdown languages
Recommended article: Q3606478
Recommended article: Bounded languages described by GF(2)-grammars
Recommended article: Q4452071
Recommended article: A new bound for the D0L language equivalence problem
Recommended article: Uniformly bounded duplication languages
description: scientific article; zbMATH DE number 4037250