THE CODE PROBLEM FOR DIRECTED FIGURES

作     者：Kolarz, Michal 

作者机构：Jagiellonian Univ Inst Comp Sci PL-30348 Krakow Poland 

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

年 卷 期：2010年第44卷第4期

页      面：489-506页

核心收录：

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

主　　题：Directed figures variable-length codes codicity verification Sardinas-Patterson algorithm 

摘      要：We consider directed figures defined as labelled polyominoes with designated start and end points, with two types of catenation operations. We are especially interested in codicity verification for sets of figures, and we show that depending on the catenation type the question whether a given set of directed figures is a code is decidable or not. In the former case we give a constructive proof which leads to a straightforward algorithm.