Most pseudo-copy languages are not context-free

DOI10.1007/978-3-030-89543-3_16OpenAlexW3209514597MaRDI QIDQ2695285

Sang-Ki Ko, Yo-Sub Han, Hyunjoon Cheon, Joonghyuk Hahn

Publication date: 30 March 2023

Full work available at URL: https://doi.org/10.1007/978-3-030-89543-3_16

zbMATH Keywords

Hamming distanceedit-distancecontext-freenesspseudo-copy languages

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Related Items (1)

Weak inverse neighborhoods of languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal off-line detection of repetitions in a string
• Finding approximate repetitions under Hamming distance.
• Über einen Automaten mit Pufferspeicherung
• An O(n log n) algorithm for finding all repetitions in a string
• Finite Automata, Palindromes, Powers, and Patterns
• An “Interchange Lemma” for Context-Free Languages
• Algorithms on Strings, Trees and Sequences
• Error Detecting and Error Correcting Codes
• Squares of regular languages
• Queue Automata: Foundations and Developments
• Simple and flexible detection of contiguous repeats using a suffix tree
• Hairpin completions and reductions: semilinearity properties

This page was built for publication: Most pseudo-copy languages are not context-free