Paper Info
Title
Regular languages of partial words
Abstract
We initiate a study of languages of partial words related to regular languages of full words. First, we investigate 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 by 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 introduce a hierarchy of classes of languages of partial words, by grouping together languages that can be connected in various strong ways to regular languages, and derive their closure properties with respect to several regular operations.
Year
DOI
Venue
2014
10.1016/j.ins.2013.12.032
Inf. Sci.
Keywords
Field
DocType
related decidability,computational-hardness result,closure property,full word,various strong way,regular operation,finite set,partial word,hole symbol,regular language,finite automaton,automata theory
Generalized star height problem,Discrete mathematics,Formal language,Nested word,Abstract family of languages,Arithmetic,Cone (formal languages),Pumping lemma for regular languages,Regular grammar,Combinatorics on words,Mathematics
Journal
Volume
ISSN
Citations 
268,
0020-0255
4
PageRank 
References 
Authors
0.58
9
3
Name
Order
Citations
PageRank
Jürgen Dassow1530118.27
Florin Manea237258.12
Robert Mercaş3506.15