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.
| Original language | English |
|---|---|
| Title of host publication | Computing and Combinatorics - 27th International Conference, COCOON 2021, Proceedings |
| Editors | Chi-Yeh Chen, Wing-Kai Hon, Ling-Ju Hung, Chia-Wei Lee |
| Publisher | Springer Science and Business Media Deutschland GmbH |
| Pages | 189-200 |
| Number of pages | 12 |
| ISBN (Print) | 9783030895426 |
| DOIs | |
| Publication status | Published - 2021 |
| Event | 27th International Conference on Computing and Combinatorics, COCOON 2021 - Tainan, Taiwan, Province of China Duration: 2021 Oct 24 → 2021 Oct 26 |
Publication series
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 13025 LNCS |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Conference
| Conference | 27th International Conference on Computing and Combinatorics, COCOON 2021 |
|---|---|
| Country/Territory | Taiwan, Province of China |
| City | Tainan |
| Period | 21/10/24 → 21/10/26 |
Bibliographical note
Publisher Copyright:© 2021, Springer Nature Switzerland AG.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- General Computer Science