Please use this identifier to cite or link to this item:
標題: Bi-catenation and shuffle product of languages
作者: Shyr, H.J.
Yu, S.S.
Project: Acta Informatica
期刊/報告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.
ISSN: 0001-5903
DOI: 10.1007/s002360050139
Appears in Collections:資訊科學與工程學系所

Show full item record

Google ScholarTM




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