Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/67803
標題: 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
期刊/報告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.
URI: http://hdl.handle.net/11455/67803
ISSN: 0001-5903
文章連結: http://dx.doi.org/10.1007/s00236-006-0015-y
Appears in Collections:期刊論文

文件中的檔案:

取得全文請前往華藝線上圖書館



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