Please use this identifier to cite or link to this item:
標題: d-minimal languages
作者: Yu, S.S.
關鍵字: formal language;primitive;context-free language;combinatorics of;words;annihilator
Project: Discrete Applied Mathematics
期刊/報告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.
ISSN: 0166-218X
DOI: 10.1016/s0166-218x(98)00105-x
Appears in Collections:資訊科學與工程學系所

Show full item record

Google ScholarTM




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