@inproceedings{8e58741ac98f4841a61c0f07515e96c3,
title = "Most Pseudo-copy Languages Are Not Context-Free",
abstract = "It is well known that the copy language L= { ww∣ w∈ Σ∗} is not context-free despite its simplicity. We study pseudo-copy languages that are defined to be sets of catenations of two similar strings, and prove non-context-freeness of these languages. We consider the Hamming distance and the edit-distance for the error measure of the two similar strings in pseudo-copy languages. When the error has an upper bound or a fixed value, we show that the pseudo-copy languages are not context-free. Similarly, if the error has a lower bound of at least four, then such languages are not context-free, either. Finally, we prove that all these pseudo-copy languages are context-sensitive.",
keywords = "Context-freeness, Edit-distance, Hamming distance, Pseudo-copy languages",
author = "Hyunjoon Cheon and Joonghyuk Hahn and Han, {Yo Sub} and Ko, {Sang Ki}",
note = "Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.; 27th International Conference on Computing and Combinatorics, COCOON 2021 ; Conference date: 24-10-2021 Through 26-10-2021",
year = "2021",
doi = "10.1007/978-3-030-89543-3_16",
language = "English",
isbn = "9783030895426",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "189--200",
editor = "Chi-Yeh Chen and Wing-Kai Hon and Ling-Ju Hung and Chia-Wei Lee",
booktitle = "Computing and Combinatorics - 27th International Conference, COCOON 2021, Proceedings",
address = "Germany",
}