Unavoidable Sets of Partial Words of Uniform Length

Autor:	Becker, Joey, Blanchet-Sadri, F., Flapan, Laure, Watkins, Stephen
Rok vydání:	2017
Předmět:	Computer Science - Formal Languages and Automata Theory F.4.3
Zdroj:	EPTCS 252, 2017, pp. 26-40
Druh dokumentu:	Working Paper
DOI:	10.4204/EPTCS.252.7
Popis:	A set X of partial words over a finite alphabet A is called unavoidable if every two-sided infinite word over A has a factor compatible with an element of X. Unlike the case of a set of words without holes, the problem of deciding whether or not a given finite set of n partial words over a k-letter alphabet is avoidable is NP-hard, even when we restrict to a set of partial words of uniform length. So classifying such sets, with parameters k and n, as avoidable or unavoidable becomes an interesting problem. In this paper, we work towards this classification problem by investigating the maximum number of holes we can fill in unavoidable sets of partial words of uniform length over an alphabet of any fixed size, while maintaining the unavoidability property. Comment: In Proceedings AFL 2017, arXiv:1708.06226
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1708.06459 Zobrazit plný text záznamu View this record from Arxiv