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是原始的。通过Q（x），我们表示X上所有原始单词的集合。它猜想Q（x）不是不含上下文的。但是，这个概念仍然是开放的。在我们的研究中，我们研究了有关Q（X）及其相关语言的一些决策问题。令U∈X^+。如果u = v^l对于正整数l和一个原始单词v，则我们表示root（u）= v。对于语言l⊆x^+，我们定义root（l）=∪___<u∈L>root（u）。然后，我们有以下结果：（1）对于给定的常规（或上下文）语言l⊆x^+，是否可以定期进行确定。（2）对于给定的常规语言l⊆X^+，是否可以毫无疑问root（l）。（3）对于给定的无上下文语言l⊆x^+，是否root（l）是常规的。是常规的（或无上下文）。（4）对于给定的常规语言l⊆x^+，决定是否持有l⊆q（x）。（5）对于给定的无上下文语言l⊆x^+，无论l⊆q（x）holds.letl⊆x^+是不可见的。然后，按DEG（L），我们的意思是集{i：q∈Q（x），q^l∈L}。然后，我们有以下结果：（1）对于给定的常规语言l⊆X^+，可以决定DEG（L）是否有限。（2）对于给定的无上下文语言l⊆x^+，如果l语言是有限的。deg（l）是否是有限的。众所周知，Q（x）中没有密集的全文常规语言。对于无上下文的印第安语言的情况，我们可以得到相同的结果，并且我们可以证明，如果l⊆x^+是一种密集的无上下文语言，DEG（更准确地说，更准确地说，上的上的）是无限的（更准确地说，上的）。培养皿网语等