Paper Info
Title
Connecting partial words and regular languages
Abstract
We initiate a study of languages of partial words related to regular languages of full words. First, we study the possibility of expressing a regular language of full words as the image of a partial-words-language through a substitution that only replaces the hole symbols of the partial words with a finite set of letters. Results regarding the structure, uniqueness and succinctness of such a representation, as well as a series of related decidability and computational-hardness results, are presented. Finally, we define a hierarchy of classes of languages of partial words, by grouping together languages that can be connected in strong ways to regular languages, and derive their closure properties.
Year
DOI
Venue
2012
10.1007/978-3-642-30870-3_16
CiE
Keywords
DocType
Citations 
related decidability,computational-hardness result,closure property,strong way,full word,finite set,partial word,hole symbol,regular language
Conference
2
PageRank 
References 
Authors
0.47
7
3
Name
Order
Citations
PageRank
Jürgen Dassow1530118.27
Florin Manea237258.12
Robert Mercaş3506.15