Abstract
The k-prefix-free, k-suffix-free and k-infix-free languages generalize the prefix-free, suffix-free and infix-free languages by allowing marginal errors. For example, a string x in a k-prefix-free language L can be a prefix of up to k different strings in L. We also define finitely prefix-free languages in which a string x can be a prefix of finitely many strings. We present efficient algorithms that determine whether or not a given regular language is k-prefix-free, k-suffix-free or k-infix-free, and analyze the time complexity of the algorithms. We establish undecidability results for deciding these properties for (linear) context-free languages.
Original language | English |
---|---|
Article number | 2141005 |
Pages (from-to) | 509-529 |
Number of pages | 21 |
Journal | International Journal of Foundations of Computer Science |
Volume | 32 |
Issue number | 5 |
DOIs | |
State | Published - Aug 2021 |
Keywords
- Codes
- context-free languages
- decision algorithms
- marginal errors
- regular languages
- undecidability