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 |
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. |
URI: | http://hdl.handle.net/11455/37961 |
ISSN: | 0166-218X |
DOI: | 10.1016/s0166-218x(98)00105-x |
Appears in Collections: | 資訊科學與工程學系所 |
Show full item record
TAIR Related Article
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.