The root of a language and its complexity

被引：0

作者：

Lischke, G ^{[1
]}

机构：

[1] Univ Jena, Fac Math & Informat, Inst Informat, D-07743 Jena, Germany

来源：

DEVELOPMENTS IN LANGUAGE THEORY | 2002年 / 2295卷

关键词：

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

The root of a language L is the set of all primitive words p such that p(n) belongs to L for some n greater than or equal to 1. We show that the gap between the time complexity and space complexity, respectively, of a language and that of its root can be arbitrarily great. From this we conclude that there exist regular languages the roots of which are not even context-sensitive. Also we show that the quadratic time complexity for deciding the set of all primitive words by an 1-tape Turing machine is optimal.

引用

页码：272 / 280

页数：9

共 17 条

[1]

Balcazar J., 1988, STRUCTURAL COMPLEXIT, V1

[2]

BARZDIN JM, 1965, PROBL KIBERN, V15, P245

[3]

DOMOSI P, 1993, PUBL MATH-DEBRECEN, V42, P315

[4]

Domosi P., 1991, P 1 SESSION SCI COMM, P59

[5] ON COMPUTATIONAL COMPLEXITY OF ALGORITHMS [J].

HARTMANIS, J ;

STEARNS, RE .

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1965, 117 (05) :285-+

[6]

HARTMANIS J, 1965, P 6 ANN IEEE S SWITC, P179

[7] ONE-TAPE OFF-LINE TURING MACHINE COMPUTATIONS [J].

HENNIE, FC .

INFORMATION AND CONTROL, 1965, 8 (06) :553-&

[8]

Hopcroft J. E., 2007, Introduction to Automata Theory, Languages and Computation

[9]

HORVATH S, 1995, PUMA, V6, P171

[10]

Jurgensen H., 1997, Handbook of Formal Languages, V1, P511

← 1 2 →