Die Einbettungs-Relation

Def: u≤v, falls u aus v durch Löschen von Buchstaben

• ist Halbordnung (transitiv, reflexiv, antisymmetrisch),
• ist keine totale Ordnung

Testfragen:

• Gegeben v. Für wieviele u gilt u≤v?
• Effizienter Algorithmus für: Eingabe u, v, Ausgabe u≤v (Boolean)