Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 5 / Issue 9

available in:   PDF (178 kB) PS (60 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-005-09-0532


Decidable and Undecidable Problems of Primitive Words, Regular and Context-Free Languages

Sándor Horváth (Department of Computer Science, L. Eötvös University, Hungary)

Masami Ito (Faculty of Science, Kyoto Sangyo University, Japan)


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: context-free languages, decidability problems, degree sets, regular languages, root sets