@inproceedings{dadb65bd3e3645e3a4cc1165e7697304,

title = "Inferring strings from runs",

abstract = "A run in a string is a nonextendable periodic substring in the string. Detecting all runs in a string is important and studied both from theoretical and practical points of view. In this paper, we consider the reverse problem of it. We reveal that the time complexity depends on the alphabet size k of the string to be output. We show that it is solvable in polynomial time for both binary alphabet and infinite alphabet, while it is NP-complete for finite k ≥ 4.We also consider a variant of the problem where only a subset of runs are given as an input. We show that it is solvable in polynomial time for infinite alphabet, while it is NP-complete for finite k ≥ 3.",

keywords = "Inferring problem, Repetition, Runs",

author = "Wataru Matsubara and Akira Ishino and Ayumi Shinohara",

year = "2010",

language = "English",

isbn = "9788001045978",

series = "Proceedings of the Prague Stringology Conference 2010",

pages = "150--160",

booktitle = "Proceedings of the Prague Stringology Conference 2010",

note = "Prague Stringology Conference 2010, PSC 2010 ; Conference date: 30-08-2010 Through 01-09-2010",

}