Some properties of the disjunctive languages contained in Q
Tóm tắt
The set of all primitive words Q over an alphabet X was first defined and studied by Shyr and Thierrin (Proceedings of the 1977 Inter. FCT-Conference, Poznan, Poland, Lecture Notes in Computer Science 56. pp. 171–176 (1977)). It showed that for the case |X| ≥ 2, the set along with
$${Q^{(i)} = \{f^i\,|\,f \in Q\}, i\geq 2}$$
are all disjunctive. Since then these disjunctive sets are often be quoted. Following Shyr and Thierrin showed that the half sets
$${Q_{ev} = \{f \in Q\,|\,|f| = {\rm even}\}}$$
and Q
od
= Q \ Q
ev
of Q are disjunctive, Chien proved that each of the set
$${Q_{p,r}= \{u\in Q\,|\,|u|\equiv r\,(mod\,p) \},\,0\leq r < p}$$
is disjunctive, where p is a prime number. In this paper, we generalize this property to that all the languages
$${Q_{n,r}= \{u\in Q\,|\,|u|\equiv r\,(mod\,n) \},\, 0\leq r < n}$$
are disjunctive languages, where n is any positive integer. We proved that for any n ≥ 1, k ≥ 2, (Q
n,0)
k
are all regular languages. Some algebraic properties related to the family of languages {Q
n,r | n ≥ 2, 0 ≤ r < n } are investigated.
Tài liệu tham khảo
Chien T.Y.: Decompositions of a free monoid into disjunctive languages. Soochow J. Math. 5, 121–127 (1979)
Choffrut C., Karhumäki J.: Combinatorics of Words. In: Rozenberg, G., Salomaa, S. (eds) Handbook of Formal languages, Vol. 1, Ch. 6, pp. 329–438. Springer-verlag, Berlin (1997)
Dömösi P., Horväth G., Vuillon L.: On Shyr-Yu theorem. Theor Comput Sci 410, 4874–4877 (2009)
Dömösi, P., Horväth, S., Ito, M., Käszonyi, L., Katsura, M.: Some combinatorial properties of words, and the Chomsky-hierarchy. In: Ito, M., Jürgensen, H., (eds.) Words, languages and combinatorics, II (Kyoto, 1992), pp. 105–123, World Sci. Publishing, River Edge, NJ (1994)
Hungerford T.W.: Algebra. Springer-Verlag, New York (1974)
Levi F.: On semigroups. Bull Calcutta Math. Soc. 36, 141–146 (1944)
Lin, K.-N.: On some classes of languages and codes. Ph.D. thesis, Tamkang College of Arts and Sci (1979)
Lyndon R.C., Schützenberger M.P.: The equation a M = b N c P in a free group. Michgan Math. J. 9, 289–298 (1962)
Păun G., Santean N., Thierrin G., Yu S.S.: On the robusteness of primitive words. Discrete Appl. Math. 117, 239–252 (2002)
Reis C.M., Shyr H.J.: Some properties of disjunctive languages on a free monoid. Inf. Control 37(3), 334–344 (1978)
Shyr H.J.: Disjunctive languages on a free monoid. Inf. Control 34, 123–129 (1977)
Shyr, H.J., Thierrin, G.: Disjunctive languages and codes, fundamentals of computation theory. In: Proceedings of the 1977 Inter. FCT-Conference, Poznan, Poland, Lect. Notes in Comput. Sci. 56, 171–176 (1977)
Shyr H.J.: Free Monoids and Languages. 3rd edn. Hon Min Book Company, Taichung, Taiwan (2001)
Shyr H.J., Yu S.S.: Languages defined by two functions. Soochow J. Math. 20(3), 279–296 (1994)
Shyr H.J., Yu S.S.: Non-primitive words in the language p + q +. Soochow J. Math. 20, 535–546 (1994)