Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/37954
標題: Bi-catenation and shuffle product of languages
作者: Shyr, H.J.
喻石生
Yu, S.S.
期刊/報告no:: Acta Informatica, Volume 35, Issue 8, Page(s) 689-707.
摘要: The shuffle product of two words consists of all words obtained by inserting one word into another word sparsely. The shuffle product of two languages is the union of all the shuffle products of two words taken one from each of these two languages. The bi-catenation of two languages A and B is the set A * B = AB boolean OR BA. A non-empty word which is not a power of any other word is called a primitive word. A language is a prefix code if no word in this language is a prefix of any other word in this language. This paper is devoted to the investigation of the elementary properties of bi-catenation and shuffle product of languages. The families of prefix codes, disjunctive languages and languages consisting of primitive words with respective to these two operations are studied. We characterize languages of which the bi-catenation or the shuffle product with any non-empty word are prefix codes. We also derive that for any bifix code A, both A * Q and A * Q((n)), n greater than or equal to 2, are disjunctive languages, where Q is the set of all primitive words over an alphabet X with more than one letter and Q((n)) = {f(n) \f is an element of Q}. For the shuffle product case, surprisingly a lozenge Q is a regular language, where a is a letter of the alphabet X.
URI: http://hdl.handle.net/11455/37954
ISSN: 0001-5903
文章連結: http://dx.doi.org/10.1007/s002360050139
Appears in Collections:資訊科學與工程學系所

文件中的檔案:

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



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