The pseudopalindromic completion of regular languages. (English) Zbl 1309.68118
Summary: 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.
MSC:
| 68Q45 | Formal languages and automata |
Keywords:
pseudopalindromes; pseudopalindromic completion; pseudopalindromic iterated completion; regular languages; algorithms; decidabilityReferences:
| [1] | Păun, G.; Rozenberg, G.; Yokomori, T., Hairpin languages, Int. J. Found. Comput. Sci., 837-847 (2001) · Zbl 1319.68139 |
| [2] | Cheptea, D.; Martín-Vide, C.; Mitrana, V., A new operation on words suggested by DNA biochemistry: hairpin completion, (Transgressive Computing (2006)), 216-228 · Zbl 1191.92013 |
| [3] | Diekert, V.; Kopecki, S.; Mitrana, V., On the hairpin completion of regular languages, (Leucker, M.; Morgan, C., ICTAC. ICTAC, Lect. Notes Comput. Sci., vol. 5684 (2009), Springer), 170-184 · Zbl 1250.68153 |
| [4] | Kari, L.; Kopecki, S.; Seki, S., Iterated hairpin completions of non-crossing words, (Bieliková, M.; Friedrich, G.; Gottlob, G.; Katzenbeisser, S.; Turán, G., SOFSEM. SOFSEM, Lect. Notes Comput. Sci., vol. 7147 (2012), Springer), 337-348 · Zbl 1302.68167 |
| [5] | Manea, F.; Martín-Vide, C.; Mitrana, V., On some algorithmic problems regarding the hairpin completion, Discrete Appl. Math., 157, 9, 2143-2152 (2009) · Zbl 1185.68392 |
| [6] | Manea, F.; Martín-Vide, C.; Mitrana, V., Hairpin lengthening, (Ferreira, F.; Löwe, B.; Mayordomo, E.; Gomes, L. M., CiE. CiE, Lect. Notes Comput. Sci., vol. 6158 (2010), Springer), 296-306 · Zbl 1286.68139 |
| [7] | Manea, F.; Mitrana, V., Hairpin completion versus hairpin reduction, (Cooper, S. B.; Löwe, B.; Sorbi, A., CiE. CiE, Lect. Notes Comput. Sci., vol. 4497 (2007), Springer), 532-541 · Zbl 1151.68420 |
| [8] | Manea, F.; Mitrana, V.; Yokomori, T., Two complementary operations inspired by the DNA hairpin formation: completion and reduction, Theor. Comput. Sci., 410, 4-5, 417-425 (2009) · Zbl 1160.68022 |
| [9] | Manea, F.; Mitrana, V.; Yokomori, T., Some remarks on the hairpin completion, Int. J. Found. Comput. Sci., 21, 5, 859-872 (2010) · Zbl 1213.68356 |
| [10] | Ito, M.; Leupold, P.; Manea, F.; Mitrana, V., Bounded hairpin completion, Inf. Comput., 209, 3, 471-485 (2011) · Zbl 1221.68136 |
| [11] | Kopecki, S., On iterated hairpin completion, Theor. Comput. Sci., 412, 29, 3629-3638 (2011) · Zbl 1216.68145 |
| [12] | de Luca, A., Sturmian words: structure, combinatorics, and their arithmetics, Theor. Comput. Sci., 183, 1, 45-82 (1997) · Zbl 0911.68098 |
| [13] | de Luca, A.; Luca, A. D., Pseudopalindrome closure operators in free monoids, Theor. Comput. Sci., 362, 1-3, 282-300 (2006) · Zbl 1101.68073 |
| [14] | Mahalingam, K.; Subramanian, K. G., Palindromic completion of a word, (BIC-TA (2010), IEEE), 1459-1465 |
| [15] | Slama-Schwok, A.; Brossalina, E.; Demchenko, Y.; Best-Belpomme, M.; Vlassov, V., Structural flexibility of a DNA hairpin located in the long terminal repeat of the drosophila 1731 retrotransposon, Nucleic Acids Res., 26, 22, 5142-5151 (1998) |
| [16] | Harrison, M. A., Introduction to Formal Language Theory (1978), Addison-Wesley: Addison-Wesley Reading, Massachusetts · Zbl 0411.68058 |
| [17] | Lothaire, M., Combinatorics on Words (1997), Cambridge University Press · Zbl 0874.20040 |
| [18] | Kari, L.; Mahalingam, K., Watson-Crick palindromes in DNA computing, Nat. Comput., 9, 2, 297-316 (2010) · Zbl 1207.68236 |
| [19] | Horváth, S.; Karhumäki, J.; Kleijn, J., Results concerning palindromicity, J. Inf. Process. Cybern., 23, 441-451 (1987) · Zbl 0634.68072 |
| [20] | Kärkkäinen, J.; Sanders, P.; Burkhardt, S., Linear work suffix array construction, J. ACM, 53, 918-936 (2006) · Zbl 1326.68111 |
| [21] | Gusfield, D., Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology (1997), Cambridge University Press: Cambridge University Press New York, NY, USA · Zbl 0934.68103 |
| [22] | Holzer, M.; Kutrib, M., Nondeterministic descriptional complexity of regular languages, Int. J. Found. Comput. Sci., 14, 6, 1087-1102 (2003) · Zbl 1101.68657 |
| [23] | Fazekas, S. Z.; Mercaş, R.; Shikishima-Tsuji, K., Hairpin completion with bounded stem-loop, (Ibarra, O. H.; Yen, H.-C., DLT. DLT, Lect. Notes Comput. Sci., vol. 7410 (2012), Springer), 428-439 · Zbl 1370.68244 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
