Abstract



We consider a restricted variant of the prefixsuffix duplication operation, called bounded prefixsuffix duplication. It consists in the iterative duplication of a prefix or suffix, whose length is bounded by a constant, of a given word. We give a sufficient condition for the closure under bounded prefixsuffix duplication of a class of languages. Consequently, the class of regular languages is closed under bounded prefixsuffix duplication; furthermore, we propose an algorithm deciding whether a regular language is a finite kprefixsuffix duplication language. An efficient algorithm solving the membership problem for the kprefixsuffix duplication of a language is also presented. Finally, we define the kprefixsuffix duplication distance between two words, extend it to languages and show how it can be computed for regular languages.  
International

Si 
Congress

19th International Conference Implementation and Application of Automata CIAA 2014 

960 
Place

Giessen, Alemania 
Reviewers

Si 
ISBN/ISSN

9783319088457 

10.1007/9783319088464 
Start Date

30/07/2014 
End Date

02/08/2014 
From page

176 
To page

187 

Lecture Notes in Computer Science Volume: 8587 LNCS 