JUCS - Journal of Universal Computer Science 5(9): 532-541, doi: 10.3217/jucs-005-09-0532
Decidable and Undecidable Problems of Primitive Words, Regular and Context-Free Languages
expand article infoSándor Horváth‡, Masami Ito§
‡ Department of Computer Science, L. Eötvös University, Hungary§ Department of Mathematics, Kyoto Sangyo University, Kyoto, Japan

Corresponding author: Sándor Horváth ( horvath@cs.elte.hu )

© Sándor Horváth, Masami Ito.
This article is freely available under the J.UCS Open Content License.
Citation: Horváth S, Ito M (1999) Decidable and Undecidable Problems of Primitive Words, Regular and Context-Free Languages. JUCS - Journal of Universal Computer Science 5(9): 532-541. https://doi.org/10.3217/jucs-005-09-0532
Open Access
Abstract
For any language L over an alphabet X, we define the root set, root(L) and the degree set, deg(L) as follows: (1) root(L) = where Q is the set of all primitive words over X, (2) deg(L) = . We deal with various decidability problems related to root and degree sets.
Keywords
root sets, degree sets, regular languages, context-free languages, decidability problems