Restorations of punctured languages and similarity of languages

✍ Scribed by Gerhard Lischke

• Publisher: John Wiley and Sons
• Year: 2006
• Tongue: English
• Weight: 165 KB
• Volume: 52
• Category: Article
• ISSN: 0044-3050
• DOI: 10.1002/malq.200510017

✦ Synopsis

We investigate to which extent restoration of punctured languages is possible if the number of unknown positions or the proportion of unknown positions per word, respectively, is bounded, and we study their relationships for different boundings. The considered restoration classes coincide with similarity classes according to some kind of similarity for languages. Thus all results we can also formulate in the language of similarity. We show some hierarchies of similarity classes for each class from the Chomsky hierarchy and prove the existence of linear languages which are not δ-similar to any regular language for any δ < 1 2 . For δ ≥ 1 2 this is unknown but it could only be possible in the case of non-slender linear languages.