ON THE COMPLEXITY OF SOME EXTENDED WORD-PROBLEMS DEFINED BY CANCELLATION RULES

被引：15

作者：

BENOIS, M ^{[1
]}

SAKAROVITCH, J ^{[1
]}

机构：

[1] UNIV PARIS 06,LITP,F-75230 PARIS 05,FRANCE

来源：

INFORMATION PROCESSING LETTERS | 1986年 / 23卷 / 06期

关键词：

COMPUTER PROGRAMMING - Algorithms - CRYPTOGRAPHY;

D O I：

10.1016/0020-0190(86)90087-6

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We give an algorithm which computes the set of descendants of a regular set R, for Thue systems of certain type. The complexity of the algorithm is O(m**3) where m is the number of states of an automation recognizing R. This allows to improve the known complexity bounds for some extended work problems defined by cancellation rules. The results have bearing on recent work on public key encryption for secure network communication.

引用

页码：281 / 287

页数：7

共 10 条

[1]

BENOIS M, 1969, CR ACAD SCI A MATH, V269, P1188

[2]

BERSTEL J, 1979, TRANSDUCTIONS CONTEX

[3] CANCELLATION RULES AND EXTENDED WORD-PROBLEMS [J].