D0L sequence equivalence is in <i>P</i> for fixed alphabets

作     者：Ruohonen, Keijo 

作者机构：Tampere Univ Technol Inst Math FIN-33101 Tampere Finland 

出 版 物：《RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS》 (法国自动化、信息与运筹学；理论与应用信息)

年 卷 期：2008年第42卷第2期

页      面：361-374页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：D0L system equivalence problem polynomial-time algorithm 

摘      要：A new algorithm is presented for the D0L sequence equivalence problem which, when the alphabets are fixed, works in time polynomial in the rest of the input data. The algorithm uses a polynomial encoding of words and certain well-known properties of Z-rational sequences.