The pseudopalindromic completion of regular languages

DOI10.1016/j.ic.2014.09.001zbMath1309.68118MaRDI QIDQ476182

Florin Manea, Szilárd Zsolt Fazekas, Kayoko Shikishima-Tsuji, Robert Mercaş

Publication date: 28 November 2014

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2014.09.001

zbMATH Keywords

algorithms; decidability; regular languages; pseudopalindromes; pseudopalindromic completion; pseudopalindromic iterated completion

Mathematics Subject Classification ID

68Q45: Formal languages and automata

Related Items

Absent Subsequences in Words

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On iterated hairpin completion
• Bounded hairpin completion
• Two complementary operations inspired by the DNA hairpin formation: Completion and reduction
• On some algorithmic problems regarding the hairpin completion
• Sturmian words: structure, combinatorics, and their arithmetics
• Pseudopalindrome closure operators in free monoids
• Iterated Hairpin Completions of Non-crossing Words
• SOME REMARKS ON THE HAIRPIN COMPLETION
• Hairpin Completion with Bounded Stem-Loop
• On the Hairpin Completion of Regular Languages
• Linear work suffix array construction
• Hairpin Lengthening
• Algorithms on Strings, Trees and Sequences
• HAIRPIN LANGUAGES
• Hairpin Completion Versus Hairpin Reduction
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• Watson-Crick palindromes in DNA computing