权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Formal Languages, Codes and Cryptosystems

形式语言、代码和密码系统

基本信息

批准号：
10440034
负责人：
ITO Masami
金额：
$ 4.99万
依托单位：
Kyoto Sangyo University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (B).
财政年份：
1998
资助国家：
日本
起止时间：
1998 至 2000
项目状态：
已结题

项目摘要

A word u is said to be primitive if u cannot be represented as the power of another word. By Q(X) we denote the set of all primitive words over X.It is conjectured that Q(X) is not context-free. However, this conjecture is still open. In our research, we investigate some decidability problems concerning Q(X) and its related languages. Let u ∈ X^+. If u = v^l for a positive integer l and a primitive word v, then we denote root (u) = v. For a language L ⊆ X^+, we define root(L) = ∪_<u∈L> root(u). Then we have the following results : (1) For a given regular (or context-free) language L ⊆ X^+, it is decidable whether root(L) is finite. (2) For a given regular language L ⊆ X^+, it is decidable whether root(L) is regular. (3) For a given context-free language L ⊆ X^+, it is undecidable whether root(L) is regular (or context-free). (4) For a given regular language L ⊆ X^+, it is decidable whether L ⊆ Q(X) holds. (5) For a given context-free language L ⊆ X^+, it is undecidable whether L ⊆ Q(X) holds.Let L ⊆ X^+. Then, by deg(L) we mean the set {i : q ∈ Q(X), q^l ∈ L}. Then we have the following results : (1) For a given regular language L ⊆ X^+, it is decidable whether deg(L) is finite. (2) For a given context-free language L ⊆ X^+, it is undecidable whether deg(L) is finite.A language L ⊆ X^+ is said to be palindromic if all words in L are palindromes. It is known that there is no dense palindromic regular language contained in Q(X). For the case of context-free palindromic languages, we have the same result and moreover we can prove that deg(L) is infinite (more exactly, aperiodic) if L ⊆ X^+ is a dense palindromic context-free language.For the period between April 1, 1998 and March 31, 2001, we have also investigated deterministic and/or nondeterministic directable automata and related languages, some kinds of code-related Petri net languages etc.

如果u不能表示为另一个词的幂，则称该词u为本原词。我们用Q（X）表示X上所有原始词的集合。推测Q（X）不是上下文无关的。然而，这一猜想仍然是开放的。在我们的研究中，我们研究了关于Q（X）及其相关语言的一些可判定性问题。设u ∈ X^+。如果对于一个正整数l和一个本原词v，u = v^l，那么我们记为root（u）= v。对于一个语言L <$X^+，我们定义root（L）=<$_<u∈L> root（u）。（1）对于给定的正则（或上下文无关）语言L <$X^+，根（L）是否有限是可判定的。(2)对于给定的正则语言L <$X^+，根（L）是否正则是可判定的。(3)对于一个给定的上下文无关语言L <$X^+，根（L）是否是正则的（或上下文无关的）是不可判定的。(4)对于给定的正则语言L <$X^+，L <$Q（X）是否成立是可判定的。(5)对于给定的上下文无关语言L <$X^+，L <$Q（X）是否成立是不可判定的。设L <$X^+。然后，我们用deg（L）表示集合{i：q ∈ Q（X），q^l ∈ L}。（1）对于给定的正则语言L <$X^+，deg（L）是否有限是可判定的. (2)对于给定的上下文无关语言L <$X^+，deg（L）是否有限是不可判定的。如果L中的所有单词都是回文的，则称语言L <$X^+是回文的。已知Q（X）中不存在稠密回文正则语言。对于上下文无关的回文语言，我们也得到了同样的结果，并且证明了deg（L）是无穷大的（更确切地说，是非周期性的），如果L <$X^+是稠密回文上下文无关语言。在1998年4月1日至2001年3月31日期间，我们还研究了确定性和/或非确定性有向自动机及相关语言，一些与代码相关的Petri网语言等。