Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
426486 | Information and Computation | 2014 | 15 Pages |
Abstract
Pseudopalindromes are words that are fixed points for some antimorphic involution. In this paper we discuss a newer word operation, that of pseudopalindromic completion, in which symbols are added to either side of the word such that the new obtained words are pseudopalindromes. This notion represents a particular type of hairpin completion, where the length of the hairpin is at most one. We give precise descriptions of regular languages that are closed under this operation and show that the regularity of the closure under the operation is decidable.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Szilárd Zsolt Fazekas, Florin Manea, Robert Mercaş, Kayoko Shikishima-Tsuji,