Please use this identifier to cite or link to this item:
標題: Classifications of dense languages
作者: Li, Z.Z.
Shyr, H.J.
Tsai, Y.S.
關鍵字: primitive words;dense languages;n-dense languages;strict n-dense;languages;disjunctive languages
Project: Acta Informatica
期刊/報告no:: Acta Informatica, Volume 43, Issue 3, Page(s) 173-194.
Let X be a finite alphabet containing more than one letter. A dense language over X is a language containing a disjunctive language. A language L is an n-dense language if for any distinct n words w(1), w(2),..., w(n) is an element of X+, there exist two words u, v is an element of X* such that uw(1)v, uw(2)v,... uw(n)v is an element of L. In this paper we classify dense languages into strict n- dense languages and study some of their algebraic properties. We show that for each n >= 0, the n- dense language exists. For an n- dense language L, n not equal 1, the language L boolean AND Q is a dense language, where Q is the set of all primitive words over X. Moreover, for a given n >= 1, the language L is such that L boolean AND Q is an element of D-n(X), then L is an element of D-m( X) for some m, n <= m <= 2n+1. Characterizations on 0-dense languages and n- dense languages are obtained. It is true that for any dense language L, there exist w(1) not equal w(2) is an element of X+ such that uw(1)v, uw(2)v is an element of L for some u, v is an element of X*. We show that every n- dense language, n >= 0, can be split into disjoint union of infinitely many n- dense languages.
ISSN: 0001-5903
DOI: 10.1007/s00236-006-0015-y
Appears in Collections:期刊論文

Show full item record

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.