Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/37961
標題: d-minimal languages
作者: Yu, S.S.
喻石生
關鍵字: formal language
primitive
context-free language
combinatorics of
words
annihilator
期刊/報告no:: Discrete Applied Mathematics, Volume 89, Issue 1-3, Page(s) 243-262.
摘要: A word v is said to be a proper d-factor of a word u if v not equal u and u = vx = yv for some words x, y. The family of words which have i distinct proper d-factors is denoted by D(i). According to the number of distinct proper d-factors of words, the free semigroup X+ generated by X can be expressed as the disjoint union of D(i)'s. Words in D(1) are called d-minimal words. d-Minimal words are often called non-overlapping words, dipolar words or unborded words. In this paper, we study the relationship between D-i(I) and D(i) concerning the basic properties of decompositions and catenations of words. We give characterizations of words in D-2(1)boolean AND D(I) and D(2). We also show that sets D-i(I)\D(j) and D(j)\D-i(1) are disjunctive. It is known that every disjunctive language is dense but not regular. We obtain the results that X+D(1) and X+D(2) are regular but X+D(i) is disjunctive for every i greater than or equal to 4. Served as an example of disjunctive d-minimal context-free languages, a disjunctive d-minimal context-free language is constructed. Moreover, we show that the well-known Dyck language is a free semigroup generated by a d-minimal bifix code. The languages of which the catenations consist of d-minimal words are studied in this paper too. That is, some properties of d-minimality-annihilators of languages are investigated. (C) 1998 Elsevier Science B.V. All rights reserved.
URI: http://hdl.handle.net/11455/37961
ISSN: 0166-218X
文章連結: http://dx.doi.org/10.1016/s0166-218x(98)00105-x
Appears in Collections:資訊科學與工程學系所

文件中的檔案:

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



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