Die Einbettungs-Relation

Def: u$\le$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$\le$v?
• Effizienter Algorithmus für: Eingabe u, v, Ausgabe u$\le$v (Boolean)